数据结构——排序算法第一幕（插入排序：直接插入排序、希尔排序 选择排序：直接选择排序，堆排序）超详细！！！！
文章目录
- 前言
- 一、排序
- 1.1 概念
- 1.2 常见的排序算法
- 二、插入排序
- 2.1 直接插入排序
- 2.2 希尔排序
- 希尔排序的时间复杂度
- 三、选择排序
- 3.1 直接选择排序
- 3.2 堆排序
- 总结
前言
时间很快，转眼间已经到数据结构的排序算法部分啦
今天我们来学习排序算法当中的 插入排序 和 选择排序
准备好上车了，fellow me
一、排序
1.1 概念
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
1.2 常见的排序算法
今天我们要学习的就是插入排序和选择排序
二、插入排序
基本思想:
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
2.1 直接插入排序
当插入第i(i>=1) 个元素时，前面的array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置即将array[i] 插入，原来位置上的元素顺序后移
就像打扑克时，抓到一张新的牌，就一一与前面的牌进行比较，找到适合的位置插入。
实现起来还是相对比较简单的
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++) // 一个一个插入
{
int end = i; // end 为以及排好序列的最后一个元素
int tmp = a[end + 1]; // tmp 表示新插入进来的元素
while (end >= 0) // 现在让新插入的元素 与前面的元素一一比较
{
if (a[end] > tmp) // 如果tmp比当前的元素小 就把当前的元素往后移动
{
a[end + 1] = a[end];
end--; // end-- 一个一个往前比较
}
else // 如果tmp比当前元素大 那就已经找到合适位置
break;
}
a[end + 1] = tmp; // 元素往后移动了一位 前面肯定是有空位的 把tmp插入就好啦
} // 这里 end是最近比较过的元素 tmp大于end位置 end+1是空缺的 所以插入到 end+1的 位置
}
结合着打扑克牌的插入的情景就很好理解了
直接插入排序的特性总结
1.== 元素集合越接近有序，直接插入排序算法的时间效率越高==
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
但 O(N^ 2) 终究还是 O(N^2) 太慢啦 下面我来优化优化 直接插入排序的进阶版本
2.2 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（通常是gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。
它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。
有图才能有真相
一组一组来使用直接插入，组的间隙慢慢变小，最后一层就是直接插入排序，这种方式相比于直接插入排序
外层的 ++循环变成了，gap的递减，从O(N)到 O(logN)
代码优化起来也很简单，在原来的基础上改动一点就好啦
void ShellSort(int* a, int n)
{
int gap = n; // 引入gap
while (gap > 1) // 外层循环
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++) // 这里直接i截止到n-gap 防止取tmp的时候数组越界
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp; // 这些操作还是 直接插入排序的代码 直接插入排序就是gap==1的情况
}
}
}
可能会有人疑问 虽然外层循环优化了，循环内部的代码和直接插入一样的呀
我来仔细讲解
希尔排序的时间复杂度
希尔排序的时间复杂度估算：
外层循环：
外层循环的时间复杂度可以直接给出为： O(log2(n)) O(log3(n)) 即O(log n)
内层循环：
可以画出曲线图:
因此，希尔排序在最初和最后的排序的次数都为n，即前一阶段排序次数是逐渐上升的状态，当到达某一顶点时，排序次数逐渐下降至n，而该顶点的计算暂时无法给出具体的计算过程
所以希尔排序的时间复杂度为 ：O(nlog n) ~ O(n^2) 最好的情况为O(n ^1.3) 最坏的情况为O(n ^2)
插入排序就到这里啦
三、选择排序
选择排序的基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
3.1 直接选择排序
- 在元素集合array[i]–array[n-1] 中选择关键码最大(小)的数据元素
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
- 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]） 集合中，重复上述步骤，直到集合剩余1 个元素
通俗一点来讲，先遍历一遍，找一个最小的数据，放第一个，然后遍历第二个到最后一个数据，找最小放在第二个
这样一直遍历，放置，遍历，放置，数据就排好了。
代码实现起来也是很简单的
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin; i < end; i++) // 每一躺找出最大和最小值
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
if (maxi == begin) // 注意有最大值在当前区域的第一个位置 如果先把最小的换过去，最大的位置就变了
{
maxi = mini; // 所以这里要处理一下
}
swap(a[mini], a[begin]);
swap(a[maxi], a[end]); // 把最小换到前面，把最大换到后面
begin++; // 数组需要遍历的元素减少两个 每次都排一个当前区域的最大值和最小值
end--;
}
}
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2) 注定是上不了台面
- 空间复杂度： O(1)
3.2 堆排序
博客链接：堆排序
堆排序在之前的二叉树第一幕已经讲过啦
这里就不多赘述了，主要是深刻理解向下调整算法和向上调整算法
实现一下代码吧
void AdjustDown(int* a, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] > a[child + 1])
{
child++;
}
if (a[child] < a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int *a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, i, n);
}
int end = n - 1;
while (end > 0)
{
swap(a[0], a[end]);
AdjustDown(a, 0, end);
end--;
}
}
堆排序就到这里啦，以上代码供复习使用，详情去 ----博客链接：堆排序
总结
今天就学习了插入排序和选择排序，总体来说就是希尔排序有一些难处理，堆排序在前面的博客已经讲过啦
其他的都挺简单的，平常也很容易想到
下一篇，小编可是要放大招了嗷，听说快速排序用起来可是非常爽的，不要走开，小编持续更新中~~~
欲望以提升热忱，毅力以磨平高山。又是充实的一天
