唐山自助网站建设系统,传奇手游发布网,网优工程师前景和待遇,做出个人网站什么水平呀哈喽#xff0c;我是结衣 不知不觉#xff0c;我们的数据结构之路已经来到了#xff0c;排序这个新的领域#xff0c;虽然你会说我们还学过冒泡排序。但是冒泡排序的性能不高#xff0c;今天我们要学习的希尔排序可就比冒泡快的多了。
希尔排序
希尔排序的前身是插入排…呀哈喽我是结衣 不知不觉我们的数据结构之路已经来到了排序这个新的领域虽然你会说我们还学过冒泡排序。但是冒泡排序的性能不高今天我们要学习的希尔排序可就比冒泡快的多了。
希尔排序
希尔排序的前身是插入排序可以说希尔排序就是插入排序的优化。并且优化了很多。所以在讲希尔排序前我们要先学会插入排序不然在后续学习希尔排序会比较的吃力。那么让我们先进入插入排序的教学吧。
插入排序
直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 实际上我们玩扑克的时候就运用了插入排序的思想 本来想放张插入排序动图的可是放进来后它就不动了。。。 下面我们来讲解插入排序的特点 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)逆序情况 最好情况为O(N)数组比较有序为希尔排序提供了思路空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 了解完了我们就要开始代码讲解了
void InsertSort(int* a, int n)
{for(int i 0;in-1;i){int end i;int tmp a[end 1];while (end0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}a[end 1] tmp;}}
}思路 在待排序的元素中假设前end个元素已有序现将第end1个元素插入到前面已经排好的序列中使得前end个元素有序。按照此法对所有元素进行插入直到整个序列有序。但我们并不能确定待排元素中究竟哪一部分是有序的所以我们一开始只能认为第一个元素是有序的依次将其后面的元素插入到这个有序序列中来直到整个序列有序为止 红色竖杆表示已经排好序列绿色圈住的数字表示要插入到前面序列的数字。
希尔排序缩小增量排序
讲完插入排序接下来就到了我们的重点了——希尔排序
希尔排序的思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 在希尔排序中我们要引入gap间隔我们来画图理解。 当gap不为1时我们可以把它看做为一个预排序先把数组变成比较有序。然后当gap为1时就是直接插入排序了因为插入排序对比较有序的数组排列效率更高所以希尔排序就为先预排序再直接插入排序。
预排序
再讲希尔排序的代码实现前我们先来讲预排序。我们先定义一个长度为6的逆序数组{654321}.再来假设gap为3。 我们知道插入排序再排逆序的数组时时间复杂度为最坏的情况。所以我们才要进行预排序。 我们一组一组排 经过预排序后数组已经变得比较有序了这对后面的直接插入排序是有好处的提高效率。
int gap 3;for(int i 0;in-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;}}这个只是一个预排序和插入排序的思路大差不差只是把改了一些细节。 看看打印结果 和我们前面推算的相同。
希尔排序的代码实现
思路讲完了预排序也讲完了。希尔排序终于要来了。在现实情况下我们能知道gap为多少吗像前面我的只排6个数据gap3还是可以的但是如果我们要排一百万一千万一亿甚至更多的数呢gap又要怎么算呢我们要知道。gap越小预排序越接近有序但也排的越慢。gap越大预排序越不接近有序但排的越快。但是我们找不到gap应该取多少所以我们可以让gap等于一个随机的数但要越来越小直到gap1进行插入排序。
void ShellSort(int* a, int n)
{int gap n;// gap 1时是预排序目的让他接近有序// gap 1是直接插入排序目的是让他有序while (gap1){gap gap / 3 1;//也可以写成gap/2.目的都是为了最后一次gap一定要为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 - gap;}else{break;}a[end gap] tmp;}}}}可能写起来比较麻烦都是希尔排序的效率可是非常高度。它的效率略低于但接近快排和堆排远高于插入排序插入排序的效率又远高于冒泡排序。希尔排序的时间复杂度在下方。
希尔排序的特性
希尔排序的特性总结 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固 下面我们来看严蔚敏老师和殷人昆老师的解释 《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆 完
