沈阳酒店企业网站制作,网址大全免费网站,网络公司专业做网站,一 美食 视频网站模板下载安装目录
1.希尔排序( 缩小增量排序 )
2.动图 编辑
3.代码实现
预排序实现
子序列排列实现
单趟排序实现
对整组数进行子排序
希尔排序代码
代码测试 时间复杂度分析
希尔排序的特性总结#xff1a; 1.希尔排序( 缩小增量排序 )
基本思想#xff1a;
1.先选定一个…目录
1.希尔排序( 缩小增量排序 )
2.动图 编辑
3.代码实现
预排序实现
子序列排列实现
单趟排序实现
对整组数进行子排序
希尔排序代码
代码测试 时间复杂度分析
希尔排序的特性总结 1.希尔排序( 缩小增量排序 )
基本思想
1.先选定一个小于N的整数gap作为第一增量然后将所有距离为gap的元素分在同一组并 对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量重 复上述操作… 2.当增量的大小减到1时就相当于整个序列被分到一组进行一次直接插入排序排序完成。
2.动图
3.代码实现
思路 预排序实现 插入排序 预排序实现
根据当前增量数组被分为若干子序列这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序。
假设最初增量为5 d越大数据挪动得越快d越小数据挪动得越慢。前期让d较大可以让数据更快得移动到自己对应的位置附近减少挪动次数。
注一般情况下取序列的一半作为增量然后依次减半直到增量为1也可自己设置。 完成了一轮希尔排序此时整个数组并不完全有序但是已经比原始的数组更接近有序了。然后减小增量通常是将原来的增量除以2或者除以31现在选择下一个增量为 2按照此排序规则继续预排序即可直到增量为1时则为直接插入排序此时则排序完成。
子序列排列实现
//子序列int gap;int endint tmp a[end gap];while (end 0){if (tmp a[end]){a[end 3] a[end];end - gap;}else{break;}}a[end gap] tmp; 这里只需要在插入排序的基础上修改一下即可。end的所加所减都为gap;
单趟排序实现
int gap;//单趟排序实现for (int i 0; i n - gap; i gap){//子序列int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end 3] a[end];end - gap;}else{break;}}a[end gap] tmp;} 这里的 n-gap 和插入排序中的 n-1 一样是为了防止越界 对整组数进行子排序
int gap;for (int j 0; j gap; j){//单趟排序实现for (int i 0; i n - gap; i gap){//子序列int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end 3] a[end];end - gap;}else{break;}}a[end gap] tmp;}} 外层循环for (int j 0; j gap; j)意在对每个以gap为间隔的分组进行遍历。 这里进行一下优化
三层代码的循环是每一组子排序排完再进行下一组直到排完整个数组。
下面这组代码优化后效率并没有很大的提升只是代码更为简洁。
这组代码是齐头并进排完第一组的前n个就排下一组了并没有把第一组全部排完。 int gap;for (int i 0; i n - gap; i){//子序列int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end 3] a[end];end - gap;}else{break;}}a[end gap] tmp;} 希尔排序代码
分析 gap越大大的值更快调到后面小的值更快调到前面越不接近有序。 gap越小大的值更慢调到后面小的值更慢调到前面越接近有序。 当gap为1就是直接插入排序。 所以我们这里的gap值应该是在变化的一般我们随n变化取gap gap/31或者gap gap/2;
void ShellSort(int* a,int n)
{int gap n;while (gap1){gap gap / 3 1;for (int i 0; i n - gap; i){//子序列int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
} 这里无论gap是奇数还是偶数这里gap最终都会除以到值为1。 gap1时是预排序目的让其接近有序。 gap1时是直接插入排序目的让其有序。 在gap1时已经十分接近有序了 代码测试 时间复杂度分析
希尔排序的时间复杂度并不固定它依赖于所选择的间隔序列增量序列。直到今天已经有多种不同的间隔序列被提出来每种都有自己的性能特点。
《数据结构(C语言版)》--- 严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆 因为咋们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照O(N^1.25) 到 O(1.6* N^1.25) 来算。
希尔排序的特性总结 时间复杂度O(N²) 空间复杂度O(1) 稳定性不稳定 复杂性简单 如有错误请指正
