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

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

一、排序的概念

排序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)$ 稳定

评论