5. 选择排序¶

5.1. 选择排序¶

再考虑给过去一年的电话账单排序这个问题。另一种直观的做法是：翻遍整叠账单直到找到一月份的那张，把它抽出来。然后翻遍剩下的一叠，找到二月份的账单，放在一月份的后面。对着不断缩小的一叠账单继续这样做，按顺序选出下一张，直到全部完成。这就是我们最后一个 \(\Theta(n^2)\) 排序算法—— 选择排序的灵感来源。选择排序的第 \(i\) 趟"选出"数组中第 \(i\) 大的键，把该记录放到数组末端。换句话说，选择排序先找到无序线性表中最大的键，然后找次大的，依此类推。它的独特之处在于记录交换的次数很少。为了找到下一个更大的键，需要扫过数组整个无序部分，但只需一次交换就能把记录放到位。因此，所需的交换总次数是 \(n-1\) （最后一条记录"免费" 就位）。

下面是选择排序的一种实现。

Java
Java (Generic)
C++

void selsort(int[] A) {
  for (int i=0; i<A.length-1; i++) {       // Select i'th biggest record
    int bigindex = 0;                      // Current biggest index
    for (int j=1; j < A.length-i; j++)     // Find the max value
      if (A[j] > A[bigindex])              // Found something bigger  
        bigindex = j;                      // Remember bigger index
    swap(A, bigindex, A.length-i-1);       // Put it into place
  }
}

void selsort(T[] A) {
  for (int i=0; i<A.length-1; i++) {       // Select i'th biggest record
    int bigindex = 0;                      // Current biggest index
    for (int j=1; j<A.length-i; j++)       // Find the max value
      if (A[j].compareTo(A[bigindex]) > 0) // Found something bigger
        bigindex = j;                      // Remember bigger index
    swap(A, bigindex, A.length-i-1);       // Put it into place
  }
}

void selectionsort(Comparable* A[], int n) {
  for (int i = 0; i < n-1; i++) { // Select i'th biggest record
    int bigindex = 0;             // Current biggest index
    for (int j = 1; j < n-i; j++) // Find the max value
      if (*A[j] > *A[bigindex])   // Found something bigger
        bigindex = j;             // Remember bigger index    
    swap(A, bigindex, n-i-1);     // Put it into place
  }
}