💓博主CSDN主页:杭电码农-NEO💓
 
⏩专栏分类:八大排序专栏⏪
 
🚚代码仓库:NEO的学习日记🚚
 
🌹关注我🫵带你学习排序知识
  🔝🔝

---

---

1. 前言

比较八大排序不能直接将
这八个排序放在一起讨论
我们根据大致效率将它们分为两组:
(每个排序的详情链接在后面)

1. 第一组

• 插入排序 详情
• 选择排序 详情
• 冒泡排序 (略)

2. 第二组

• 堆排序 详情
• 希尔排序 详情
• 快速排序 详情
• 归并排序 详情

各大排序的进阶版本被放在了专栏:
    八大排序专栏

本篇文章将从稳定性和效率两个方面
来分析这两组排序

---

2. 什么是排序算法的稳定性?

官方话语是这样的:

排序序列中,有多个具有相同关键字的记录经过排序,记录对应的相对次序保持不变,这就是排序的稳定性。

举个例子,定义一个无序数组:

int a[]={5(i),3,6,4,5(j),2,8};
1

数组中有两个5
把第一个5记为 i
第二个5记为 j
当我们用任意算法排好序后

int a[]={2,3,4,5,5,6,8};//排好序后的数组
1

若 i 还在 j 前面,则这个算法是稳定的

int a[]={2,3,4,i,j,6,8};
1

若 i 在 j 后面,则算法不稳定

int a[]={2,3,4,j,i,6,8};
1

---

3. 各大排序稳定性分析

想要搞清楚排序是否稳定
就要明白内部的实现思路!

---

3.1 插入和希尔排序的分析

1. 插入排序:

插入排序是从数组中第一个元素开始
一一和它后面的元素做比较
并且一个元素向前挪动停下来的条件是:
当前元素的值大于等于正在挪动的元素

结论: 是稳定的

2. 希尔排序:

虽然希尔排序是对插入排序的优化
但是希尔排序多了一个分组预排序
当相同的数组被分到同一组时
它们的顺序不会变化
但是当相同的数据分到不同组时
排好序后的顺序就有可能改变!

结论: 不是稳定的

---

3.2 选择,堆排序的分析

1. 选择排序:

选择排序明显是不稳定的
当前循环选出的最大值是
这个值第一次出现的位置
将它放在数组最后,第二层循环
寻找次大值时若和刚刚的值相同
这个次打值就到倒数第二个位置了

结论: 不稳定的

2. 堆排序:

堆排序和选择排序类似
我们直接举个向下调整的例子:

蓝色的5从第一个位置跑到最后一个了

结论: 不稳定的

---

3.3 冒泡,快速排序的分析

1. 冒泡排序:

冒泡排序是挨个儿比较
挨个儿交换.所以不会将相同的值
交换到不同的位置

结论: 稳定的

2. 快速排序

快速排序比较特殊.
当基准值key和L,R指针相遇的点
对应的值相同时,会改变位置!
画图说明:

5的前后顺序发生了变化

结论: 不稳定的

---

3.4 归并排序分析

归并排序可以稳定也可以不稳定
当左右子数组中出现相同值时
如果先将左子数组的数据入数组
那么归并排序就是稳定的
如果先将右子数组的数据入数组
那么归并排序就是不稳定的

所以我们写归并排序时
数据相同时尽量先下左边

结论: 稳定的!

---

4. 各大算法效率比较

现实生活中处理的信息量往往非常大
这里我们随机生成五百万个数排序
试一试每一个排序算法要花多少毫秒?

注:clock是记录程序
走到当前这一行运行的时长
两个clock相减就是中间程序运行的时间

//测试性能
void TestOP()
{
srand(time(0));
const int N = 5000000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);

for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
}

int begin1 = clock();
InsertSort(a2, N);
int end1 = clock();

int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();

int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();

int begin4 = clock();
HeapSort(a2, N);
int end4 = clock();

int begin5 = clock();
QuickSort(a2, 0, N - 1);
QuickSort(a2, 0, N - 1);
int end5 = clock();

int begin6 = clock();
MergeSort(a2, N);
int end6 = clock();

printf("InsertSort:%d ms\n", end1 - begin1);
printf("ShellSort:%d ms\n", end2 - begin2);
printf("SelectSort:%d ms\n", end3 - begin3);
printf("HeapSort:%d ms\n", end4 - begin4);
printf("QuickSort:%d ms\n", end5 - begin5);
printf("MergeSort:%d ms\n", end6 - begin6);

free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

对于五百万个数据来说
插入,选择,冒泡排序运行的时间会很长
所以我们这里直接比较第二组排序:

五百万个数据:

一百万个数据:

每个排序效率都不错
快排与归并格外的好!

---

5. 总结与代码分享

八大排序整体完结!
下面分享一个知识表格大全:

我将C语言实现八大排序
所有代码汇总分享给大家:

gitee代码仓库

八大排序所有内容结束!

🔎 下期预告:C嘎嘎初阶 🔍