4、选择排序

4.1 简单选择排序

简单选择排序的基本思想是：在待排序的数据中选出最大(小)的元素放在其最终位置。简单排序算法的流程如下所示：

void SelectSort(SqList &L){
  for(int i = 1; i < L.length; ++i){
    int k = i;
    for(int j = i+1; j <= L.length; ++j){
      if(L.r[j].key < L.r[k].key) k = j;//记录最小值的位置
    }
    if(k!=i){
      int t = L.r[i];
      L.r[i] = L.r[k];
      L.r[k] = t;//交换
    }
  }
}

简单选择排序在最好情况下的移动次数为0，最坏情况下的移动次数为 3(n−1)。对于比较次数，无论序列处于什么状态，比较次数都是相同的  ∑i=1n−1(n−i)=2n(n−1)。所以简单选择排序的时间复杂度为  O(n2)，空间复杂度为  O(1)。简单选择排序是不稳定的排序。

4.2 堆排序

堆的定义： 若n个元素的序列  {a1,a2,...,an}满足 { a i ≤ a 2 i a i ≤ a 2 i − 1

{ai≤a2iai≤a2i−1

{ai≤a2iai≤a2i−1则称序列为小根堆；若满足 { a i ≥ a 2 i a i ≥ a 2 i − 1

{ai≥a2iai≥a2i−1

{ai≥a2iai≥a2i−1则称序列为大根堆。

从堆的定义来看，堆实质是满足“二叉树中任一非叶子节点均小于(大于)它的孩子结点”的完全二叉树。

对排序的基本方法：若在输出堆顶的最小值之后，使得剩余 n − 1 n-1 n−1个元素的序列重新又建成一个堆，则得到n个元素的次小值(次大值)… …如此反复，便能得到一个有序序列，这个过程称之为对排序。

4.2.1 调整剩余元素为新的堆

将小根堆输出堆顶元素之后，剩余元素调整称为新的堆的过程如下所示：在输出堆顶元素之后，用堆中最后一个元素代替之；之后将根结点的值与左、右子树的根节点值进行比较，并与其中的小者进行交换；重复上述操作，直至到叶子节点，将得到新的堆，称这个从堆顶到叶子的调整过程为“筛选”。筛选过程的代码如下所示：

void HeapAdjust(int R[], int length, int s){
  int rc = R[s];
  for(int j = 2*s; j < length; ++j){
    if(j + 1 < length && R[j] < R[j+1])++j;
    if(rc >= R[j]) break;//找到rc应该插入的位置
    R[s] = R[j];//rc的位置不断往下移动
    s = j;
  }
  R[s] = rc;//将rc插入到最终找到的rc的位置上
}

所以，对于一个无序的序列，进行反复筛选只有便可以得到一个堆。从最后一个非叶子结点开始，向前调整，依次调整 n/2−(n/2−1)的子树，直到所有数均为大根堆或者小根堆为止。无需序列进行调整的代码如下所示：

void AllHeapAdjust(int R[], int length, int s){
  for(int i = n/2; i >= 1; --i)
    HeapAdjust(R, length, i);
}

整个堆排序算法的流程如下所示：

void HeapSort(int R[]){
  int i = 0;
  for(int i = n/2; i >= 1; --i)
    HeapAdjust(R, i, n);//建立初始堆
  for(int i = n; i > 1; --i){
    Swap(R[1], R[i]);//根与最后一个元素进行交换
    HeapAdjust(R, 1, i - 1);//对R[1]到R[i-1]重新建立堆
  }
}

对于堆排序来说，最坏最坏情况下的时间复杂度均为 O(nlogn)。堆排序的空间复杂度为O(1)，同时堆排序是不稳定的排序方式。

5、归并排序

归并排序的基本思想是：将两个或者两个以上的有序子序列“归并”成一个有序序列。在内部排序中，通常采用2-路归并排序，即将两个位置相邻的有序子序列 R[m+1,...,n]归并成一个有序序列 R[1,...,n]。2-路归并排序的示意如下图所示：

有 n个元素的序列最多需要合并的次数为 log2n。

归并排序的时间效率为 O(nlog2n)；空间效率为  O(n)，因为归并排序需要一个与原始序列同样大小的辅助序列；归并排序是一个稳定排序。

6、基数排序

基数排序的基本思想是：分配+收集。基数排序也叫桶排序或者箱排序，首先设置若干个箱子，将关键字为k的记录放入到第k个箱子中，然后再按序号将非空的箱子进行连接；

基数排序要求数字是有范围的，均由0-9这是个数字组成，则只需要设置十个箱子，相继按照个，十，百…进行排序。基数排序的实例如下所示，首先将所有数字以个位数为关键字扔到不同的箱子中，之后依次将各个箱子中的数字进行收集；第二次将所有数字以十位数为关键字扔到不同的箱子中，之后依次将各个箱子中的数字进行收集；第三次将所有数字以百位数为关键字扔到不同的箱子中，之后依次将各个箱子中的数字进行收集… …

基数排序的时间效率为： O(k∗(n+m))，其中k表示关键字的个数，  m表示关键字取值范围为 m m m个值。基数排序的空间效率为  O(n+m)，基数排序是一种稳定的排序方法。

7、各种排序方法的比较

按照平均时间性能来分，

时间复杂度为  O(nlogn)的方法有：快速排序，堆排序和归并排序，其中以快速排序为最好；

时间复杂度为  O(n2)的方法有：直接插入排序，冒泡排序和简单选择排序，其中以直接插入排序为最好，特别是对于关键字近似有序的记录序列尤为如此；

时间复杂度为  O(n)的方法只有基数排序。

简单选择排序，堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

按照平均空间性能来分，

所有简单的排序方法，如直接插入，冒泡排序，简单选择排序和堆排序的空间复杂度为 O(1)

快速排序基于递归的思想，需要用到栈的辅助空间，空间复杂度为 O(logn)

归并排序所需辅助空间较多，空间复杂度为  O(n)

基于线性表的基数排序所需辅助空间最多，为 O(n+m)

所有排序方法的比较如下表所示：