插入排序中 希尔排序的超详细讲解 | 与直接插入排序算法时间效率的对比 +完整可运行c语言代码

文章目录希尔排序1. 基本思想2. 例子3. 复杂度分析4. 稳定性分析5. 测试函数6. 头文件部分7. 实现8. 测试案例main函数输出结果希尔排序希尔排序也是⼀种插⼊排序,它是直接插入排序经过改进的一个更高效的版本1. 基本思想希尔排序是把记录按下标的⼀定增量分组对每组使⽤直接插⼊排序算法排序; 随着增量逐渐减少,每组包含的关键词越来越多当增量减⾄1时整个⽂件恰被分成⼀组算法便终⽌ 给定一个序列[5,4,3,2,1,0] 之前写过的直接插入排序, 序列末端的0要到首位置很麻烦,要移动元素n-1次 ⽽希尔排序在数组中采⽤跳跃式分组的策略,通过某个增量(gap)将数组元素划分为若⼲组然后分组进⾏插⼊排序随后逐步缩⼩增量继续按组进⾏插⼊排序操作直⾄增量为1 希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序,⼩的基本在前,⼤的基本在后 然后缩⼩增量到增量为1时 基本有序:小的关键词基本在前面大的基本在后面,不大不小在中间 像是 [2,1,3,6,4,7,5,8,9] 是基本有序 像是 [1,5,9,3,7,8,2,4,6] 就算不上基本有序 看着文字可能有点抽象下面直接看例子2. 例子给定一个数组 [8,9,1,7,2,3,5,4,6,0]初始时 ------ gap length / 2 5 整个数组被分为5组 即 [ 8 , 3 ] , [ 9 , 5 ] , [ 1 , 4 ] , [ 7 , 6 ] , [ 2 , 0 ] 分组间隔一般取数组长度的一半对这5组分别进行直接插入排序然后我们缩小增量 gap/22 此时数组被分为2组 即 [ 3 , 1 , 0 , 9 , 7 ] , [ 5 , 6 , 8 , 4 , 2 ]对这两组分别进行直接插入排序再次缩小增量 gap/21 (此时也是最后一轮) 此时整个数组为一组 [ 0 , 2 , 1 , 4 , 3 , 7 , 6 , 9 , 8 ]最后对全部的数据进行直接插入排序 (只需对上面元素简单微调即可 无需移动大量元素)3. 复杂度分析最好情况: 在排序之前元素已经是有序了,每一轮增量只需要少量比较 时间复杂度为O(n) 最坏情况: 取绝于增量序列 经典增量序列(也就是本文讲的)n/2 n/4 ... 1 最坏为O(n^2) Hibbard增量序列 2^k -1 保证相邻元素是互质的 (具体感兴趣可以去搜搜 这里就不过多介绍了) 最坏为: O(n ^ 3/2) 当然还有一些其他的增量序列4. 稳定性分析不稳定排序 相同大小的元素会因远距离插入交换改变相对位置5. 测试函数这些测试函数也是上一节 直接插入排序里的测试函数typedefintkeyType;typedefstruct{keyType key;// 查找表中每个数据元素的关键值void*data;// 数据的其他区域}Element;typedefstruct{Element*data;// 存放查找表中数据元素的首地址intlength;// 查找表的元素个数}SortTable;enumsortStatus{success,failed};voidswapElement(Element*a,Element*b);// 交换元素a和元素bSortTable*generateRandomArray(intn,intlow,inthigh);// 产生随机数范围[low,high]SortTable*generateLinearArray(intn,intswapTimes);// 参数顺序空间随机交换swapTimes次 轻微乱序 整体接近有序SortTable*copySortTable(SortTable*old);// 拷贝和old一样值的排序表voidreleaseSortTable(SortTable*table);//释放表// 排序算法函数的别名typedefvoid(*sortHandler)(SortTable*);// 测试sortName的排序算法voidtestSort(constchar*sortName,sortHandler sort,SortTable*table);/* 交换a和b的元素值 */voidswapElement(Element*a,Element*b){Element tmp;memcpy(tmp,a,sizeof(Element));memcpy(a,b,sizeof(Element));memcpy(b,tmp,sizeof(Element));}/* 产生n个随机数的排序表值的范围是[low, high] */SortTable*generateRandomArray(intn,intlow,inthigh){SortTable*tablemalloc(sizeof(SortTable));if(tableNULL){fprintf(stderr,sort table malloc failed!\n);returnNULL;}table-lengthn;table-data(Element*)malloc(sizeof(Element)*n);if(table-dataNULL){fprintf(stderr,element malloc failed!\n);free(table);returnNULL;}srand(time(NULL)1);for(inti0;in;i){table-data[i].key(rand()%(high-low1))low;table-data[i].dataNULL;}returntable;}/* 产生n个随机交换swapTimes次的有序顺序表 *///轻微乱序 整体接近有序SortTable*generateLinearArray(intn,intswapTimes){SortTable*tablemalloc(sizeof(SortTable));if(tableNULL){fprintf(stderr,sort table malloc failed!\n);returnNULL;}table-datamalloc(sizeof(Element)*n);if(table-dataNULL){fprintf(stderr,data malloc failed!\n);free(table);returnNULL;}table-lengthn;for(inti0;in;i){table-data[i].keyi;table-data[i].dataNULL;}// 在已经有序的排序表中交换swapTimes次srand(time(NULL)2);for(inti0;iswapTimes;i){intpos1rand()%n;intpos2rand()%n;swapElement(table-data[pos1],table-data[pos2]);}returntable;}/* 拷贝一个排序表使用同样的数据进行不同排序算法的测试 */SortTable*copySortTable(SortTable*old){SortTable*table(SortTable*)malloc(sizeof(SortTable));table-lengthold-length;table-datamalloc(sizeof(Element)*old-length);for(inti0;iold-length;i){table-data[i].keyold-data[i].key;table-data[i].dataold-data[i].data;}returntable;}/* 释放table */voidreleaseSortTable(SortTable*table){if(table){if(table-data){free(table-data);}free(table);}}// 检查排序表里的数据是否是从小到大排序staticenumsortStatuscheckData(constSortTable*table){for(inti0;itable-length-1;i){if(table-data[i].keytable-data[i1].key){printf(Check Sort Data Failed: %d : %d\n,table-data[i].key,table-data[i1].key);returnfailed;}}returnsuccess;}/* 测试sortName的排序算法算法通过sort传递函数名数据以table传入 */voidtestSort(constchar*sortName,sortHandler sort,SortTable*table){clock_tstartclock();sort(table);clock_tendclock();if(checkData(table)failed){printf(%s failed!\n,sortName);return;}printf(%s cost time: %fs.\n,sortName,(double)(end-start)/CLOCKS_PER_SEC);}​6. 头文件部分voidshellSort(SortTable*table);7. 实现voidshellSort(SortTable*table){for(intgaptable-length/2;gap0;gap/2){//这下面其实就是直接插入排序移动的步长从1变成了gap// i从gap开始遍历每组第一个元素无前置同组数据无需排序,i是各组第二个及后续待调整元素for(intigap;itable-length;i){Element tmptable-data[i];//备份待插入元素intji;//向前每次跨gap 大元素后移/*for (j i;j gap table-data[j - gap].key tmp.key;j - gap) { table-data[j] table-data[j - gap]; }*/// 每次向前跨gap对比若前面元素更大则把前面元素后移一个gap位置while(jgaptable-data[j-gap].keytmp.key){table-data[j]table-data[j-gap];j-gap;}//找到最终插入位置 插入table-data[j]tmp;}}}8. 测试案例main函数voidtest01(){intn10000;// table1: n个随机数的排序表值的范围是[0, 5000]// table2: n个随机交换10次的有序顺序表 轻微乱序 整体接近有序// table3: 拷贝table1中的内容SortTable*table1generateRandomArray(n,0,05000);SortTable*table2generateLinearArray(n,10);SortTable*table3copySortTable(table1);//测试testSort(insertSort,insertSort,table1);//随机排列的 直接插入排序testSort(Linearinsert,insertSort,table2);//轻微乱序的 直接插入排序testSort(shellSort,shellSort,table3);//随机排列的 希尔排序//释放表releaseSortTable(table1);releaseSortTable(table2);releaseSortTable(table3);}intmain(){test01();return0;}输出结果insertSort cost time:0.547000s.Linearinsert cost time:0.001000s.shellSort cost time:0.002000s.insertSort cost time:0.580000s.Linearinsert cost time:0.002000s.shellSort cost time:0.003000s.insertSort cost time:0.548000s.Linearinsert cost time:0.002000s.shellSort cost time:0.002000s.//多次测试所得耗时数值不会完全相同 会受很多因素影响//这里就贴个三组数据//感兴趣可以自己测试下table1 完全随机数据 table2 接近有序 轻微乱序 table3 和 table1 一样的数据 完全随机数据 由此我们看到 希尔排序 希尔排序面对乱序数据优势巨大 数组轻微乱序,整体接近有序时和普通插入差不多​ 嘻嘻嘻嘻 希尔排序部分到此结束​ (有错误欢迎指出) (疑问也是)❤️❤️持续更新中…嘿嘿