优化选择排序？

Question

我读到的消息来源说，选择排序的时间复杂性是：

• 最佳案例: O(n^2)
• 平均数: O(n^2)
• 最坏情况: O(n^2)

我想知道，如果剩余的部分已经排序，那么通过添加一行代码来使算法本身“短路”，是否值得“优化”该算法。

下面是用C编写的代码：

我还添加了一个注释，指出哪些行是“优化”部分的一部分。

void printList(int* num, int numElements) {
    int i;  

    for (i = 0; i < numElements; i ++) {
        printf("%d ", *(num + i));
    }
    printf("\n");
}

int main() {
    int numElements = 0, i = 0, j = 0, min = 0, swap = 0, numSorted = 0;

    printf("Enter number of elements: ");
    scanf("%d", &numElements);

    int* num = malloc(sizeof(int) * numElements);

    for (i = 0; i < numElements; i ++) {
        printf("Enter number = ");
        scanf(" %d", num + i);
    }

    for (i = 0; i < numElements-1; i++) {
        numSorted = i + 1;  // "optimized"
        min = i;

        for (j = i + 1; j < numElements; j++) {
            numSorted += *(num + j - 1) <= *(num + j);  // "optimized"
            if (*(num + min) > *(num + j))
                min = j;
        }

        if (numSorted == numElements)  // "optimized"
           break;

        if (min != i) {
            swap = *(num + i);
            *(num + i) = *(num + min);
            *(num + min) = swap;
        }

        printList(num, numElements);
    }

    printf("Sorted list:\n");
    printList(num, numElements);

    free(num);

    getch();
    return 0;

}

Answer 1

优化选择排序有点傻。它有可怕的最佳情况，平均和最坏的时间复杂性，所以如果你想要一个远程优化的排序，你会(几乎？)一定要选另一种。甚至插入排序也会更快，实现起来也不会复杂得多。

更重要的是，检查列表是否被排序会增加算法在最坏情况下所花费的时间(我也倾向于考虑平均情况)。而且，即使是排序最多的列表也不一定会以这种方式进行得更快:考虑一下1,2,3,4,5,6,7,9,8。即使列表只需要在结束时交换两个元素，算法也不会短路，因为它直到结束才会被排序。

Answer 2

仅仅因为某些东西可以被优化，并不一定意味着它应该。假设分析或“老板说-所以”表明优化是合理的，有几件事你可以做。

与任何涉及内存迭代的算法一样，任何减少迭代次数的方法都会有所帮助。

• 记录最小值和最大值-将迭代次数减半。
• 跟踪多个min/最大值(每个值为1/8，迭代)
  • 在某些情况下，temp值将不适合于寄存器。
  • 代码会变得更复杂

​

它还可以帮助最大化缓存的局部性。

• 在前向迭代之后执行反向迭代
  • 最近访问的内存仍然应该被缓存。
  • 直接进行另一次前向迭代会导致缓存丢失。
  • 由于您正在向后移动，缓存预测器可能会预取其余部分。
  • 实际上，这在某些架构上可能会更糟(RISC-V)

​

• 在可能的情况下，在缓存行上操作
  • 这可以允许在同一时间预取下一个缓存行。
  • 您可能需要对齐数据或专门处理第一个和最后一个数据。
    • 即使增加了对齐，最后几个元素也可能需要“填充”。

​

​

在有用和实用的地方使用SIMD指令和寄存器

• 适用于非分支秩阶的温度排序
• 可以同时容纳多个数据点(AVX-512可以执行高速缓存)。
• 避免内存访问(从而减少缓存丢失)

如果使用多个max/min值，则对max和min的n值进行优化排序。

• 有关排序少量固定值的技术，请参见here。
• 将内存交换保存到每次迭代结束，并执行一次
  • 同时将临时人员(或指针)保存在寄存器中

​

有许多更多的优化方法可用，但最终相似的选择排序开始变得模糊。每一种方法都会增加复杂性，从而增加维护成本，以至于一个更简单的实现更合适的算法可能是一个更好的选择。

Answer 3

我看到如何回答这个问题的唯一方法是，如果您定义了为什么要优化它的目的。

• 在一个专业的环境中，这值得吗?在工作中，对于“在生产中”运行的代码来说--大多数可能是(甚至几乎可以肯定)是而不是。
• 作为一个教/学的工具，它值得吗?有时，，yes，。

我教个人编程，有时我教他们算法和数据结构。我认为选择排序是最容易解释和教授的方法之一--在解释了寻找最小值和交换两个值的算法(swap())之后，它就自然而然地流动了。最后，我介绍了优化的概念，在这里我们可以实现这个计数器“已经排序”的检测。

诚然，气泡排序更适合引入优化，因为它至少有3个易于解释和实质性的优化。