如何使插入排序更快？

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 对象数组，我想按不同的字段对它进行排序，这取决于从标准输入中获取的 ordering_chars 数组。例如，如果 ordering_chars 是 ['a', 'd', 'm'] 这意味着如果 avg 相等，则按距离排序，如果也相等，则排序按月。该代码正在运行，但它会因大数据而变慢。您是否有一些解决方案可以使这项工作更有效率？我正在考虑使用函数指针，但我不确定该怎么做。

PS。我必须使用InsertionSort，它不能是任何其他排序方式，而且我不能使用STL，这是因为这段代码是为了进行Online Judge（我没有参加任何类型的比赛，只是为了测试自己并学习一些东西）。

Answer 1

它太慢了，因为您正在为 Child 变量制作大量副本。

更改 Child::isSmallerThan 以通过引用而非值来获取 Child&。并更改 Child tmp。将它放在循环中并将其也更改为引用。

也按照您的建议优化比较功能。为后一种情况制作 3 个 lambdas，return 一个 int -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) { ... }
}

在您的 InsertionSort 中，您可以创建比较函数：

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;
}

并用那个来比较 Children

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;
   }
}

节省的另一个来源是更快的比较功能。有关可能的实施，请参阅。如果不使用 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;
}

如何使插入排序更快？

How to make InsertionSort faster?

c++

sorting

algorithm

children

object