Chapter10 排序

基本概念

• 关键字值相同的数据元素在排序前后的相对次序保持不变，则称为稳定排序，否则称为不稳定排序。

排序算法的衡量标准

1. 时间复杂度：考虑比较操作和搬移操作
2. 空间复杂度
3. 稳定性

插入排序

基本原理： 首先将由第一个数据元素组成的序列看成是有序的，然后将剩余的n-1个元素依次插入到前面的已排好序的子序列中去，使得每次插入后的子序列也是有序的。

常见的几种插入排序：

• 直接插入排序
• 折半插入排序
• 希尔排序

直接插入排序

时间复杂度

1. 最佳情况：

   
   • 比较N-1次，$O(N)$
   • 搬移2(N-1)，$O(N)$

2. 最差情况：

   
   • 比较$\sum_{i=1}^{N-1}(i+1)=O(N^2)$​
   • 搬移$\sum_{i=1}^{N-1}(i+2)=O(N^2)$

3. 平均情况

   • 比较$\sum_{i=1}^{N-1}(\dfrac{i}{2}+1)=O(N^2)$​

   • 搬移$\sum_{i=1}^{N-1}(\dfrac{i}{2}+2)=O(N^2)$

空间复杂度

O(1)

稳定性

有稳定性，同样的key顺序可以不变

适用情况

短序列或者几乎是已排序（有序性好）的序列

template <class KEY, class OTHER>
void simpleInsertSort(SET<KEY, OTHER> a[], int size)
{    
	int k;
	SET<KEY, OTHER> tmp; 
    for (int j=1; j<size; ++j) {
         tmp = a[j];
         for ( k = j-1; tmp.key < a[k].key && k >= 0; --k)
             a[k+1] = a[k];
         a[k+1] = tmp;
    }
}

折半插入排序

利用二分查找法，快速地找到a[j]的插入位置。从而使比较次数下降到O(logN)

时间复杂度

• 比较：

$$\sum_{i=1}^{N-1} log(i+1) = O(N log N)$$

• 搬移：

希尔排序

希尔排序的思想是避免大量的数据搬移，先是比较那些离得稍远些的元素，这样，一次交换就相当于直接插入排序中的多次交换。然后比较那些离得近一点的元素，以此类推，逐步逼近直接的插入排序

利用了直接插入排序的两个性质：

1. 在最佳情况下（正序）时间复杂度为O(N);

2. 对于短序列，直接插入排序比较有效。

算法思想

• 先将序列分割成若干个小序列，在这些小序列内进行插入排序；
• 分割方法：相隔一定距离的各个记录组成一个子序列逐渐扩大小序列的规模，
• 减小小序列的个数，使得待排序列处于更有序的状态；
• 最后对整个序列进行直接插入排序，从而完成排序

步长（增量）的选择

如果选择1，2，4，8…… ，时间复杂度为$O(N^2)$

但事实上：

• 步长不应互为倍数

• 最后一次排序步长为1

• Knuth的推荐序列：1，3，7，15，…… ，即$2^n -1$

• 平均时间复杂性是$O(N^\frac{3}{2})$

• 空间复杂度： O(1)

• 不稳定！

代码实现

template <class KEY, class OTHER>
void shellSort(SET<KEY, OTHER> a[], int size)
{
    int step, i, j;
    SET<KEY, OTHER> tmp;
 
    for (step = size/2; step > 0; step /= 2)     //step为希尔增量
    for (i = step; i < size; ++i) {
	     tmp = a[i];
         for (j = i - step; j >= 0 && a[j].key > tmp.key;  j -= step) 
	           a[j+step] = a[j];
	     a[j+step] = tmp;
    }
}

选择排序

• 首先，从n个元素中选出关键字最小的元素。
• 再从剩下的(n-1)个元素中选出关键字最小的元素
• 依次类推，每次从剩下的元素序列中挑出关键字最小的元素，直至序列中最后只剩下一个元素为止。
• 这样，把每次得到的元素排成一个序列，就得到了按非递减序排列的排序序列。

直接选择排序

• 特点：逐个比较
• 首先在所有元素中用逐个比较的方法选出最小元素，把它与第一个元素交换；
• 然后在剩下的元素中再次用逐个比较的方法选出最小元素，把它与第二个元素交换；
• 以此类推，直到所有元素都放入了正确的位置。

分析

• 比较次数：$\dfrac{N^2 -N}{2}$
• 搬移次数：$3(N-1)$​
  • 1次交换=3次搬移
• 时间复杂度：$O(N^2)$​
• 适合短序列；搬移次数少，适合大记录排序
• 不稳定
  • 例子

堆排序

• 直接选择排序在n个元素中选出最小元素需要n-1次比较，而利用基于堆的优先级队列选出最小元素只需要O(logN)的时间
• 排序N个元素，步骤如下：
  • 应用buildHeap对N个元素创建一个优先级队列（堆）
  • 通过调用N-1次deQueue取出每个项，结果就排好序了。

分析

• 时间复杂度：建堆用了$O(N)$的时间，deQueue是对数时间。因此总的时间是$O(NlogN)$。
• 空间复杂度：$O(1)$
• 稳定性：不稳定
• 适用情况：适合长序列

交换排序

• 交换排序就是根据序列中两个数据元素的比较结果来确定是否要交换这两个数据元素在序列中的位置。
• 交换排序的特点是：通过交换，将关键字值较大的数据元素向序列的尾部移动，关键字值较小的数据元素向序列的头部移动。

冒泡排序（直接交换排序）

• 优化：设置交换标志，当一轮冒泡中没有出现交换时，代表序列已经有序，即可终止

分析

• 比较次数：$O(N^2)$
  • 优化后最好情况：有序，只需进行$N-1$次比较，时间复杂度$O(N)$
• 搬移次数：
  • 最好情况：正序$O(1)$
  • 最差情况：逆序$O(N^2)$
  • 平均$O(N^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定
• 不一定适合接近有序的序列因为有不确定性
  • 改进措施：摇动排序，一次向后冒泡，一次向前冒泡，向后和向前交替进行
• 冒泡排序是最差的，即使改进也不如直接插入和直接选择。

快速排序

• 在待排序的序列中选择一个数据元素，以该元素为标准，将所有数据元素分为两组：
  • 第一组的元素均小于或等于标准元素，放在数组的前面部分；
  • 第二组的数据元素均大于标准元素，放在数组的后面部分；
  • 标准元素放在中间，这个位置就是标准元素的最终位置。
  • 这称为一趟划分。
• 然后对分成的两组数据重复上述过程（递归），直到所有的元素都在适当的位置为止。

程序实现

• 执行一次划分，再执行两个递归
• 快速排序是用递归的方式实现的，它的递归参数就是排序的范围

划分函数divide()

template <class KEY, class OTHER>
int divide( SET<KEY, OTHER> a[], int low, int high)
{
     SET<KEY, OTHER>  k = a[low];
     do  {
          while (low < high && a[high].key >= k.key) --high;
          if (low < high) { a[low] = a[high]; ++low;}
          while (low < high && a[low].key <= k.key) ++low;
          if (low < high)  {a[high] = a[low]; --high;}
     } while (low != high);
     a[low] = k;
     return low;
}

快速排序函数quickSort()

template <class KEY, class OTHER>
void quickSort(SET<KEY, OTHER> a[], int low, int high)
{ 
    int mid;

    if (low >= high) return; 
    mid = divide(a, low, high); 
    quickSort( a, low, mid-1);//排序左一半
    quickSort( a, mid+1, high);//排序右一半
}

（可选）包装函数

template <class KEY, class OTHER>
void quickSort(SET<KEY, OTHER> a[], int size)
{
    quickSort(a, 0, size-1);
}

快速排序性能分析

根据快排算法，可以写出运行时间的递归表达式

$$T(N) = T(i) + T(N-i-1) + cN \\ T(0) = T(1) = 1$$

最好情况分析

快速排序的最好情况是中心点将集合划分成两个相同规模的子集，且这种划分发生在递归的每个阶段。 那么就有

$$T(N) = 2T(\dfrac{N}{2}) + cN$$

式子两边同除以N，进行递推转通项

$$\dfrac{T(N)}{N} = \dfrac{T(\frac{N}{2})}{\frac{N}{2}} + c \\ \dfrac{T(\frac{N}{2})}{\frac{N}{2}} = \dfrac{T(\frac{N}{4})}{\frac{N}{4}}+ c \\ \cdots \\ \dfrac{T(2)}{2} = \dfrac{T(1)}{1} + c$$

进行递推转通项，可得

$$T(N) = cNlogN + T(1) = O(NlogN)$$

最坏情况分析

快速排序的最坏情况是中心点是最大或最小，将集合划分成规模为0和N-1的子集，此时

$$T(N) = T(N-1) + cN$$

递推转通项，得到

$$T(N) = T(1) + c \sum_{i=2}^N i = O(N^2)$$

平均情况分析

考虑每个可能的子集规模的开销并求平均值，由于有两个递归调用加上用来执行划分的线性时间

$$T(N) = 2T(\dfrac{\sum_{i=0}^{N-1}T(i)}{N}) + cN$$

这推导真的太烦了，应该不考吧，随便写写了

$$NT(N) - (N-1)T(N-1) = 2T(N-1) + c(2N-1) \\ NT(N) = (N+1)T(N-1) + 2cN$$

然后递推转通项

$$\frac{T(N)}{N+1} = \frac{T(N-1)}{N} + \dfrac{2c}{N+1} \\ \frac{T(N-1)}{N} = \frac{T(N-2)}{N-1} + \dfrac{2c}{N} \\ \cdots$$

相加得到

$$\frac{T(N)}{N+1} = \frac{T(1)}{2} + 2c\sum_{i=3}^{N+1}\dfrac{1}{i} = O(\log N)$$

最终得到结论

$$T(N) = O(N\log N)$$

结论

1. 时间复杂度
   • 每次

归并排序

• Merge sort的思想来于合并两个已排序的有序表
• 实现方法：
  • 顺序比较两者的相应元素，小者移入另一表中
  • 反复如此，直至其中一表为空为止
  • 将另一表中剩余结点自左至右复制到表C的剩余位置。

程序实现

template <class KEY, class OTHER>
void merge(SET<KEY, OTHER> a[], int left, int mid, int right)
{
    SET<KEY, OTHER> *tmp = new SET<KEY,OTHER>[right-left+1]; 
    int i= left, j = mid, k = 0;
 
    while (i < mid && j <= right)                          //两表都未结束
	       if (a[i].key < a[j].key)     tmp[k++] = a[i++]; 
	       else tmp[k++] = a[j++]; 
 
    while ( i<mid )  tmp[k++] = a[i++];       //前半部分没有结束
    while ( j<=right )  tmp[k++] = a[j++];    //后半部分没有结束
	 
    for (i=0, k = left; k<=right; ) a[k++] = tmp[i++];
    delete [] tmp;
}

template <class KEY, class OTHER>
void mergeSort(SET<KEY, OTHER> a[], int left, int right)
{
     int mid = (left+right)/2;
 
     if (left == right) return;
     mergeSort(a, left, mid);
     mergeSort(a, mid+1, right);
     merge(a,left,mid+1,right);
}

（可选）包装函数

template <class KEY, class OTHER>
void mergeSort(SET<KEY, OTHER> a[], int size)
{
    mergeSort(a, 0, size-1);
}

分析

1. 简单地将原始序列分为两个子序列$O(1)$
2. 分别对每个子序列递归排序$OT(N/2)$
3. 最后将排好序的子序列合并为一个有序序列$O(N)$

综上，写出递推公式，并且使用主定理可以得到时间复杂度

$$T(N) = 2T(\frac{N}{2})+ O(N) = O(Nlog_2N)$$

时间复杂度

写出递推公式

• 归并排序具有稳定性，而且也是优化算法中为数不多具有稳定性的
• 时间复杂度$O(NlogN)$
• 空间复杂度$O(N)$​，这是个重要的缺点
• 经常应用在外排序中

基数排序

低位优先法（LSD）

• 先对最低位K0进行口袋排序，然后把所有记录按口袋的顺序收在一起；
• 再对序列按照次低位K1进行口袋排序，然后把所有记录按口袋的顺序收在一起；
• 依次类推，直到对最高位Kd-1排序，序列就变成有序的了。
• 总结：这是一个分、收；分、收；…；分、收的过程。

分析

• 时间复杂度：O(d(N+r))
  • 分：O(N)
  • 收：O®
  • 循环次数d
  • 由于大部分情况下$N >> d,r$，所以可以认为基数排序具有常数级别的时间复杂度$O(N)$
• 空间复杂度：O®
• 稳定
• 注：N指排序的数字数目，r指桶的个数，d为最大数字的位数

程序实现

• 思路：采用带首尾指针的链表，便于收集。
• 每个口袋用单链表表示，建立基数个首尾指针，以指针数组表示。
• 分：对每个口袋建立单链表
• 收：将单链表的首尾指针相连

template <class OTHER>
struct node {
    SET<int, OTHER> data;
    node *next;
 
    node() { next = NULL; }
    node(SET<int, OTHER> d): data(d)
          { next = NULL; }
};

template <class OTHER>
void bucketSort(node<OTHER> *&p)                // p是链表头
{
    node<OTHER> *bucket[10], *last[10], *tail ;        
    int i, j, k, base = 1, max = 0, len = 0;
    for (tail = p; tail != NULL; tail = tail->next)        // 找最大键值
	  if (tail->data.key > max) max = tail->data.key;

    // 寻找最大键值的位数
    if (max == 0) len = 0;
    else while (max > 0) { ++len; max /= 10; }
    for (i = 1; i <= len; ++i) {                 // 执行len次的分配与重组
       for (j = 0; j <= 9; ++j) bucket[j] = last[j] = NULL;      
       while (p != NULL) {                                  // 执行一次分配
  	      k = p->data.key / base % 10;                    
	      if (bucket[k] == NULL)  bucket[k] = last[k] = p;
	      else last[k] = last[k]->next = p; 
	      p = p->next;
       }
       p = NULL;                                             // 重组后的链表头
       for (j = 0; j <= 9; ++j) {                                  // 执行重组
          if (bucket[j] == NULL) continue;
          if (p == NULL)  {p = bucket[j]; tail = last[j];} 
          else tail->next = bucket[j];
          tail = last[j];
       }
       tail->next = NULL;                   // 表尾置空
       base *= 10;                          // 为下一次分配做准备
     }
}

总结

内排序方法比较

算法	最大时间	最小时间	平均时间	辅助空间	稳定性
直接插入排序	$O(N^2)$	$O(N)$	$O(N^2)$	$O(1)$	稳定
折半插入排序	$O(N^2)$	$O(Nlog_2N)$	$O(N^2)$	$O(1)$	稳定
希尔排序	$O(N^2)$	$O(N^{1.5})$	$O(N^{1.5})$	$O(1)$	不稳定
直接选择排序	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	不稳定
堆排序	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$	$O(1)$	不稳定
直接交换（冒泡）排序	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	稳定
快速排序	$O(N^2)$	$O(NlogN)$	$O(NlogN)$	$O(1)$	不稳定
归并排序	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$	$O(N)$	稳定
基数排序	$O(d(N+r))$	$O(d(N+r))$	$O(d(N+r))$	$O(r)$	稳定

注：

• 希尔排序指选定最优序列情况下的希尔排序
• 直接交换（冒泡）排序指没有使用交换标志和摇动排序优化的版本