做任务领礼品的网站,wordpress怎么和手机连接数据库,家具网站建设策划,郑州网站的建设✨个人主页#xff1a; 熬夜学编程的小林
#x1f497;系列专栏#xff1a; 【C语言详解】 【数据结构详解】【C详解】
目录
1、希尔排序( 缩小增量排序 )
1.1、预排序实现
1.2、希尔排序代码实现
1.3、代码测试
1.4、时空复杂度分析
1.5、性能比较
总结 上一弹我们…
✨个人主页 熬夜学编程的小林
系列专栏 【C语言详解】 【数据结构详解】【C详解】
目录
1、希尔排序( 缩小增量排序 )
1.1、预排序实现
1.2、希尔排序代码实现
1.3、代码测试
1.4、时空复杂度分析
1.5、性能比较
总结 上一弹我们学习了直接插入排序通过时空复杂度分析时间复杂度为O(N^2)一般情况效率较低有没有对直接插入排序进行优化的排序呢没错我们这一弹讲解的排序就是对直接插入排序的优化的排序
1、希尔排序( 缩小增量排序 ) 希尔排序是一种基于插入排序的算法通过引入增量的概念来改进插入排序的性能 希尔排序法又称缩小增量法。希尔排序法的基本思想是将原始列表分成多个子列表先对每个子列表进行插入排序然后逐渐减少子列表的数量使整个列表趋向于部分有序最后当整个列表作为一个子列表进行插入排序时由于已经部分有序所以排序效率高。这个过程中每次排序的子列表是通过选择不同的“增量”来确定的。 动图如下 实现思路 预排序直接插入排序 1.1、预排序实现 预排序 根据当前增量数组被分为若干子序列这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序。 假设当前增量为5 首先增量为5我们将数组元素分为增量5个子序列每个子序列由原数组中相隔增量位置上的元素组成。所以我们有如下子序列 子序列1: 94 子序列2: 18 子序列3: 26 子序列4: 53 子序列5: 75 然后对每个子序列进行独立的插入排序 子序列1排序后49 子序列2排序后18 子序列3排序后26 子序列2排序后35 子序列3排序后57 一趟排序之后的数组 4 1 2 3 5 9 8 6 5 7 完成了一轮希尔排序此时整个数组并不完全有序但是已经比原始的数组更接近有序了。然后减小增量通常是将原来的增量除以2或者除以31现在选择下一个增量为 2按照此排序规则继续预排序即可直到增量为1时则为直接插入排序此时则排序完成。 一个子序列排序实现
int gap;
int end;
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;
与直接插入代码不同的是这里对end所加减的均为gap
单次插入完成后我们来控制单个子序列的整个过程每实现一次排序下一次插入的数据为endgap。 单趟排序实现
int gap;for (int i 0; i n-gap; i gap)
{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;
}这里for循环的条件为 i n-gap 防止数组越界.
完成单个子序列的排序后我们再对整个子序列排序
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 (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}
}外层循环for (int j 0; j gap; j)意在对每个以gap为间隔的分组进行遍历。 优化 这串代码三层循环的逻辑是按照每一组排序完成后再进行下一组排序的事实上我们可以不需要最外层的循环。 int gap 3;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;
}这里我们将原先代码中的i gap修改为i意味着这次不是按照一组一组进行了是一次排序完每个组的第二个元素再进行下一个元素的排序。 1.2、希尔排序代码实现
我们先对预排序的增量进行分析 gap越大大的值更快调到后面小的值更快调到前面越不接近有序。 gap越小大的值更慢调到后面小的值更慢调到前面越接近有序。 当gap为1就是直接插入排序。 所以在实现希尔排序时给gap固定值是行不通的。 因此gap的值是应该随着n来变化的实现多次预排。为了满足gap最终为1博主推荐的方式是先将gap赋值成n然后在排序的时候将gap赋值成gap/31(或者gap/2)。 void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;//博主写的是/31也可以是gap/2for (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是奇数还是偶数这里gap最终都会除以到值为1。
在这里 gap1时是预排序目的让其接近有序。gap1时是直接插入排序目的让其有序。 在gap1时已经十分接近有序了。 这里gap预排序次数还是有点多因此我们可以再次进行修改让gap每次除以3为了使gap最后能回到1我们进行加一处理。 注意 1. 此处都是每隔gap进行插入。 2. gap不是一定为gap/3 1也可以是gap /2 原因是当gap等于1的时候就是直接插入排序进行一次排序即可变成有序所以只要最后的gap为1都是可以的。 1.3、代码测试 测试代码
//测试希尔排序
int main()
{int a[] { 9,8,7,6,5,4,3,2,1,0 };//给一组数据int sz sizeof(a) / sizeof(a[0]);//计算数组元素个数printf(排序前\n);ArrayPrint(a, sz);ShellSort(a, sz);printf(排序后\n);ArrayPrint(a, sz);return 0;
}
测试结果 1.4、时空复杂度分析 希尔排序的时间复杂度并不固定它依赖于所选择的间隔序列增量序列。直到今天已经有多种不同的间隔序列被提出来每种都有自己的性能特点。 《数据结构(C语言版)》--- 严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆
时间复杂度
因为咋们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照O(N^1.25) 到 O(1.6* N^1.25) 来算。 空间复杂度
插入排序的空间复杂度为O(1)因为它是一个原地排序算法不需要额外的存储空间来排序。 1.5、性能比较
我们在前面一弹提到了clock()函数可以获取程序启动到函数调用时之间的CPU时钟周期数我们在这里通过具体的排序算法来进行比较性能。
注意clock()函数的头文件是#includetime.h时间的单位为毫秒。 性能比较的思想是通过比较两个函数所运行的时间大小。通过clock计算排序前的程序运行的时间再计算排序结束程序运行的时间时间的差值则为排序运行的时间。 尽量使用release模式进行测试因为release效率更高。
测试代码
void TestOP()
{srand(time(0));//随机数种子const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);//动态开辟N个元素int* a2 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand() i;//随机数只有3万为了更加随机再加上ia2[i] a1[i];}//clock计算程序运行到此时的时间 毫秒int begin1 clock();//排序前程序运行时间InsertSort(a1, N);int end1 clock();//排序后程序运行时间int begin2 clock();ShellSort(a2, N);int end2 clock();printf(InsertSort:%d\n, end1 - begin1);//程勋运行时间的差值即排序运行的时间printf(ShellSort:%d\n, end2 - begin2);free(a1);//释放空间free(a2);
}当N为10万时release版本测试出来的结果 当N为100万时release版本测试出来的结果 明显能够看到希尔排序的效率比直接插入排序的效率高很多当N为10万的时候希尔排序是直接插入排序的18倍当N为10万的时候希尔排序是直接插入排序的20倍。 希尔排序的特性总结 时间复杂度O(N²) 空间复杂度O(1) 稳定性不稳定 复杂性简单 总结 本篇博客就结束啦谢谢大家的观看如果公主少年们有好的建议可以留言喔谢谢大家啦
