c - 优化选择排序？

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。即使列表只需要在最后交换两个元素，算法也不会短路，因为它直到最后才排序。