优化选择排序？

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