-
排序算法基础篇
前言
排序算法是算法的重要分支，也是算法初学者必须要掌握的。目前有十大经典排序算法，分别为冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序，堆排序，计数排序，桶排序，基数排序。笔者写的此类排序算法文章共计三篇，三篇文章将根据排序算法的时间复杂度分为上篇（ O(n^2) ），中篇（ O(nlogn) ），下篇（ O(n+k) ），文章将详细描述各个排序算法的思想及过程，并提供代码和一些优化思路，希望对大家有一些帮助
因为某些排序算法在用代码实现时会涉及到数据结构的相关知识，但排序思想都是可以理解的，不会相关数据结构的可暂缓手动实现
需要注意的是文章里都是默认将数据排成升序，因此一些描述过程是针对升序而言的
目录
冒泡排序
冒泡排序的思想
冒泡排序一般是编程初学者接触的第一个排序算法，因为其思想简单明了，实现的代码也很好编写，很容易被接受。冒泡排序的思想本质上就是两两交换，把数组中最大的元素交换到末尾，通过多次交换之后，最终形成有序数字，下面是冒泡排序的动图，接下来我们举例一一说明
上面的动图应该能让大家简单理解冒泡排序的思想，接下来我们用一个例子逐步分析，将数组4，1，7，5，6排成升序，从下标为0的位置开始，与它的后一位空间内的值进行对比
下标为0的空间所存的值是4，它的后一位的空间所存的值为1，将其进行对比，4大于1，交换两空间内的值，如下图
接着从下标为1的位置开始，与它的后一位的空间所存的值进行对比，下标为1的空间所存的值是4，它的后一位的空间所存的值为7，将其进行对比，4小于7，不进行交换，如下图
继续从下标为2的位置开始，下标为2的空间所存的值是7，它的后一位的空间所存的值为5，将其进行对比，7大于5，交换，如下图
再继续从下标为3的位置开始，下标为3的空间所存的值是7，它的后一位的空间所存的值为6，将其进行对比，7大于6，交换，如下图
至此第一趟冒泡排序就结束了，我们使用的这个例子赶巧了，就经过一趟冒泡排序就把它整有序了，在该例子中，我们可以发现，最大的那个数字，即数字7，经过一趟冒泡排序的交换一定会被交换到属于它的位置，也就是末尾，这个数字就默认被排好了，那我们在进行下一趟冒泡排序时就不需要再管这个数字。要是最坏的情况，一趟冒泡排序就只能排好最大的那个数字，也就是说n个数字需要排n-1趟，而每一趟几乎要遍历整个数组，这要消耗很多资源，尤其是要排的数字量比较大时，冒泡排序很难起到大作用
冒泡排序的代码实现
伪代码
for i := 1 to n-1
for j := 1 to n-1-i
if A[j] < A[j+1]
exchange A[j] with A[j+1]
伪代码阅读规则：
伪代码的下标是从1开始的，:=表示赋值，{ /}表示指令序列，类似于C语言的{ }，to表示控制该循环的计数是增加的，downto表示控制该循环的计数是减少的（默认to与downto的控制循环计数变化值为1，当控制循环计数的变化值不为1时可使用by来表示变化值）
c/c++的具体实现代码
- //交换函数
- void swap(DataType* p1, DataType* p2)
- {
- DataType tmp = *p1;
- *p1 = *p2;
- *p2 = tmp;
- }
- //冒泡排序实现函数
- void BubbleSort(DataType* arr, int size)
- {
- for (int i = 0; i < size; i++)
- {
- for (int j = 0; j < size - i - 1; j++)
- {
- if (arr[j] < arr[j + 1])
- {
- swap(&arr[j], &arr[j + 1]);
- flag = 1;
- }
- }
- }
- }
冒泡排序的优化
有些情况下，冒泡排序并不需要排n-1趟才能把乱序数组排成有序的数组，就比如我们上面举的那个例子，只需要排一趟就能将整个数组排成有序的。而我们写的代码是要求进行n-1趟的排序，按最坏的情况来考虑的，这是不能够更改的，但中间存在优化的空间
仔细观察可以发现，当数组已经有序的时候，遍历数组时是没有数字要进行交换的，也就是说，只要程序中不再出现数字交换就表明该数组已经有序了，那么怎样告知程序遍历一遍数组后没有发生数字交换呢？
我们可以在 i 的循环层里设置一个变量flag，先把它的值赋予0，默认数组是有序的，然后在 j 的循环层里，只要有两个数字发生了交换，那就表明该数组仍不是有序的，将flag的值改为1，表明该数组无序，需要进行下一趟的排序，若没有进行交换，则表明数组已经有序，直接退出循环，程序结束
下面是优化后的代码
伪代码
for i := 1 to n-1
{
flag := 0
for j := 1 to n-i-1
if arr[j] < arr[j+1]{
exchange arr[j] with arr[j+1]
flag := 1/}
if flag = 0
return/}
伪代码阅读规则：
伪代码的下标是从1开始的，:=表示赋值，{ /}表示指令序列，类似于C语言的{ }，to表示控制该循环的计数是增加的，downto表示控制该循环的计数是减少的（默认to与downto的控制循环计数变化值为1，当控制循环计数的变化值不为1时可使用by来表示变化值）
c/c++的具体实现代码
- //交换函数
- void swap(DataType* p1, DataType* p2)
- {
- DataType tmp = *p1;
- *p1 = *p2;
- *p2 = tmp;
- }
- //冒泡排序
- void BubbleSort(DataType* arr, int size)
- {
- for (int i = 0; i < size; i++)
- {
- int flag = 0;
- for (int j = 0; j < size - i - 1; j++)
- {
- if (arr[j] < arr[j + 1])
- {
- swap(&arr[j], &arr[j + 1]);
- flag = 1;
- }
- }
- if (flag == 0)
- break;
- }
- }
冒泡排序的时间和空间复杂度
从上面的分析可知，冒泡排序时间复杂度最好的情况能够达到O(n)，最坏的情况就是O(n^2)，在空间复杂度上只额外申请了两个控制循环的变量，是常数个，故空间复杂度为O(1)
选择排序
选择排序的思想
选择排序通过不断地遍历数组，依次选取数组中最小的数字，将其交换到数组的前面，在最坏的情况下选取n-1次就能够完成整个数组的排序，下面是选择排序的动图，接下来我们举例一一说明
便于比较，我们仍使用数组4，1，7，5，6并将其排成升序，首先从下标为0的位置开始遍历数组，找到其中最小的数字，是下标为1的空间所存的数字1，将其与下标为0的空间所存的值进行交换，交换结果如下图
上面我们已经选出了整个数组的最小元素，并把它放到了首元素的位置，那这个数字就默认已经排好了，接下来从剩下的元素里选取最小的元素，就是下标为1的数字4，将其与下标为1的位置的值进行交换，其实是没有变化的
前两个元素都已经默认排好了，接着从剩下的元素里选取最小的元素，是下标为3的数字5，将其与下标为2的元素的值进行交换，交换结果如下图
前三个元素已经默认排好了，接着从剩下的元素里选取最小的元素，是下标为4的数字6，将其与下标为3的元素的值进行交换，交换结果如下图
至此该数组已经排序完成，共进行了n-1次（n是元素个数）排序
选择排序的代码实现
伪代码
for i := 1 to n-1
{
for j := i+1 to n-1
{
if arr[j] < arr[min]
min := j
/}
if min != i
exchange arr[min] with arr[i]
/}
伪代码阅读规则：
伪代码的下标是从1开始的，:=表示赋值，{ /}表示指令序列，类似于C语言的{ }，to表示控制该循环的计数是增加的，downto表示控制该循环的计数是减少的（默认to与downto的控制循环计数变化值为1，当控制循环计数的变化值不为1时可使用by来表示变化值）
c/c++的具体实现代码
- void SelectSort(int* arr, int size)
- {
- for (int i = 0; i < size - 1; i++)
- {
- int min = i;
- for (int j = i+1; j < size - 1; j++)
- {
- if (arr[j] < arr[min])
- min = j;
- }
- if (min != i)
- swap(&arr[min], &arr[i]);
- }
- }
- //swap即交换函数，与前面的代码是互通的，这里就省略了
选择排序的优化
上面排序的过程是遍历数组元素从中选取最小值，然后放到前面的位置，重复这样的步骤完成排序，那我们为何不利用遍历数组元素选取最小值的同时再选取一个最大值呢？将最小值放到数组前面，再将这个最大值放到数组末尾，这样下来直接省了一半的工作量
下面是优化后的代码
伪代码
left := 1 right := n
while left < right
{
for i := left+1 to right
{
if arr[i] < arr[min]
min := i
if arr[i] > arr[max]
max := i
/}
exchange arr[min] with arr[left]
if max = left
max := min
exchange arr[max] with arr[right]
left := left+1
right := right-1
/}
伪代码阅读规则：
伪代码的下标是从1开始的，:=表示赋值，{ /}表示指令序列，类似于C语言的{ }，to表示控制该循环的计数是增加的，downto表示控制该循环的计数是减少的（默认to与downto的控制循环计数变化值为1，当控制循环计数的变化值不为1时可使用by来表示变化值）
c/c++的具体实现代码
- void SelectSort(int* a, int n)
- {
- int left = 0;
- int right = n - 1;
- while (left < right)
- {
- int min = 0;
- int max = 0;
- for (int j = left; j <= right; j++)
- {
- if (a[j] >= a[max])
- max = j;
- if (a[j] <= a[min])
- min = j;
- }
- swap(&a[left], &a[min]);
- if (left == right)
- max = min;
- swap(&a[right], &a[max]);
- left++;
- right--;
- }
- }
选择排序的空间及时间复杂度
选择排序是不断的遍历数组，找到最大最小值，要遍历n-1次数组，在未优化之前，是妥妥的O(n^2)，即使优化省了近一半的工作量，但还是属于O(n^2)这一数量级
在空间复杂度上只额外申请了常数个控制循环的变量，故空间复杂度是O(1)
插入排序
插入排序的思想
插入排序默认第一个数字是排好的，所以开始排序时是从数组下标为1的位置开始，然后与它前面的数字进行对比
如果比它前面的数字要小，那么继续向前找，直到遇到小于等于该数或数组首元素的位置停下，然后在这个位置插入
如果比它前面的数字要大，那就直接在原地插入
下面是插入排序的动图，接下来我们举例一一说明
同样以待排序数组4，1，7，5，6为例，将其用插入排序法排成升序
首先默认首元素位置已经排好了，从下标为1的位置开始插排，下标为1的是数字1，这里需要设置一个临时变量tmp，用来记录1的值，再与它前面的数字进行对比，1小于4，且4位于首元素，前面没有其他元素了，数字1要插入到4的前面，因此数字4要向后挪动一位，数字1要插入，如下图
接着从下标为2的位置开始插排，下标为2的是数字7，大于它前面的数字4，因此在原地插入，等于没有变化，如下图
接着从下标为3的位置开始插排，下标为3的是数字5，与它前面的数字对比，5小于7，因此继续向前对比，5大于4，停下，在4与7之间的位置插入，7需要向后挪动一位，如下图
接着从下标为4的位置开始插排，下标为4的是数字6，与它前面的数字对比，6小于7，因此继续向前对比，6大于5，停下，在5与7之间的位置插入，7需要向后挪动一位，如下图
至此，整个数组已经排序完成
插入排序的代码实现
伪代码
for i := 1 to n-1
{
end := 1
tmp := arr[end+1]
while end >= 1
{
if arr[end] > tmp
arr[end+1] := arr[end]
else
break
end := end-1
/}
arr[end+1] := tmp
/}
伪代码阅读规则：
伪代码的下标是从1开始的，:=表示赋值，{ /}表示指令序列，类似于C语言的{ }，to表示控制该循环的计数是增加的，downto表示控制该循环的计数是减少的（默认to与downto的控制循环计数变化值为1，当控制循环计数的变化值不为1时可使用by来表示变化值）
c/c++的具体实现代码
- void InsertSort(int* arr, int n)
- {
- for (int i = 0; i < n-1; i++)
- {
- int end = 0;
- int tmp = arr[end + 1];
- while (end >= 0)
- {
- if (arr[end] > tmp)
- arr[end + 1] = arr[end];
- else
- break;
- end--;
- }
- arr[end + 1] = tmp;
- }
- }
插入排序的时间及空间复杂度
插入排序在有序的情况下排的是最快的，能达到O(n)，在逆序的情况下是最坏的，能达到O(n^2)，其他情况都处于 O(n) ~ O(n^2) 之间，越接近有序需要执行的指令越少，越接近逆序，需要执行的指令越多，时间复杂度就越高
空间复杂度还是O(1)
希尔排序
希尔排序的前言
希尔排序算法由DonaldShell发明，并根据他的名字命名的，是插入排序的优化，又叫缩小增量排序，在讲希尔排序之前，需要了解为何要引入希尔排序，我们之前分析插入排序的时间复杂度时发现，插入排序对不同的数组排序，所消耗的时间是不同的，如果将一个数组排成序，数组里的数据恰好就是有序的话，那此时的插入排序最省时省力，遍历一遍数据就搞定，但如果数组里的数据是逆序的话，那是最麻烦的
例如将数组1，2，3，4用插入法排成升序，程序从下标1开始，与前一个数对比，2大于1，直接在原地插入，接着程序来到下标2，与前一个数对比，3大于2，直接在原地插入，程序接着来到了下标3，与前一个数对比，4大于3，直接在原地插入，整个程序相当于对数组遍历一遍，时间复杂度是 O(n)
如果要求将数字4，3，2，1排成升序，这是最麻烦的,程序从下标1开始，与前一个数对比，3小于4，将3插入到4的前面，此轮插入循环结束，此时数据为3，4，2，1
接着程序从下标2开始，与前一个数对比，2小于4，接着向前对比，2小于3，3前面没有元素了，已经来到了数组首元素的位置，将2插入到3的前面，此轮插入循环结束，此时数据为2，3，4，1
程序接着从下标3开始，与前一个数对比，1小于4，接着向前对比，1小于3，继续向前对比，1小于2，2前面没有元素了，已经来到了数组首元素的位置，将1插入到2的前面，此轮插入循环结束，此时数据为1，2，3，4 整个排序过程时间复杂度达到了O(n^2)由此可见，插图入排序有序最快O(n)，逆序最慢O(n^2)，而其它的随机存放则处于O(n)~O(n^2)之间，越接近有序，插入排得就越快，越接近逆序，插入排得就越慢，希尔排序就是根据这个原理优化插入的
希尔排序的思想
希尔排序有两个阶段
1.预排序
2.插入排序
要想理解希尔排序，对预排序的理解是重中之重，接下来的内容默认把数据排成升序
预排序就是将待排序的数组简单的排个序，预排序并不一定会使数组有序，而是让它接近有序具体的做法就是将待排序的数组把以gap为间隔的数字分成一个组，将整个数组分成gap个组，再对分的各个组进行插入排序
下面举例说明
这个阶段是预排序的分组阶段，到这预排序阶段进行了一半
至此，预排序的工作已经完成，对比最开始的数组，预排序后的数组更接近升序，希尔排序也进行了一半，还差对整个数组进行插排，不过，对整个数组进行插排是不需要过多描述的，这是前面插入排序的事，接下来我们讨论一下gap的取值问题
gap的值该怎么获得？上例我用的是3，那就一定是3吗？不能用2吗？不能用5吗？不能随便选一个吗？为了gap的取值，接下来，咱们还得仔细研究取不同gap值的区别
当gap取值为2时
当gap取值为5时
放在一起对比
如果上图数据看的不够明显，再看下面一组数据
由上图两组数据的对比，可以发现大概规律是
gap越大，数值大的数据可以越快跳到后面，数值小的数据可以越快跳到前面，但并不是很有序
gap越小，每组需要交换的次数就越多，但很接近有序了
这些数据量还是太少了，所以对比结果不太明显，篇幅原因，大家可自行取更多的数据组进行验证
由此可见，gap的取值不是随随便便的，我们要利用它的规律得到最好的效果
经过前辈们大量的研究和实验，发现当要排序的数据量较大的时候，有两种gap的取值方案且进行多次预排的结果是比较理想的
首先gap = n(n是待排序数据总数目)，然后gap的值以
gap = gap / 2 或是 gap = gap / 3 +1 这两种取值方案不断变化
也就是说，gap的取值不是单一的，预排不是只进行一次，而是动态变化的，就拿gap = gap / 2 来说，假设要排1000个数字，那么第一次预排gap取500，第二次预排gap取250，第三次预排gap取125，第四次预排gap取62......最后一次一定会取到1，刚好又满足了希尔排序的第二步，对整个数组进行插入排序，不过此时经过这么多轮的预排，数组已接近有序，插排将非常快
大家可以仔细感受这个过程真的是非常之巧妙，在数据量较大时，gap的取值先是很大，快速把大数字插排到右边，小数字插排到左边，此时的数组相较最开始时略微有序，而这略微有序能帮下一次gap取值插排时提速，就这样上一次预排的结果促进下一次的预排，gap越取越小，预排结果越接近有序，但预排时的速度不减，很快就完成了排序任务，真的把前面gap取值时的规律运用的淋漓尽致
希尔排序的代码实现
伪代码
gap := n
while gap >1
{
gap := gap/3+1
for i := 1 to n-gap
end := i
tmp := arr[end+gap]
while end >= 1
{
if arr[end] > arr[end+gap]
arr[end+gap] := arr[end]
else
break
end := end-gap
/}
arr[end+gap] := arr[tmp]
/}
伪代码阅读规则：
伪代码的下标是从1开始的，:=表示赋值，{ /}表示指令序列，类似于C语言的{ }，to表示控制该循环的计数是增加的，downto表示控制该循环的计数是减少的（默认to与downto的控制循环计数变化值为1，当控制循环计数的变化值不为1时可使用by来表示变化值）
c/c++的具体实现代码
- void ShellSort(DataType* arr, int size)
- {
- int gap = size;
- while (gap > 1)
- {
- gap = gap / 3 +1;
- for (int i = 0; i < size - gap; i++) //这里使用i++是多组排序同时进行
- {
- int end = i;
- DataType tmp = arr[end + gap];
- while (end >= 0)
- {
- if (arr[end] > arr[end + gap])
- arr[end + gap] = arr[end];
- else
- break;
- end -= gap;
- }
- arr[end + gap] = tmp;
- }
- }
- }
希尔排序的时间及空间复杂度
希尔排序是动态变化的，其运行状态很难估量，时间复杂度目前并没有确切的值，大概在O(n^1.3)~O(n^1.5)之间，贴近O(nlogn)，希尔排序突破了排序算法O(n^2)的壁垒，因为希尔排序的出现，后面出现了更多高效率的排序算法
时间及空间复杂度汇总表格
算法名称 时间复杂度 空间复杂度 稳定性 冒泡排序 O(n) ~ O(n^2) O(1) 稳定 选择排序 O(n^2) O(1) 不稳定 插入排序 O(n) ~ O(n^2) O(1) 稳定 希尔排序 接近O(nlogn) O(1) 不稳定 -
相关阅读:
maven打包springboot项目，分配不同开发环境的配置
一张图带你学习Linux文件权限，简单易懂！
JetBrains产品字体大小调整
react-redux 实现 todolist (联系上一篇文章)
flowable 会签例子
【Rust】使用HashMap解决官方文档中的闭包限制
网络、HTTP、HTTPS、Session、Cookie、UDP、TCP
EL表达式的内置对象及其作用域
基于PRM(probabilistic roadmaps)算法的机器人路线规划算法matlab仿真
OJ练习第182题——字典树（前缀树）
- 原文地址：https://blog.csdn.net/m0_61350245/article/details/126535099
