抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

🔑数据结构_第八章：排序

编程

发布于：2023年9月16日

🔑数据结构_第八章：排序

一、排序的概念

排序Sort，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

  • 输入：$n$个记录$R_1,R_2,…，R_n$，对应关键字为$k_1,k_2,…,k_n$。
  • 输出：输出序列的一个重排$R_1^{‘},R_2^{‘},…,R_n^{‘}$，使得有$K_1^{‘} \le K_2^{‘} \le … \le K_n^{‘}$(也可以递减)。

排序算法的评价指标：

  • 时间复杂度

  • 空间复杂度

  • 稳定性：

    若待排序表中有两个元素$R_i$和$R_j$，其对应的关键字相等——即$key_i= key_j$，且在排序前$R_i$在$R_j$的前面，若使用某一排序算法排序后，$R_i$仍然在$R_j$的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

    • 问：稳定的排序算法一定要比不稳定的好吗？

      答：不一定！看实际业务需求！

排序算法的分类：

  • 内部排序：数据都在内存中，主要关注时间复杂度和空间复杂度。
  • 外部排序：数据太多，无法全部放入内存，不仅要关注时间空间复杂度，还要关注如何使读写磁盘的次数更少！

数据结构算法可视化网站：Data Structure Visualizations

二、插入排序

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

（一）直接插入排序

10a6c6bd2edfb0c71651d843a8cd4e7a.gif 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//直接插入排序——王道咸鱼
//传入数组A[i]和数组长度n
void InsertSort(int A[], int n){
    int i, j, temp;
    for(i=1; i<n; i++){		//将各元素插入已排好序的序列中
        if(A[i] < A[i-1]){		//若A[i]关键字小于前驱
            temp=A[i];		//用temp暂存A[i]
            for(j=i-1; j>=0 && A[j]>temp; i--)		//检查所有前面已排好序的元素
                A[j+1]=A[j];		//所有大于temp的元素都向后挪
            A[j+1]=tepm;		//复制到插入位置
        }
    }
}

//直接插入排序——王道教材
void InsertSort(int A[], int n){
    int i, j;
    for(i=2; i<=n; i++){
        if(A[i]<A[i-1]){
            A[0]=A[i];
            for(j=i-1; A[0]<A[j]; j--)
                A[j+1]=A[j];
            A[j+1]=A[0];
        }
    }
}

性能评估：

  • 空间复杂度：$O(1)$；

  • 时间复杂度：$O(n^2)$：

    主要来自于对比关键字、移动元素，若有$n$个元素，则需要$n-1$躺处理。

    最好情况：$O(n)$；

    最坏：原本为逆序——$O(n^2)$。

  • 稳定性：稳定。

（二）折半插入排序：

因为已排好序的部分肯定是有序的，所以可以将查找插入位置的部分换成折半查找的方式。

当low>high 时折半查找停止，应将[low, high]区间内的元素全部右移，再将temp复制到low所指位置。

而如果要保持算法稳定性，当A[mid]=temp时，应继续在mid所指位置右边寻找插入位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//折半插入排序
void InsertSort(int A[], int n){
    int i, j, low, high, mid;
    for(i=2; i<=n; i++){			//依次将A[2]~A[n]插入前面的已排序序列
        A[0]=A[i];					//将A[i]暂存到A[0]
        low=1; high=i-1;			//设置折半查找的范围
        while(low<=high){			//折半查找（默认递增有序）
            mid=(low+high)/2;		//取中间点
            if(A[mid]>A[0])			//查找左半子表
                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(n2)数量级，整体看起来时间复杂度仍然是$O(n^2)$。

image7c9729494c670563.png

（三）希尔排序ShellSort

1、算法逻辑

希尔排序：先将待排序表分割成若干形如$L[i,i+ d,i+ 2d,..,i+ kd$的“特殊”子表，对各个子表分别进行直接插入排序。

缩小增量$d$，重复上述过程，直到$d=1$为止。

image617bf51311aeca0f.png imaged23096e2b8b38e2d.png

演示1：

076c6e5bd8afd185a54b19d2e068ef66.gif

演示2：

02e22a618aab8dda49.gif

2、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(int A[], int n){
    int i, j, d;
    //A[0]只是暂存单元不是哨兵，当j<=0时，插入位置已到
    for(d=n/2; d>=1; d=d/2){		//步长变化
        for(i=d+1; i<=n; i++){
            if(A[i]<A[i-d]){		//需将A[i]插入有序增量子表
				A[0]=A[i];
            	for(j=i-d; j>0 && A[0]<A[j]; j-=d)
                	A[j+d]=A[j];	//记录后移，查找插入的位置
				A[j+d]=A[0];		//插入
            }
        }
    }
}

3、性能分析

  • 空间复杂度：$O(1)$；

  • 时间复杂度：

    目前无法用数学手段证明确切的时间复杂度。

    最坏时间复杂度为$O(n^2)$，当$n$在某个范围内时，可达$O(n^{1.3})$。

  • 稳定性：

    不稳定！

  • 适用性：

    只适用于顺序表，不适用于链表。

总结：

image8609f4815286ae0e.png

三、冒泡排序和快排序

（一）冒泡排序

41d4ca3e0253b00c56c657f2e7c2f87b.gif

1、概念

从后往前(或从前往后)两两比较相邻元素的值，若为逆序——即$A[i-1]>A[i]$——则交换它们，直到序列比较完。

称这样过程为“一趟”冒泡排序。

2、代码

王道咸鱼学长：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//交换函数
void swap(int &a, int &b){
    int temp=a;
    a=b;
    b=temp;
}

//冒泡排序——从后往前升序排序
void BubbleSort(int A[], int n){
    for(int i=0; i<n-1; i++){
        bool flag=false;			//表示本躺冒泡是否发生交换的标志
        for(int j=n-1; j>i; j--){	//一趟冒泡过程
            //若为逆序则交换
        	if(A[j-1]>A[j]){
        	    swap(A[j-1], A[j]);
        	    flag=true;
        	}
        }
        if(flag==false)		//本躺遍历没有发生交换，说明表已经有序
            return;
    }
}

我自己手撸（从前往后遍历升序排序）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//交换两个数
void swap(int &a, int &b){
    int temp;
    temp=a;
    a=b;
    b=temp;
}

//冒泡排序——从前往后遍历升序排序
void BubbleSort(int A[], int n){
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            if(A[j]<A[i])
                swap(A[j], A[i]);
        }
    }
}

int main(){
    int A[10];
    srand((unsigned int)time(0));
    printf("这是A[]的值：\n");
    for(int i=0; i<10; i++){
        A[i]=rand();
        printf("第%d次：%d\n", i+1, A[i]);
        //int a = rand();
        //printf("%d\n", a);
    }
    BubbleSort(A, 10);
    printf("\n冒泡排序结果：\n");
    for(int i=0; i<10; i++){
        printf("第%d个数：%d\n", i+1, A[i]);
    }
    return 0;
}

运行结果：

image5fe84c6809495a45.png

3、性能评估

  • 稳定性：稳定

  • 时间复杂度：

    • 最好（有序）：$O(n)$；
    • 最坏（倒序）：$O(n^2)$；
    • 平均：$O(n^2)$.

  • 空间复杂度：$O(1)$.

  • 可以应用于链表！

  • 每次执行交换swap()需要执行三次交换！

  • 需注意每次循环开始前检查是否已排好序，如果是直接结束！（上文中王道11、19、20行代码）

（二）快速排序

5d8bac0c113d49e4eaeb88acbfbec395.gif

1、算法逻辑

算法思想：

在待排序表$L[1…n]$中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分$L[1…k-1]$和$L[k+1…n]$，使得$L[1…k-1]$中的所有元素小于pivot，$L[k+1…n]$中的所有元素大于等于pivot，则pivot放在了其最终位置$L(k)$上，这个过程称为一次“划分”。

然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

2、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//对表进行划分
/*
* 该方法用第一个元素的值pivot作为枢纽将待排序序列划分成左右两个子表：
* 左子表的全部元素都小于pivot，右子表的全部元素都大于pivot；
* 然后对其左右子表再各自递归进行该操作，直至每个子表中只含有一个元素时，整个序列就排好序了。
*/
int Partition(int A[], int low, int high){
    int pivot=A[low];		//第一个元素作为枢纽
    //用low、high搜索枢纽的最终位置，low向右移，high向左移，直至二者重合
    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;			//low、high重合，枢纽元素存放到最终位置
    return low;				//返回存放枢纽的最终位置
}

//快速排序
void QuickSort(int A[], int low, int high){
    if(low<high){		//跳出递归的条件——当递归最内层的子表中只剩一个元素（即low=high）时说明整个序列排序完成
        int pivotpos=Partition(A,low,high);		//划分
        QuickSort(A,low,pivotpos-1);	//划分左子表
        QuickSort(A,pivotpos+1,high);	//划分右子表
    }
}

3、性能评估

可以将其看作n个结点的二叉树：最小高度为$[log2n]+1$，最大高度为$n$。

imagea64f6f795935480a.png

  • 时间复杂度：

    受递归层数影响：

    • 最好：$O(nlog_2n)$（每次选的枢轴元素都能将序列划分成均匀的两部分）。
    • 最坏：$O(n^2)$（若序列原本就有序或逆序，则时空复杂度最高（可优化，尽量选择可以把数据中分的枢轴元素））。
    • ❗平均时间复杂度：$O(nlog_2n)$（实际情况中更接近最好情况）。

  • 空间复杂度：

    也受递归层数影响：

    • 最好：$O(log_2n)$.
    • 最坏：$O(n)$.

  • 稳定性：不稳定！

快速排序是所有内部排序算法中平均性能最优的排序算法！

四、直接选择排序和堆排序

（一）简单选择排序

bf08bdd9b3b37d4adbc9822dc7438f10.gif

1、算法思想

选择排序：每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列。

2、代码实现

imagef4d9fa8c16d354cd.png 
1
2
3
4
5
6
7
8
9
10
11
12
//快速排序
void SelectSort(int A[], int n){
    for(int i=0; i<n-1; i++){		//一共进行n-1躺
        int min=A[i];		//记录最小元素值
        for(int j=i+1; j<n; j++){	//在[i+1,n-1]范围内寻找最小值（n为元素个数而不是数组下标）
            if(A[j]<min)
                min=A[j];			//更新最小元素值
        }
        if(A[i]!=min)		//若第一个元素不是最小值则交换位置，否则不做处理
            swap(A[i], min);
    }
}

3、性能评估

  • 时间复杂度：$O(n^2)$.

    无论有序、逆序还是乱序都要进行n-1躺处理。

  • 空间复杂度：$O(1)$.

  • 稳定性：不稳定。

  • 适用性：顺序表和链表都适用。

（二）堆排序

1、相关概念与算法思想

（1）数据结构——“堆”

imaged8d8e43e5b735f3f.png imageb910853a5f411cf7.png image8626c7e830261fa4.png
  • 大根堆：根结点$\ge$左右子树的完全二叉树；
  • 小根堆：根结点$\le$左右子树的完全二叉树；

（2）算法思想

*注：以下是升序排序为例：

  1. 先将待排序序列改造成大根堆，这样子对应完全二叉树（以下称为“树”）的根结点就是整个序列中最大的那一个；
  2. 然后将根结点和最后一个叶子结点交换，此时整个序列中最后一个元素就是排序好了的；
  3. 再把除去最后一个已排好序的结点的子树重新改造为大根堆；
  4. 循环2、3步骤，直至只剩最后一个根节点未排序，那么此时整个序列已经排好序了！

2、代码实现

imagefac8b7cee10f901b.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0]=A[k];							//A[0]暂存子树的根结点
    for(int i=2*k; i<len; i*=2){		//沿key较大的子结点向下筛选
        if(i<len && A[i]<A[i-1]){
            i++;						//取key较大子结点的下标
        }
        if(A[0]>=A[i])
            break;						//筛选结束
        else{
            A[k]=A[i];					//将A[i]调整到双亲结点上
            k=1;						//修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];							//被筛选结点的值放入最终位置
}

//建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)			//从后往前调整所有非终端节点
        HeadAdjust(A,i,len);
}

//堆排序的完整逻辑
void HeapSort(int A[], int len){
    BuildMaxHeap(A,len);				//初始建堆
    for(int i=len; i>1; i--){			//n-1躺的交换和建堆过程
        swap(A[i], A[1]);				//交换堆顶元素和堆底元素
        HeadAdjust(A, 1, i-1);			//把剩余的待排序元素整理成堆
    }
}

3、性能分析

  • 时间复杂度：$O(n\log_2n)$.
  • 空间复杂度：$O(1)$.
  • 稳定性：不稳定。

4、堆的插入和删除

❗是在堆里面不是在排序序列里面❗

（1）插入

  1. 先将新的元素放到表尾；
  2. 再根据实际情况将元素不断“上升”，直到无法继续上升为止。

（2）删除

  1. 将目标元素删除，用表尾元素代替删除元素；
  2. 再根据实际情况将元素不断“下坠”，直到无法继续下坠为止。
image02823fc8cd41be7a.png

五、归并排序

（一）算法思想

e69936e1f6ea4197748a676d2df06209.gif image9cd539d294d5c5c1.png

（二）代码实现

imageeff23fe1c243fe28.png image73e5cd043e2c0b77.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int *B=(int *)malloc(n*sizeof(int));	//辅助数组B

//A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(int A[], int low, int mid, int high){
    int i, j, k;
    for(k=low; k<=high; k++)
        B[k]=A[k];						//将A中所有元素复制到B中
    for(i=low, j=mid+1, k=1; i<mid&&j<=high; k++){
        if(B[i]<=B[j])
            A[k]=B[i++];				//将较小值复制到A中
        else
            A[k]=B[j++];
    }
    while(i<=mid)	A[k++]=B[i++];
    while(j<=high)	A[k++]=B[j++];
}

void MergeSort(int A[], int low, int high){
    if(low<high){
        int mid=(low+high)/2;		//从中间划分
        MergeSort(A,low,mid);		//对左半部分归并排序
        MergeSort(A,mid+1,high);	//对右半部分归并排序
        Merge(A,low,mid,high);		//归并
    }
}

（三）性能评估

  • 时间复杂度：$O(nlog_2n)$.
  • 空间复杂度：$O(n)$.
  • 稳定性：稳定。

总结：

image5a6ed77d866a5619.png

六、各种排序算法性能分析总结

算法 时间复杂度 空间复杂度 稳定性
直接插入排序InsertSort $O(n^2)$ $O(1)$ 稳定
折半插入排序 $O(n^2)$ $O(1)$ 稳定
希尔排序ShellSort 最坏$O(n^2)$，当$n$在某个范围内时可达$O(n^{1.3})$ $O(1)$ 不稳定
冒泡排序BubbleSort $O(n^2)$ $O(1)$ 稳定
快速排序QuickSort $O(nlog_2n)$ 最好$O(log_2n)$，最坏$O(n)$ 不稳定
（简单）选择排序SelectSort $O(n^2)$ $O(1)$ 不稳定
堆排序HeapSort $O(nlog_2n)$ $O(1)$ 不稳定
归并排序MergeSort $O(nlog_2n)$ $O(n)$ 稳定

更新于：2024年5月13日

数据结构

算法

评论