c++ - 如何使插入排序更快？

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 相等，则按距离排序，如果也相等，则按月排序。该代码正在运行，但它会因大数据而变慢。您是否有一些解决方案可以使这项工作更有效率？我在考虑使用函数指针，但我不确定如何准确地做到这一点。

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

Answer 1

它太慢了，因为您正在为您的子变量制作大量拷贝。

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

另外，正如您所建议的，您可以优化比较功能。为后一种情况创建 3 个 lambda，返回 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