十大排序算法之归并排序、快速排序、堆排序

cover

33238e2b7a5d476195dfc19af728bbaf

归并排序

介绍

归并排序 (Mergesort)(Merge-sort) 是利用归并的思想实现的排序方法,该算法采用经典的分治 (divideandconquer)(divide-and-conquer) 策略。

如图,具体来说,归并排序在排序的时候,会把一段数组拆分成不同的小数组(临界时只有一个元素),并在合并时排序。

img

复杂度/稳定性

时间复杂度

以上图代码为例,此时 n=8n = 8 ,可以看到,归并排序的分段是以下标二分的办法.

如下图,具体来看,对于分出的每两段数组合并的时候,每一层都会比较 nn 次,总共有 log2nlog_2n 层,时间复杂度为 O(nlog2n)O(nlog_2n)

image-20230814181555918

稳定性

每两段数组都是相邻的,相同的数合并时相对位置不会变化,因此它是稳定的。

代码实现

以下是c++实现,请参考注释理解:

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
40
41
42
const int N = 1e4+5;
int n, tmp[N], a[N];
void fsort(int l, int r){
//先进行递归分组
if(l >= r) return ;//临界情况,分得的数组最小为1
int mid = (l+r)/2; //取中间值
fsort(l, mid); //左边
fsort(mid+1, r); //右边

//回溯时进行合并,并排序,因为不能直接在原数组操作(),所以新定义tmp数组暂存合并结果
int i = l, j = mid+1, k = l;
while(i <= mid && j <= r){ //比较两个序列每个元素的大小并按次序存入暂存数组
if(a[i] <= a[j]){
tmp[k] = a[i];//左边区间的数小,放入
i++;
k++;
}
else{
tmp[k] = a[j];//右边区间的数小,放入
j++;
k++;
}
}
//还有可能其中一个数组有多出来的数,需要额外放置
while(i<=mid){
tmp[k]=a[i];
i++;
k++;
}
while(j<=r){
tmp[k]=a[j];
j++;
k++;
}
//把暂存区的数存入原数组
for(int i = l; i <= r; i++)
a[i] = tmp[i];
}
signed main(){
fsort(1, n);
return 0;
}

快速排序

介绍

快速排序 (Quicksort)(Quick-sort) 利用二分思想,完成数列的排序操作。

快速排序通过在待排序序列中选取基准值,再将数列调整为以基准值位置为界,一侧比基准值小,另一侧则比基准值大,然后递归两侧执行同样操作,即可完成排序。

如图1:

img

而具体到每次操作,可以参考下面这张图2:

3

复杂度/稳定性分析

时间复杂度

\qquad 最好情况下,每次划分可以均衡,类比归并排序,每一层排 nn 个数,共有 log2nlog_2n 层,时间复杂度为 O(nlog2n)O(nlog_2n)

\qquad 最坏情况下:基准值选取最值,每次划分会出现空序列,需要划分 nn 次,即共有 nn 层,时间复杂度为 O(n2)O(n^2)

同理,如果基准值失去随机性,快速排序的时间复杂度也会退化到 O(n2)O(n^2)

稳定性

快速排序每次按照基准值分类的时候,如上图,若两个元素数值相等,在 iijj 互换的过程中,相对位置会发生变化,所以不稳定。

代码实现

以下是c++实现,请参考注释理解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 1e4+5;
int n, a[N];
void quicksort(int l, int r){//参考上图2理解
if(l >= r) return ;//不要越界
int t = a[l]; //选基准值,如上图,选第一个位置的
int i = l, j = r;
while(i < j){ //i!=j时,进入循环
while( a[j] > t ) j--; //从后往前依次寻找比基准值小的
while( a[i] <= t && i<j) i++;//从前往后依次寻找比基准值大的
if(i < j) swap(a[i], a[j]);//满足i < j才能交换,不能相同位置互换
}
swap(a[l],a[i]); //把基准值放到合适的位置,此时i = j
quicksort(l,i-1);//继续向下分
quicksort(i+1,r);
}
signed main(){
quicksort(1, n);
return 0;
}

堆排序

堆排序 (Heapsort)(Heap-sort) 是借助堆这种数据结构完成的排序,思路类似于选择排序。

它和选择排序最大的不同是使用了树这一数据结构,把选择排序效率低下的一个个元素遍历的查找改为在树中查找。

前置芝士:堆

如图,堆是一种特殊的完全二叉树,分为大顶堆与小顶堆两种:

  1. 大顶堆: 完全二叉树中任一非叶子结点的值都大于等于其子结点的值。
  2. 小顶堆: 完全二叉树中任一非叶子结点的值都小于等于其子结点的值。

img

介绍

选择排序的原理还是很好懂的,所以跳过这一块(类比即可),着重讲如何用堆查找元素。

如果我们需要数组元素单调递减,需要最终形成一个大顶堆:从下往上倒序遍历非叶子结点(没有儿子节点的节点),通过交换方式依次调整父子结点顺序,直至符合大顶堆的规则。

举例:有如图的一个数组,需要这样操作便可得到一个有序的数组。

image-20230818112757861

复杂度/稳定性分析

时间复杂度

和选择排序类似,总共需要操作 nn 个数,不同的是,选择排序操作一个数需要 nn ,而堆排序查找一个数只需要 log2nlog_2n ,所以堆排序的时间复杂度是 O(nlog2n)O(nlog_2n)

稳定性

堆排序和选择排序类似,排序过程中相同元素位置发生改变,不稳定。

代码实现

以下是c++实现,请参考注释理解:

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
const int N = 1e4+5;
int m, a[N]
//堆排序
//堆部分
void adjust(int i, int parent)
{
int child = parent * 2;//先判断儿子
// 保证判断的范围不超过i
if(child + 1 <= i && a[child] < a[child + 1]){
child++;//选择两个儿子中较大的那个往上传递(维护大顶堆)
}
if(a[child] > a[parent]){
swap(a[child], a[parent]);//如果儿子比较大,就往上交换
if(child <= i / 2){//不超过i的父节点
adjust(i, child);//如果当前节点更新,那么当前节点的子节点也需要更新
}
}
}
//主体排序部分
void heapSort(){
for(int i = n; i > 1; i--){//从右侧往左侧维护,注意不能从左往右,因为不能保证其子节点已经被维护过
for(int j = i / 2; j >= 1; j--){ //从i节点的父节点开始维护
adjust(i, j); //以j号节点往根节点调整,传递的i辅助判断是否越界
}
swap(a[1], a[i]);//此时树根是下标[1, i]范围内最大的数,和当前位置交换(参考选择排序)
}
}
signed main(){
heapSort();
return 0;
}

本文作者:Genkaim

本文链接: https://www.genkaim.top/posts/954ceb85