如何加快插入排序的速度？

Question

我有这段代码

   class Child{
    public:
        string code;
        float avg;
        unsigned int distance;
        int month;
        bool isSmallerThan(Child child, char *ordering_chars);
    };

    bool Child::isSmallerThan(Child child, char *ordering_chars) {
        for(int i=0; i<3; i++){
            if(ordering_chars[i] == 'a'){
                if(avg == child.avg)
                    continue;
                return avg < child.avg;
            }
            else if(ordering_chars[i] == 'd'){
                if(distance == child.distance)
                    continue;
                return distance < child.distance;
            }
            else if(ordering_chars[i] == 'm'){
                if(month == child.month)
                    continue;
                return month < child.month;
            }
        }
        return false;
    }

    void InsertionSort(Child *array, int n, char *ordering_chars){

        Child temp;
        int i, j;
        for(j = 1; j < n; j++)
        {
            temp = array[j];
            for(i = j - 1; (i >= 0) && array[i].isSmallerThan(temp, ordering); i--)
            {
                array[i+1] = array[i];
            }
            array[i+1] = temp;
        }
    }

我有一个Child对象的数组，我想按不同的字段对其进行排序，这取决于从stdin获取的ordering_chars数组。例如，如果ordering_chars是['a'，'d'，'m']，则表示如果平均值相等，则按距离排序，如果它也相等，则按月份排序。代码能够工作，但对于大数据而言速度过慢。你有什么解决方法可以使其更加高效吗？我想使用函数指针来解决，但我不确定如何做到这一点。

PS. 我必须使用InsertionSort，不能使用其他方式进行排序，另外我不能使用STL，因为这个代码是用于在线评测的（我不参加任何比赛，只是为了测试自己和学习）。

- Shacerr

---

你必须使用插入排序吗？插入排序被认为是相对低效的算法。 - artemis

很不幸，它必须是插入排序，但可以稍作修改。 - Shacerr

你犯的第一个错误是编写自己的排序算法并期望它能够执行。C++自带了一个快速排序实现，可能已经被优化得很好了。研究一下这段代码，以获取改进代码的思路。此外，对于任何类似“如何使这个更快？”的问题，你必须进行测量，因此去获取一个所谓的分析器，并在你的代码上使用它。 - Ulrich Eckhardt

是的，C++ 中有高效的排序算法，但重点是我必须阅读自己实现的这个（插入）排序算法。这段代码并不适用于实际生活中的使用，更像是一种教育性质的东西。 - Shacerr

@JerryM.，在恰当使用的情况下，插入排序不是一件坏事。特别地，std::sort（至少在 MS 实现中）在一个区间包含少于 ~30 个元素时会采用插入排序。 - Evg

Answer 1

由于您正在为Child变量制作大量副本，所以速度太慢。

将Child::isSmallerThan更改为按引用而非按值传递Child&。还要将Child tmp放在循环内并将其也更改为引用。

正如您建议的那样，您可以优化比较函数。创建3个lambda表达式，每个表达式返回-1、0、1表示小于、等于或大于：

auto get_comparator(char c) {
  if (c == 'a')
   return +[] (Child& x, Child& y) { /* compare x.avg and y.avg */ }
  if (c == 'd') 
   return +[] (Child& x, Child& y) { ... }
  if (c == 'm')
   return +[] (Child& x, Child& y) { ... }
}

在您的插入排序中，您可以创建比较函数：

```html

在您的插入排序中，您可以创建比较函数：

```

auto comp_first = get_comparator(ordering_chart[0]);
auto comp_second = get_comparator(ordering_chart[1]);
auto comp_second = get_comparator(ordering_chart[2]);

auto comparator = [comp_first, comp_second, comp_second](Child& x, Child& y) {
  int rez = comp_first(x, y);
  if (rez != 0) return rez == 1;
  rez = comp_second(x, y);
  if (rez != 0) return rez == 1;
  rez = comp_third(x, y);
  return rez == 1;
}

使用该值来比较这些子元素。

- Bob Bills

---

好的建议 - 但如果你遵循它，请确保计时差异以找出它有多快！ - tucuxi

这里为什么要使用非const引用？（我通常默认使用const，即除非我特别想修改一个对象） - DodgyCodeException

@DodgyCodeException 没有理由不使用它，const 是首选，只是不想用太长的代码吓到人们。 - Bob Bills

Answer 2

通过在找到一个项目的正确位置后仅执行一次交换，您可以避免大量的小交换。 代码中（请注意，未经测试 - 可能存在不对称错误），

for(int j = 1; j < n; j++) {
   Child temp = array[j];
   int swaps = 0;
   for(int i = j-1; (i >= 0) && array[i].isSmallerThan(temp, ordering); i--) {
      swaps ++;
   }
   if (swaps) {
        // make space & place new element where it belongs
        // beware: this may be problematic for more complex classes
        memmove(array+i+2, array+i+1, swaps);
        array[i+1] = temp;
   }
}

另一种节省的方法来自于更快的比较函数。请参见Bob's answer以获取可能的实现。如果不使用Lambda，我会选择

bool Child::isSmallerThan(const Child &o, char *ordering_chars) const {
    int m = month == o.month ? 0 : month < o.month ? 1 : -1;
    int d = distance == o.distance ? 0 : distance < o.distance ? 1 : -1;
    int a = avg == o.avg ? 0 : avg < o.avg ? 1 : -1;

    switch (ordering_chars[0]) {
      case 'a': a <<= 2; break;
      case 'd': d <<= 2; break;
      case 'm': m <<= 2; break;
    }
    switch (ordering_chars[1]) {
      case 'a': a <<= 1; break;
      case 'd': d <<= 1; break;
      case 'm': m <<= 1; break;
    }

    return a+d+m > 0;
}

- tucuxi

---

你的算法不是选择排序而是插入排序吗？ - DodgyCodeException

哎呀，对了。我一边写代码一边修复它。我总是容易混淆这两个。 - tucuxi

已修复，现在使用单次交换插入排序。 - tucuxi

现在想象一下，如果Child中的一个字段是指向具有虚析构函数的对象的智能指针，会发生什么。 - DodgyCodeException

如果您在所有地方都使用memcpy/memmove，包括从temp复制到和复制回去的操作，那么我认为您可能没问题。但是，如果对于某些数组元素使用复制构造函数，而对于其他元素使用位拷贝，则不行。 - DodgyCodeException

当前的子类没有这样的指针。我已经添加了免责声明。 - tucuxi