网站网页建设与维护,黄村网站建设报价,狠狠做狠狠干免费网站,中国肩章军衔图解希尔排序#xff08;直接插入排序的优化#xff09; 1.分组思想 上图中gap为5#xff0c;说明要分成5组。 这5组分别用了五种颜色的线条连接起来了。 第1组#xff1a;9、4 第2组#xff1a;1、8 第3组#xff1a;2、6 第4组#xff1a;5、3 第5组#xff1a;7、5 2.缩… 希尔排序直接插入排序的优化 1.分组思想 上图中gap为5说明要分成5组。 这5组分别用了五种颜色的线条连接起来了。 第1组9、4 第2组1、8 第3组2、6 第4组5、3 第5组7、5 2.缩小增量的过程
前面gap为5的情况排序后会变成下面情况 按照gap把数据分成了两组。
当数据很大的时候数据的间隔很大。 小的数据会往前方大的数据会往后放。
gap会逐渐缩小间隔也会逐渐缩小。
整体的数据会更加趋于有序这个时候使用直接插入排序效率会更高。
gap为2的时候会排序成下面情况 此时分为了1组再排序一次后变成下面情况 此时的数据即为有序的。
3.排序情况分析
3.1 排序五组数据的情况 gap为5将数据分为5组图中红色线画中的为第一组。定义一个 i 变量指向这一组的第二个数据定义一个 j 变量指向 i - gap 的位置。 将 i 下标的值放到定义的 tmp 中然后与 j下标 的值比较。 若 j 下标的值较大将 j 下标的值放到 j gap 的位置。 执行后 j 变量向 j - gap 位置走若这个位置的下标为负数。 则要将 tmp 的值放到 j gap的位置。 j 变量此时在-5下标处要将 tmp 的值放到 j 5的位置。 这一组数据此时为有序了。 排序下一组数据i即可j 变量依然是在 i - gap 的位置。 后面4组数据类似不在演示。 最终排序结果是
3.2 排序两组数据的情况
此时 gap 为2数据此时分为了两组。第一组由红色线画出4、2、5、8、5第二组由蓝色线画出1、3、9、6、7。 i 变量指向这一组的第二个数据 j 变量指向 i - gap 的位置。 将 i 下标的值放到定义的 tmp 中然后与 j下标 的值比较。 若 j 下标的值较大将 j 下标的值放到 j gap 的位置。 执行后 j 变量向 j - gap 位置走若这个位置的下标为负数。 则要将 tmp 的值放到 j gap的位置。 j 变量此时在-2下标处要将 tmp 的值放到 j 2的位置。 这一组数据中的 2 和 4 此时为有序了。 排序下一组数据i 即可j 变量依然是在 i - gap 的位置。 后面剩下的数据类似不在演示。 最终排序结果是
3.3 排序一组数据的情况
i 变量指向第二个数据 j 变量指向 i - gap 的位置。 将 i 下标的值放到定义的 tmp 中然后与 j下标 的值比较。 若 j 下标的值较大将 j 下标的值放到 j gap 的位置。 执行后 j 变量向 j - gap 位置走若这个位置的下标为负数。 则要将 tmp 的值放到 j gap的位置。 j 变量此时在-1下标处要将 tmp 的值放到 j 1的位置。 此时 前两个数据有序了后面的数据排序过程类似。 排序下一组数据i 即可j 变量依然是在 i - gap 的位置。 最终结果是
4.代码分析以及实现 1.间隔分组通常为总长度的一半 2.组内排序 3.重新设置间隔分组为前一组的一半 4.当gap 1时,为直接插入排序。
void ShellSort(int *arr, int n)
{// 初始化间隔为数组的长度int gap n; while (gap 1){// 逐渐减小间隔每次将间隔除以2gap / 2;// 也可以使用这种方式来减小间隔这是一种不同的策略// gap gap / 3 1;// 遍历数组每次跳过gap个元素对每个子序列进行插入排序for (int i 0; i n - gap; i){// 初始化j为当前元素的索引int j i;// 保存当前子序列的元素以便在排序过程中移动int tmp arr[i gap];// 将tmp插入到已排序的子序列中的正确位置while (j 0){// 如果tmp小于子序列中的元素则将该元素向后移动一个间隔if (tmp arr[j]){arr[j gap] arr[j];// 继续向前比较j - gap;}else{// 如果tmp不小于子序列中的元素则跳出循环break; }}// 当j为负数时表示tmp已经找到了正确的位置将其插入到子序列中arr[j gap] tmp;}}
}执行结果
5.性能分析
