【初阶数据结构篇】插入、希尔、选择、堆排序
文章目录
须知
💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！
👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对数据结构感兴趣的朋友，让我们一起进步！
前言
下面都以排升序为例
排序共有4种，如下图：
本篇文章将先讲述前两个排序大类，后续博客将讲解剩下的排序算法。
1. 插入排序
1.1 直接插入排序
基本思想
直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列。
实际生活中的应用：打扑克牌。
动图理解：
1.1.1 分析
当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移。
数组为例：
int a[]={5,4,6,3,2,1,9,8,7};
end指向已经排好序的最后一个位置，tmp用于存储待排序的数据。
if(a[end]>tmp},循环移动将将数据往前移腾出空间，用于存储待排数据
最好情况移动一次，最差情况end==-1移动到最后，将tmp置于a[end+1]处。
1.1.2 示例代码：
void InsertSort(int* arr, int n)
{
//n-2
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else {
break;
}
}
arr[end + 1] = tmp;
}
}
时间复杂度分析：
最坏情况：数组降序排列
当我们对下标为i（0<i<n）的tmp数据进行插入时，会将其与前面i个数据比较i次，总比较次数即1+2+3+……(n-1)，O(n^2)
最好情况：数组升序排列
当我们对下标为i（0<i<n）的tmp数据进行插入时，只会与其前面一个数据比较一次，即总共(n-1)此，为O(n)
空间复杂度：O(1)
1.2.希尔排序
在直接插入排序中我们发现，元素越无序，直接插入排序算法时间效率越低（因为比较次数越多）。特别是当数组为降序，我们要排升序，此时数组的相对无序程度达到了最大，时间复杂度也到了最大.
希尔排序法⼜称缩⼩增量法。
希尔排序法的基本思想是：先选定⼀个整数（通常是gap=n/3+1），把 待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排 序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于 直接插⼊排序。 它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算 法的。
gap=n,gap=gap/2进行操作。
1.2.1 分析
既然是直接插入排序法的改进，二者在许多地方有相似之处：
一次预排序
从下标为0的元素开始，每隔gap-1个数据取数据分到一组，从取数据的方式我们可以得出以下结论:
。总共有gap组（0-(gap-1)的元素为每一组的头元素）
。每组有n/gap或n/gap+1个数据
。每一次排序我们排的是end和end+gap（即tmp）处的元素，保证每次排序都是在同一组内排
end初始为0可得tmp初始为gap，tmp末态为n-1可得end末态为n-1-gap
。在一组内进行的是直接插入排序，只不过把距离从1换为gap，全部换一下就行了，思路是一样的
。每次预排序结束后，让gap/3+1
。加一保证最后一次排序gap为1，否则无法保证最后一次是直接插入排序
1.2.2 示例代码：
//希尔排序时间复杂度：O（n^1.3)
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;//保证最后一次gap一定为1
for (int i = 0; i < n - gap; i++)
{
int end = i;//n-gap-1
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else {
break;
}
}
arr[end + gap] = tmp;
}
}
}
复杂度分析：
希尔排序的时间复杂度估算：
外层循环： 外层循环的时间复杂度可以直接给出为：或者，即 O(log n) 2 O(log n) 3 O(logn)
内层循环：
假设⼀共有n个数据，合计gap组，则每组为n/gap个；在每组中，插⼊移动的次数最坏的情况下为 1 +2+3+....+( − n 1)) gap ，⼀共是gap组，因此： 总计最坏情况下移动总数为： gap∗[1+2+3+....+( − n 1)] gap gap取值有（以除3为例）：n/3 n/9 n/27 ...... 2 1 n • 当gap为n/3时，移动总数为： ∗ 3 • 当gap为n/9时，移动总数为： ∗ n 9 (1 +2) = n n (1 +2+3+....+8) = ∗ 9 • 最后⼀躺，gap=1即直接插⼊排序，内层循环排序消耗为n 通过以上的分析，可以画出这样的曲线图：
因此，希尔排序在最初和最后的排序的次数都为n，即前⼀阶段排序次数是逐渐上升的状态，当到达 某⼀顶点时，排序次数逐渐下降⾄n，⽽该顶点的计算暂时⽆法给出具体的计算过程 希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排 序的时间复杂度都不固定。《数据结构(C语⾔版)》---严蔚敏书中给出的时间复杂度为：
2. 选择排序
2.1 直接选择排序
选择排序的基本思想： 每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待 排序的数据元素排完。
2.1.1分析
1. 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(⼩)的数据元素 2. 若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素 交换 3. 在剩余的 array[i]--array[n-2] （ array[i+1]--array[n-1] ） 集合中，重复上述步 骤，直到集合剩余 1 个元素 。
动图：
void SelectSort1(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int mini = i;
for (size_t j = i+1; j < n; j++)
{
if (arr[j] < arr[mini])
mini = j;
}
Swap(&arr[i], &arr[mini]);
}
}
时间复杂度太高O(n^2)
进一步进行优化：再一次循环中同时找最大和最小，最大的放后面，最小的放前面。
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin+ 1; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
//mini begin
//maxi end
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
++begin;
--end;
}
}
这个思路没问题，我们接下来看下面的数据。
。进入循环后，maxi指向9，mini指向1。
进入交换步骤1和9进行交换。此时mini指向9，maxi指向1.
进入第二个交换函数，9和1交换，此时mini指向1，maxi指向9.还原至初始位置。
//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据
if (maxi == begin)
{
maxi = mini;
}
为什么会造成这样？
begin指向的是数据最小的位置，mini指向最小数据，maxi指向最大的数据交换完后，数据指向大小发生改变，mini指向最大数据，maxi指向最小的数据。最小的数据与end指向位置交换。
2.1.2 完整代码：
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
//mini begin
//maxi end
//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
++begin;
--end;
}
}
选择排序特性：
- 直接选择排序思考⾮常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
2.2 堆排序
已经实现过了，不再重复，有需要的可以看博客链接：
【数据结构篇】探索堆的算法的巧妙-CSDN博客
相信通过这篇文章你对二叉树递归暴力的有了初步的了解。如果此篇文章对你学习数据结构（排序算法）有帮助，期待你的三连，你的支持就是我创作的动力！！！
下一篇文章再会！！！