数据结构 | 内排序：交换排序算法

一些术语：

• 函数prior-比较器类最重要的方法。如果返回值为真，说明排好序后第一个参数应该放在第二个参数之前。
• 函数swap-交换数组中（若未特殊说明，排序算法的输入都存储在数组中）的两条记录的内容。
• 排序问题-重排一组记录，使其关键码域的值单调递增（注意，不是严格的单调递增）。
• 稳定的排序算法-不会改变关键码值相同的记录的相对顺序的算法。

一　插入排序

  插入排序方法逐个处理待排序的记录。每条新记录与前面已排序的子序列进行比较，将它插入子序列中的正确位置。
  下面是从教材中摘录的插入排序的实现。

// Insertion sort implementation
template <typename E, typename Comp>
void inssort(E A[], int n) { // Insertion Sort
  for (int i=1; i<n; i++)       // Insert i'th record
    for (int j=i; (j>0) && (Comp::prior(A[j], A[j-1])); j--)
      swap(A, j, j-1);
}··

• 最佳情况（关键码按照正序排列）：只需要比较n-1次，因此比较时间代价为$\Theta(n)$；交换次数总是比较次数减去n-1（每一轮比较的最后一次比较无需交换），因此交换时间代价为0；
• 最差情况（关键码按照倒序排列）：需要依次做1,2,…,n-1次比较，总和约为$n^2/2$，因此比较时间代价为$\Theta(n^2)$，交换时间代价为$\Theta(n^2)$；

  实际上，插入排序的时间代价与其无序程度——逆置总数目有关。逆置是指对于一个待排序记录的关键码值，前面记录的关键码值大于其的数目。逆置的总数目决定了比较和交换的次数。

• 平均情况（对于第i条记录，其前面的i-1条记录中有一半关键码值大于之）：比较次数约为最差情况的一半，即$n^2/4$，因此比较时间代价为$\Theta(n^2)$，交换时间代价为$\Theta(n^2)$。

---

二　冒泡排序

  冒泡排序从记录数组的底部比较到顶部，比较相邻的关键码。
  下面是从教材中摘录的冒泡排序的实现。

// Bubble sort implementation
template <typename E, typename Comp>
void bubsort(E A[], int n) { // Bubble Sort
  for (int i=0; i<n-1; i++)     // Bubble up i'th record
    for (int j=n-1; j>i; j--)
      if (Comp::prior(A[j], A[j-1]))
        swap(A, j, j-1);
}

  无论什么情况下，对于每一轮外层循环而言，内层循环的比较次数总是相对上一轮少1。也就是说，需要依次做n,n-1…,1次比较，总和约为$n^2/2$，因此比较时间代价为$\Theta(n^2)$。
  交换时间代价则与插入排序相同。

---

三　选择排序

  选择排序首先从排序的序列中找到最小关键码值，接着是次小关键码值，以此类推。
  下面是从教材中摘录的选择排序的实现。

// Selection sort implementation
template <typename E, typename Comp>
void selsort(E A[], int n) { // Selection Sort
  for (int i=0; i<n-1; i++) {   // Select i'th record
    int lowindex = i;           // Remember its index
    for (int j=n-1; j>i; j--)   // Find the least value
      if (Comp::prior(A[j], A[lowindex]))
	      lowindex = j;           // Put it in place
    swap(A, i, lowindex);
  }
}

  这里的选择排序从记录数组的顶部开始，依次比较相邻的关键码，因此比较时间代价与冒泡排序相同，为$\Theta(n^2)$。交换发生在外层循环的最后，次数是$n-1$，因此交换时间代价为$\Theta(n)$。

---

四　交换排序算法的时间代价

  插入排序、冒泡排序、选择排序是三种典型的交换排序算法。它们的渐近复杂度比较如表T1所示。它们在平均及最差情况下的时间代价（将比较和交换的时间代价相加，并应用化简法则）均为$\Theta(n^2)$。

	插入排序	冒泡排序	选择排序
比较情况
最佳情况	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$
平均情况	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$
最差情况	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$
交换情况
最佳情况	0	0	$\Theta(n)$
平均情况	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n)$
最差情况	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n)$

T1.三种交换排序算法的渐近复杂度比较

  它们的共性在于它们都依赖数组中所有记录移动到“正确”位置所要求的总步数，即逆置。对于一个含有n个元素的序列L而言，其中有$C^2_n=\frac{n(n-1)}{2}$对不同的元素。那么最差情况下就有$\frac{n(n-1)}{2}$对逆置，平均情况下就有$\frac{n(n-1)}{4}$对逆置。因此，可以说任何一种将比较限制在相邻两个元素之间进行的交换算法的平均时间代价至少是$\frac{n(n-1)}{4}=\Omega(n^2)$。