本文主要是介绍6.1排序——插入排序与希尔排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
本篇博客来梳理两种常见排序算法:插入排序与希尔排序
常见的排序算法如图
写排序算法的原则:先写单趟,再写整体
一、直接插入排序
1.算法思想
先假定第一个数据有序,把第二个数据插入;再假设前两个数据有序,把第三个数据插入…以此类推,直到整个序列有序
2.具体操作(以排成升序为例)
(1)单趟:针对单个数据
假设[0,end]有序,处理end+1处数据(用tmp存起来,原因:挪数据的时候会覆盖),依次与前面的数比,用while循环控制
- tmp更大:插入
- tmp更小:挪数据,同时–end
程序结构如下
while(end>=0)
{if(tmp更小)//挪数据;--end;elsebreak;
}
//插入数据
注意:如果处理最小的数据,end会是-1(数据要插入到a[0]的位置)
在这里插入代码片
(2)单趟变整体:用for循环控制end从0->n-2
end最大是n-2的原因:要动end+1处数据,保证不越界
(3)具体代码实现
// 直接插入排序(假设排成升序)
void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){//单趟int end = i;//end最大是n-2int tmp = a[end + 1];//end+1最大是n-1while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];//往后挪数据--end;}else{break;}}a[end + 1] = tmp;//插入数据}
}
3.特性总结
(1)时间复杂度:o(N²)
(2)空间复杂度:o(1)
(3)稳定性:稳定
(4)元素集合越接近有序,算法效率越高
二、希尔排序(缩小增量排序)
1.算法思想
先对整个序列进行预排序,使数组接近有序,最后进行直接插入排序的时候数组已经很接近有序,因此可以大大提升算法的效率
2.具体操作(以排成升序为例)
(1)第一步:预排序(让数组接近有序)——本质:gap>1的插入排序
取gap==3,把整组数据分成了3组
①单趟:处理一次之后黄色分组边界上的数字(9,5,8,5)就有序了,相当于对9,5,8,5进行插入排序,只不过中间跨越了gap这么多数据
//以下两层循环实际上就是直接插入排序的变种,把1换成了gap
for (int j = 0; j < n - gap; j+=gap)
{//单趟int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + 1] = tmp;
}
对比一下插入排序的代码,就是把1换成了gap
②单趟变整体——处理红色和蓝色的组别(在外面再用一层for循环控制)
//以下两层循环实际上就是直接插入排序的变种,把1换成了gap
for(int i = 0;i < gap; i++)
{for (int j = 0; j < n - gap; j+=gap){//单趟int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + 1] = tmp;}
}
三层循环看起来太多了,有时候可能会不好分析,于是就可以对(1)(2)进行优化
上面代码的逻辑:先处理黄色组,再处理红色组,最后处理蓝色组,其中对红色组和蓝色组的处理需要在最外层套入第三层循环
优化操作:“每组并着走”,而不是像上面那样“一组一组来”,把最外层循环去掉,然后第二层循环中j+=gap改成j++,处理顺序变成:黄->红->蓝->黄->红->蓝…
for (int j = 0; j < n - gap; j++)//j+=gap改成了j++{//单趟int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + 1] = tmp;}
(2)第二步:插入排序——gap==1的插入排序
注意:gap越大,大的就更快跳到后面,小的就更快跳到前面,但不那么有序
gap越小,跳得更慢,但更有序
所以:gap要不断变小,直到最后变成1,这样最终插入排序处理的序列就更有序——再来一层循环控制gap(此处对上面优化版的代码进行操作,否则四层循环看着都晕了)
常见调整方式:gap=gap/3+1(保证最后一个gap是1)
此处没有单独写插入排序的原因:gap最后会迭代成1,此时执行的就是直接插入排序
至此,完整的希尔排序代码就出来了
(3)具体代码实现
// 希尔排序(假设排成升序)
void ShellSort(int* a, int n)
{//预排序int gap = 3;while(gap > 1)//外面再来一层循环,实现gap的迭代{gap = gap / 3 + 1;//保证最后一个gap是1//以下两层循环实际上就是直接插入排序的变种,把1换成了gapfor (int j = 0; j < n - gap; j++){//单趟int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + 1] = tmp;}}
}
3.特性总结
(1)希尔排序是对直接插入排序的优化
(2)gap>1时是预排序,目的是让数组更接近有序。当gap==1的时候,数组已经接近有序了,此时进行直接插入排序就会很快,性能得到了优化
(3) 希尔排序时间复杂度计算难度大,限于本人水平,只能在这里写个结论,大约是o(N^1.3)
(4)稳定性:不稳定
这篇关于6.1排序——插入排序与希尔排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!