常见排序算法之插入排序
目录
一、直接插入排序
1.1 什么是插入排序
1.2 代码思路
1.3 C语言源码
二、希尔排序
2.0 插入排序的弊端
2.1 什么是希尔排序？
2.2 排序思路
2.3 C语言源码
一、直接插入排序
1.1 什么是插入排序
插入排序是一种简单直观的排序算法，它通过构建有序序列，对未排序数据逐个插入到合适的位置，从而达到排序的目的。
具体操作为：将第一个元素视为已排序部分，然后依次将后面的元素插入到已排序部分，直到所有元素都插入完成为止。
插入排序的时间复杂度为O(N^2)，是一种稳定的排序算法。
1.2 代码思路
采取先部分后整体的思路进行讲解
- 部分
- 假设前n个元素均为已排序好的元素，已排序好的最后一个元素的数组下标为end
- 将end+1下标对应的值与end对应的值进行比较
如果大于前一个值，则在end+1的位置插入该值。
如果小于前一个值，则在end-1的位置插入该值。 - 循环比较已经排序好的元素的值与end+1的值，重复插入操作。
在比较有限次后若发现满足条件，则跳出循环。
考虑最坏的情况，如果end-1为0时，也就是插入到了数组的第一个位置，则跳出循环。
- 整体
- 从n=0开始循环，假设循环i次,那么每次已排序好的数组最后一个下标就是数组的大小-i
- 关键问题是要进行多少次循环？
1.3 C语言源码
void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > a[end + 1]){a[end + 1] = a[end];end--;}else{break;}a[end + 1] = tmp;}}
}
二、希尔排序
2.0 插入排序的弊端
插入排序的主要弊端在于其时间复杂度较高。在最坏情况下，插入排序的时间复杂度为O(n^2)，因此对于大规模数据集合来说，插入排序的效率较低。尤其是当数组是升序排序时，想要转成降序排序，效率极低。
由此衍生出希尔排序。通过引入增量序列，将整个数据集合分成多个子序列，并对每个子序列进行插入排序，逐渐减小增量，最终实现对整个数据集合的排序。这样做减少了数据的搬移次数，提高了排序的效率。希尔排序通过这种分组的方式，使得较小的元素可以更快地移动到合适的位置，从而减少了插入排序中的反复比较和移动操作，提高了排序效率。
2.1 什么是希尔排序？
希尔排序是一种基于插入排序的排序算法，也被称为“缩小增量排序”。它的基本思想是将待排序的元素分成若干个小组，对每个小组进行插入排序；然后逐渐减小每组的元素个数，继续进行插入排序，直到每组只有一个元素为止。通过这种分组和逐渐减小增量的方式，希尔排序可以在一定程度上减少插入排序的移动操作次数，从而提高排序效率。
2.2 排序思路
采取先部分后整体的思路进行讲解
- 部分
- 设置分组的间隔 gap。
- 将每个组看作一个新的数组进行插入排序。
- 插入排序的数组下标以及循环结束的条件需要改变，见下图解
- 整体
- 重新设置分组的间隔gap，缩小组数，重复插入排序操作。
- 直至gap为1，对整体进行一次插入排序，则最终完成了对数组的排序。
- 关于gap的取值选择，目前尚无定论。取gap = gap / 3+1为例
摘自《数据结构-用面向对象方法与C++描述》-殷人昆
2.3 C语言源码
void ShellSort(int* a, int n)
{int gap = n;//总逻辑while (gap > 1){gap = gap / 3 + 1;//多组排序逻辑for (int j = 0; j < gap; j++){//一组排序逻辑for (int i = 0; i < n - gap; i++){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;}}}}
}