考研笔记 | 数据结构 §8.排序

  • 英语:

  1. 排序: 重新排序表中元素,使其满足按关键字递增或递减的过程。
  2. 方法:
    • 内部排序:排序期间全放在内存中的排序;
    • 外部排序:排序期间元素无法同时在内存,在排序期间不断在内外存间移动的排序。

§1 插入排序

  1. 直接插入排序:“将待排序记录插入有序序列中,重复$n-1$次”
    直接插入排序示意图
  2. 算法空间效率$O(1)$,时间$O(n)$/$\sum^n_i=2(i+1)$,平均$\frac{n^2}{4}$/$O(n^2)$,算法稳定。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
        void InsertSort(ElenType A[], int n){
    int i,j; // 适用于顺序存储和链式存储的线性表
    for(i=2;i<=n;i++){
    if(A[i],key<A[i-1].key){
    A[0]=A[j];
    for(j=i-1;A[0].key<A[j].key;--j)
    A[j+1]=A[j];
    A[j+1]=A[0];
    }
    }
    }
  3. 折半插入排序:查找有序子表由折半法实现,其他不变。

  4. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void InsertSort(ElemType A[],int n){
    int i,j,low,high,mid;
    for(i=2;j<=n;i++){
    A[0]=A[i];
    low=1;high=i-1;
    while(low<=high){
    mid=(low+high)/2;
    if(A[mid].key>A[0].key)
    high=mid-1;
    else
    low=mid+1;
    }
    for(j=i-1;j>high+1;--j){
    A[j+1]=A[j];
    A[high+1]=A[0];
    }
    }
    }// 时间复杂度 O(n^2),算法稳定
  5. 希尔排序(缩小增量排序):将序列分为若干个子块,分别进行直接插入排序,直至对整个序列进行直接插入排序。

  6. 步骤:
    1. 分成子序列(增量dk);
    2. 对子序列排序
    3. 缩小增量,重复以上步骤
    4. 增量序列最后一个增量一定是1,如(9,5,3,2,1)或(3,2,1)
  7. 例子:对于(52,49,80,36,14,58,61)
    希尔排序示意图
    时间复杂度$O(n)^{\frac {3}{2}}$,算法不稳定
  8. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void ShellSort(ElemType A[],int n){//前后记录位置增量是dk,不是1
    for(dk=n/2;dk>=1;dk=dk/2){
    for(i=dk+1;dk>=1;dk=dk/2){
    if(A[i].key<A[i-dk].key){
    A[0]=A[i];
    for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk){
    A[j+dk]=A[j]//记录后移
    A[j+dk]=A[0];
    }
    }
    }
    }
    }

    空间效率$O(l)$,时间效率$O(n^2)$,不稳定,适用于线性表顺序存储。

§2 交换排序

  1. 冒泡排序:“依次比较相邻元素,‘逆序’则交换,重复n-1次”
  2. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void BubbleSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){
    flag=false;//表示交换的标志
    for(j=n-1;j>1;j--){
    if(A[j-1].key>A[j].key){
    swap(A[j-1],A[j]);//交换
    flag=true;
    }
    }
    if(flag==false)
    return;//未交换,说明有序
    }
    }//没糖排序都有一个元素放到最终位置

    空间复杂度$O(1)$,时间复杂度:最坏$O(n^2)$,最好$O(n)$,平均$O(n^2)$,算法稳定。

  3. 快速排序:一趟排序把记录分为两份,一份关键字比另一份小。
  4. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int Dived(ElemType A[],int low,int high){
    ElemType pivot=A[low];
    while(low<high){
    while(low<high&&A[high]>=pivot){
    --high;
    A[low]=A[high];
    }
    while(low<high&&A[low]<=pivot){
    ++low;
    A[high]=A[low];
    }
    A[low]=pivot;
    return low;
    }
    void QuickSort(ElemType A[],int low,int high){
    if(low<high){//跳出条件
    int pivot=Dived(A,low,high);
    QuickSort(A,low,pivot-1);
    QuickSort(A,pivot+1,high);
    }
    }
    }

    空间复杂度:最好$\lceil \log_2{(n+1)} \rceil$,最坏$O(n)$,平均$O(log_2n)$
    时间复杂度:最好,平均$O(n\log n)$,最坏$O(n^2)$
    算法不稳定。

  5. 快速排序,是内部排序算法中平均性能最优的算法。
  6. 简单选择排序:“在待排序记录中选取最小的,交换到合适位置,重复n-1次。”
  7. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void SelectSort(ElemType A[],int n){//伪代码
    for(i=0;i<n-1;j++){
    min=j;
    for(j=i+1;j<n;j++){
    if(A[j]<A[min])
    min=j;
    }if(min!=i)
    swap(A[i],A[min]);//交换
    }
    }

    空间复杂度:$O(1)$
    时间复杂度:最好$0$,最坏和平均情况$O(n^2)$,算法不稳定

§3 堆排序

  1. 树形选择排序,将$L[1,\dots,n]$看成一棵完全二叉树的顺序存储结构,且
    1. $L(i) \leq L(2i)$且$L(i) \leq L(2i+1)$
    2. $L(i) \geq L(2i)$且$L(i) \geq L(2i+1)$
      满足1为小顶堆,满足2为大顶堆。
  2. 建堆(大顶堆):对$\lfloor \frac{n}{2} \rfloor$个结点为根的子树筛选(最后一个结点父亲),若根结点关键字小于左右子女关键字较大者,则交换。重复步骤。
  3. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void BuildMaxHeap(ElemType A[],int len){//建大根堆
    for(int i=len/2;i>0;i--){
    AdjustDown(A,i,len);
    }
    }
    void AdjustDown(ElemType A[],int k,int len){
    A[0]=A[k];
    for(i=2*k;i<=len;i*=2){
    if(i<len&&A[i]<A[i+1])
    i++;//取key较大子结点向下取下标
    if(A[0]>=A[i])
    break;
    else{
    A[k]=A[i];//将A[i]调到双亲上
    k=i;//修改k值
    }
    }
    A[k]=A[0];
    }//调整时间与树高有关,为O(n)
  4. 1
    2
    3
    4
    5
    6
    7
    void HeapSort(ElemType A[],int len){
    BuildMaxHeap(A,len);//初始建堆
    for(i=len;i>1;i--){//n-1趟交换与建堆
    Swap(A[i],A[1]);
    AdjustDown(A,1,i-1);//输出堆顶,调整
    }
    }

    空间复杂度:$O(1)$,建堆$t=O(n)$
    时间复杂度:$O(n\log_2n)$,算法不稳定

  5. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void AdjustUp(ElemType A[],int k){//建立大顶堆,上调法
    A[0]=A[k];
    int i=k/2;
    while(i>0&&A[i]<A[0]){
    A[k]=A[i];
    k=i;
    i=k/2;//双字下调,向上比较
    }
    A[k]=A[0];
    }

§4 归并排序

  1. 归并排序:两个及以上有序表组合为一个有序表
  2. 二路归并排序:

    二路归并排序举例示意图

  3. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    ElemType *B=(ElemType *) malloc((n+1)* sizeof (ElemType));//辅助数组
    void Merge(ElemType A[],int low,int mid,int high){
    for(int k=low;k<=high;k++)
    B[k]=A[k];//将A中元素复制到B
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
    if(B[i]<=B[j])
    A[k]=B[k+1];//比较B中两段元素,将较小值赋予A中
    else
    A[k]=B[j++];
    }
    while(i<=mid) //两个while仅一个会执行
    A[k+1]==B[i++];//若一表未检测完,复制
    while(j<=high)
    A[k++]=B[j++];//若二表未检测完,复制
    }
  4. 1
    2
    3
    4
    5
    6
    7
    8
    void MergeSoft(ElemType A[],int low,int high){
    if(low<high){
    int mid=(low+high)/2;//从中间划分两个子序列
    MergeSoft(A,low,mid);
    MergeSoft(A,mid+1,high);
    Merge(A,low,mid,high);//归并
    }
    }

    空间复杂度:$O(n)$,时间复杂度$O(n
    log_2n)$,算法稳定

§5 基数排序

  1. 基数排序:借“分配”与“收集”两种操作对关键字进行排序。
  2. 分类:最高位优先(MSD),最低位优先(LSD)
  3. 方法:按个位分配到一个链表,并按个位收集,依次……
    基数排序示意图
  4. 空间效率:$O(r)$,时间效率:$O(d(n+r)$,其中n为排序,r为收集,算法稳定。

§6 小结

  1. 内部排序算法比较
排序方法时间复杂度空间稳定特点
最好平均最坏复杂度与否
直接插入排序$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(n^{\frac {3}{2}})$$O(n^{\frac {3}{2}})$$O(n^{\frac {3}{2}})$$O(1)$
快速排序$O(n\log_2 n)$$O(n\log_2 n)$$O(n^2)$$O(\log_2 n)$平均时间性能最好
堆排序$O(n\log_2 n)$$O(n\log_2 n)$$O(n\log_2 n)$$O(1)$辅助空间少
2-路归并排序$O(n\log_2 n)$$O(n\log_2 n)$$O(n\log_2 n)$$O(n)$算法稳定
基数排序$O(d(n+r))$$O(d(n+r))$$O(d(n+r))$$O(r)$适合个数多关键字少的情况
  1. 排序方法的选择
    1. 若n较小($n\leq 50$),可用直插式简单选则排序,效果最好;
    2. 若基本有序,宜直插式冒泡;
    3. n较大,应采用$O(n\log_2n)$方法:快排,堆排或归并;
    4. 当文件n个关键字随机时,任何借助“比较”的算法,至少$O(n\log_2n)$;
    5. 若n很大,且关键字可分解,用基数排序;
    6. 当记录本身信息量大,为避免大量移动,可用链表存储。
  2. 小结
    1. 排序稳定,且关键字为实数(不可分解,double,float类),选择直接插入排序;
      • 稳定的排序方法:冒泡排序、直接插入排序、归并排序、基数排序;
        • $O(n\log_2n)$ :堆排序、归并排序、快速排序;
        • $O(n^2)$:直接插入排序、冒泡、简单选择排序;
        • 可达$O(n)$:直接插入排序、冒泡排序;
    2. 辅助空间:快速排序$O(\log2_n)$>归并排序$O(n)$>直接插入排序、冒泡排序、简单选择排序、希尔排序、堆排序$O(1)$;
    3. 排序趟数与序列原始状态无关:简单选择排序、直接插入排序、基数排序;
    4. 每趟排序结束至少确定一个元素位置:简单选择排序、快速排序、堆排序;
    5. 一般情况下,查找效率最低的是:堆排序。
-------文章到此结束  感谢您的阅读-------