@[toc]
插入排序
插入排序分为直接插入排序和希尔排序,其中希尔排序是很值得学习的算法
希尔排序的基础是直接插入排序,先学习直接插入排序
直接插入排序
直接插入排序类似于打扑克牌前的整牌的过程,假设我们现在有2 4 5 3四张牌,那么应该怎么整牌?
方法很简单,把3插到2和4中间,这样就完成了整牌的过程,而插入排序的算法就是这样的过程
插入排序的基本原理图如下所示
我们在这里定义end为已经排查结束的,排好序的一段数据的最后一个元素,tmp作为存储要移动的元素,那么具体实现方法如下:
这里找到了tmp确实比end要小,于是下一步是要让tmp移动到end前面这段有序的数据中的合适的位置
算法实现的思想是:tmp如果比end的值小,那么就让end的值向后移动,end再指向前一个,再比较覆盖移动...直到tmp的值不比end小或者end直接走出数组,如果走出数组就让tmp成为新的首元素
这样就完成了一次插入,那么接着进行一次排序:
从中可以看出,插入排序整体的思想并不算复杂,代码实现相对也更简单,直接插入排序的价值在于给希尔排序做准备
插入排序的实现如下:
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i; // 找到有序数组的最后一个元素
int tmp = a[i + 1]; // 要参与插入排序的元素
while (end >= 0)
{
if (a[end] > tmp)
{
// 进行覆盖
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
直接插入排序的时间复杂度也不难分析,是O(N^2),和冒泡排序在同一个水平,并不算高效
直接插入排序更多是给希尔排序做铺垫,希尔排序是很重要的排序,处理数据的效率可以和快速排序看齐
希尔排序
上面学完了插入排序,那么就必须总结一下插入排序的弊端
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
于是,希尔排序就是基于上面这两个问题进行解决的:
首先,插入排序对于已经排序差不多的序列有很强的效率,但与此同时它一次只能调整一个元素的位置,因此希尔就发明了希尔排序,它具体的操作几乎和插入排序相同,只是在插入排序的基础上,前面多了预排序的步骤,预排序是相当重要的,可以把一段数据的大小排序基本相同
那预排序的实现是如何实现的?
首先把数据进行分组,假设分成3组,下面的图片演示了这个过程
分好组后,对每一组元素单独进行插入排序
此时,序列里的数据就已经很接近有序了,再对这里的数据进行插入排序,可以完美适应插入排序的优点
这里只是写了希尔排序的基本思想是如何工作的,具体的代码实现较为复杂
那么下一个问题就有了,为什么gap是3?如果数据量特别大还是3吗?gap的选择应该如何选择?
这里对gap要进行理解,gap到底是用来做什么的,它的大小会对最终结果造成什么影响
gap是对数据进行预处理阶段选择的大小,通过gap可以把数据变得相对有序一点,而gap越大,说明分的组越多,每一组的数据就越少,gap越小,分的就越细,就越接近真正的有序,当gap为1的时候,此时序列只有一组,那么就排成了真正的有序
代码实现如下:
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
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 = end - gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
这里重点理解两点
gap = gap / 3 + 1; // 这句的目的是什么?
gap==1 // 是什么
gap=gap/3+1会让gap的最终结果一定为1
而gap为1的时候,此时就是插入排序,而序列也接近有序,插入排序的优点可以很好的被利用
希尔排序的时间复杂度相当难算,需要建立复杂的数学模型,这里直接说结论,希尔排序的时间复杂度大体上是接近于 O(N^1.3) 整体看效率是不低的,值得深入钻研学习