8-排序

评价指标:时间复杂度、空间复杂度、算法的稳定性。
分类:内部排序、外部排序

1.插入排序

顺序表
算法思想:将一个待排序的记录按照关键字的大小插入前面已经排好的子序列中，直到全部记录插入完成

  1. void InsertSort (int A[],int n){
  2.     int i,j,temp;
  3.     for (i=1;j<n;i++)
  4.         if （A[i]<A[i-1]){//A[i]小于前驱
  5.             temp=A[i];
  6.             for (j=i-1;j>=0 && A[j]>temp;--j)
  7.                 A[j+1]=A[j];
  8.             A[j+1]=temp;
  9.         }
  10. }

空间复杂度O(1);时间复杂度：O(n^2);算法稳定性：稳定

1.1优化一：折半插入排序

时间复杂度仍不变

  1. void InsertSorts(int A[],int n){
  2.     int i,j,low,high,mid;
  3.     for (i=2;i<=n;i++){
  4.         A[0]=A[i];
  5.         low=1;high=i-1;
  6.         while (low<=high){
  7.             mid=(low+high)/2;
  8.             if (A(mid)>A[0])high=mid-1;
  9.             else low=mid+1;
  10.         }//停止条件是low>high
  11.         for (j=i-1;j>=high+1;--j)
  12.             A[j+1]=A[j];
  13.         A[high+1]=A[0];
  14.     }
  15. }

1.2优化二：希尔排序

  1. void ShellSort(int A[],int n){
  2.     int d,i,j;
  3.      for (d=n/2;d>=1;d=d/2)//步长变化
  4.         for (i=d+1;i<=n,++i)
  5.             if (A[i]<A[i-d]){
  6.                 A[0]=A[i];
  7.                 for (j=i-d;j>0 && A[0]<A[j];j-=d)
  8.                     A[j+d]=A[j];
  9.                 A[j+d]=A[0];
  10.             }
  11. }

空间复杂度O(1);时间复杂度O(n^2)（最坏情况），稳定性：

2.交换排序

2.1冒泡排序

  1. void swap(int&a int &b){
  2.     int temp=a;
  3.     a=b;
  4.     b=temp;
  5. }//交换
  7. void BubbleSort(int A[],int n){
  8.     for (int i=0;i<n-1;i++){
  9.         bool flag=false;
  10.         for (int j=n-1;j>i;j--)
  11.             if A[j-1]>A[j]{
  12.                 swap(A[j-1],A[j])
  13.                 flag=true;
  14.             }
  15.         if(flag=false)return;
  16.     }
  17. }

空间复杂度O(1);时间复杂度O(n^2)

2.2快速排序

在待排序表中任意选取一个元素pivot作为基准，通过一趟排序将带排序表划分为具有特点的两部分，左侧<=pivot,右侧>=pivot

  1. int Partition(ElemType A[],int low,int high){
  2.     ElemType pivot=A[low];
  3.     while(low<high){
  4.         while(low<high && A[high]>=pivot)
  5.             high--;
  6.         A[low]=A[high];
  7.         while(low<high && A[low]<=pivot)
  8.             low++;
  9.         A[high]=A[low];
  10.     }
  11.     A[low]=pivot;
  12.     return low;
  13. }
  14. void QuickSort(ElemType A[],int low,int high){
  15.     if(low<high){
  16.         int pivotpos=Partition(A,low,high);
  17.         QuickSort(A,low,pivotpos-1);
  18.         QuickSort(A,pivotpos+1,high);
  19.     }
  20. }

平均空间复杂度：O(log2n);时间复杂度O(nlog2n)，不稳定，顺序存储(链式存储)
最坏：空间复杂度：O(n);时间复杂度O(n^2)

3.选择排序

每一趟在待排序元素中选取关键字最小的元素加入有序子序列

3.1简单选择排序

  1. void SelectSort(int A[],int n){
  2.     for (int i=0;i<n-1;i++){
  3.         int min=i;
  4.         for (int j=i+1;j<n;j++)
  5.             if (A[j]<A[min]) min=j;
  6.         if (min!=i) swap(A[i],A[min]);
  7.     }
  8. }

空间复杂度O(1),时间复杂度O(n^2),算法不稳定，线性表、链表皆可

3.2堆排序

堆：

  • 大根堆：完全二叉树中，根>=左、右
  • 小根堆：完全二叉树中，根<=左、右

3.2.1建立大根堆

  • 检查所有非终端结点(n/2向下取整计算)
  • 不满足时，将当前结点与其更大的孩子互换
  2. void BuildMaxHeap(int A[],int len){
  3.     for (int i=len/2;i>0;i--)
  4.         HeadAdjust(A,i,len);
  5. }//建立大根堆
  6. void HeadAdjust(int A[],int k,int len){
  7.     A[0]=A[k];
  8.     for (int i=2*k;i<=len;i*=2){
  9.         if (i<len && A[i]<A[i+1])
  10.             i++;
  11.         if (A[0]>=A[i]) break;
  12.         else{
  13.             A[k]=A[i];
  14.             k=i;
  15.         }
  16.     }
  17.     A[k]=A[0];
  18. }//将以k为根的子树调整为大根堆
  19. void HeapSort(int A[],int len){
  20.     BuildMaxHeap(A,len);
  21.     for (int i=len;i>1;i--){
  22.         swap(A[i],A[1]);
  23.         HeadAdjust(A,i,i-1)
  24.     }
  25. }//堆排序的完整逻辑

关键字对比次数不超过4n，建堆时间复杂度:O(n)，总体时间复杂度O(nlog2n),空间复杂度O(1),算法不稳定
大根堆得到的是递增序列，小根堆是递减序列

3.2.2 堆的插入与删除

插入，先放入表尾，然后按照大根堆/小根堆的性质进行互换
删除：用表尾元素进行代替被删除的元素，然后按照大根堆/小根堆的性质进行互换

4.归并排序

把两个或多个已经有序的序列合并成一个
进行m路归并时，没选择一个元素需要对比关键字m-1次
时间复杂度O(nlog2n),空间复杂度O(n),算法稳定

  1. int *B=(int*)malloc(n*sizeof(int));
  2. void Merge(int A[],int low,int mid,int high){
  3.     int i,j,k;
  4.     for (k=low;,k<=high;k++)
  5.         B[k]=A[k];//将A中元素复制到B中
  6.     for (i=low;j=mid+1;k=i;i<=mid && j<=high;k++){
  7.     if (B(i)<=B[j])
  8.         A[k]=B[i++];
  9.     else
  10.         A[k]=B[j++];
  11.     }
  12.     while(i<mid) A[k++]=B[i++];
  13.     while(j<=high) A[k++]=B[j++];
  14. }
  15. void MergeSort(int A[],int low,int high){
  16.     if (low<high){
  17.         int mid=(low+high)/2;
  18.         MergeSort(A,low,mid);
  19.         MergeSort(A,mid+1,high);
  20.         Merge(A,low,mid,high);
  21.     }
  22. }

5.基数排序

步骤：

  • 1)按个位递减排序；
  • 2)按十位递减排序，十位相同，个位递减；
  • 3)按照百位递减排序；
  • ……..

空间复杂度O(r)时间复杂度O(d(n+r))，算法稳定
擅长处理:

  • 关键字拆分为d组，且d较小；
  • 每组关键字取值范围不大，且r较小；
  • 数据元素格式n较大；

6.内部排序算法比较与应用

排序算法 时间复杂度 空间复杂度 稳定性
最好情况 平均情况 最坏情况
直接插入排序 O(n) O(n^2) O(n^2) O(1) 稳定
冒泡排序 O(n) O(n^2) O(n^2) O(1) 稳定
简单(直接)选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
希尔排序 O(1) 不稳定
快速排序 O(nlog2n) O(nlog2n) O(n^2) O(log2n) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 稳定
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) 稳定

6.1应用：

1)若n较小时(n<=50)采用直接插入排序或简单选择排序；n较大时采用快排、堆排、归并排序;
2)若n很大，记录关键字位数较少且可分解，采用基数排序；
3)当文件的n个关键字随机分布，至少需要O(nlog2n)；
4)若初始结构基本有序：采用直接插入或冒泡排序；
5)记录元素比较大，应避免大量移动排序算法，宜采用链式存储结构

7.外部排序

磁盘读写以块为单位，数据读入内存后才能被修改，使用 归并排序的方法，最少只需在内存中分配3块大小的缓冲区。
优化：多路归并
对r个初始归并段，做k路归并，则归并树可用k叉树表示，若树高为h，则归并趟数=h-1=log_k r （取上界）
K路平衡归并：

  • 最多只能有k个段归并为一个；
  • 每一趟归并中，若有M个归并段参与归并，则进过这一趟处理得到[m/k] (向上取整)个新的归并段

7.1败者树

败者树:最多对比关键字log2 k （向上取整）

7.2 置换-选择排序

构造更长的初始归并段

7.3 最佳归并树

类比参照哈夫曼树
对于k叉归并，若初始归并段数量无法构成严格k叉归并树，需要补充几个长度为0的“虚段”，再进行k叉哈夫曼树的构造。

  • 若(初始归并段数量-1)%(k-1)=0,说明刚好可以构成严格的k叉树，不需要额外添加；
  • 若(初始归并段数量-1)%(k-1)=u≠0,则需补充(k-1)-u个虚段；