江苏龙网

  1. 主页 > 生活百科 > >

图解希尔排序，超详细非常好理解( 三 )

希尔排序


因为对每个子序列都采用直接插入排序算法进行排序，因此这里我们简单回顾一下它的原理 。在直接插入排序中将待排序的序列看作两部分，前面部分是已排好序的，后面部分是未排序的 。在最开始的时候，前面部分只有第一个元素，后面部分包含剩余的所有元素 。直接插入排序由多步组成，每一步都将后面部分的第一个元素与前面部分进行比较以找出它应该插入的位置，使插入它之后的新的前面部分依旧是有序的 。这样每一步中，前面部分都增加一个元素而后面部分都减少一个元素，对于一个有m个元素的序列，进行m-1步后该序列就排好序了 。
图4中的例子展示了对子序列排序进行并发执行时，是如何访问每个子序列中的每个待排序元素的，即按照图中绿色箭头指示的顺序访问这些待排序的元素 。

图解希尔排序，超详细非常好理解

文章插图
图4 对子序列排序的并发执行
当我们对希尔排序某一趟中的所有子序列进行排序时，先执行第一个子序列的第1步直接插入排序，然后执行第二个子序列的第1步直接插入排序，以此类推，直到执行完最后一个（第i个）子序列的第1步直接插入排序 。然后我们又回到第一个子序列，对它进行第2步的直接插入排序；然后执行第二个子序列的第2步直接插入排序，一直到最后一个子序列的第2步直接插入排序完成 。然后又回到第一个子序列，执行它的第3步直接插入排序，等等 。这一过程重复执行直到最后一个子序列的第m-1步直接插入排序完成，此时所有的子序列都各自是有序的了 。
第一个子序列的第1步直接插入排序是对它的第二个元素进行排序（第一个元素不需要排序，因为单个元素被认为是有序的），注意该元素在整个序列中的下标为i；第二个子序列的第1步直接插入排序也是对它的第二个元素进行排序，该元素在整个序列中的下标为i+1；第三个子序列的第1步直接插入排序也是对它的第二个元素进行排序，该元素在整个序列中的下标为i+2；最后一个子序列的第1步直接插入排序同样是对它的第二个元素进行排序，该元素在整个序列中的下标为i+i-1（2i-1） 。
然后，第一个子序列的第2步直接插入排序是对它的第三个元素进行排序，该元素在整个序列中的下标为2i；第二个子序列的第2步直接插入排序也是对它的第三个元素进行排序，该元素在整个序列中的下标为2i+1；最后一个子序列的第2步直接插入排序同样是对它的第三个元素进行排序，该元素在整个序列中的下标为2i+i-1（3i-1） 。
因为每一个子序列的元素都是独立而不重叠的，互相之间不会干扰 。所以这样并发执行的结果和串行执行的结果是相同的，这就证明了这样并发执行的正确性 。
按照这样的并发方式，一趟中所有待排序的元素（它们属于不同的子序列）其实是按它们在整个序列中的顺序访问的 。我们从整个序列的第i个（它的下标为i）元素开始，一次向后遍历一个元素，每遍历到一个元素就在它所在的子序列中对它进行直接插入排序，整个序列中属于同一子序列的所有元素的下标值相差i 。当整个序列中的最后一个元素被遍历到且排序后，整个序列在该趟中的所有子序列都已排好序了 。此时，就可以进入希尔排序的下一趟了 。
4. 代码实现这里我们用C语言来实现希尔排序，代码很简单，即便不精通C语言也能看懂，代码中我们也给出了详细的注释 。我们定义了一个辅助函数incrementValue()，它接收两个参数，总的趟数t和当前趟数k，然后用公式2^(t - k + 1) - 1计算并返回当前趟应该采用的增量值 。
#include <math.h>/* * Function: incrementValue * Description: 根据希尔排序总的趟数和当前趟生成增量，计算公式为：2^(t - k + 1) - 1 。* param: t 总的趟数 * param: k 当前趟数 * return: 当前趟对应的增量 */int incrementValue(int t, int k) {int power = t - k + 1;int value = https://www.isolves.com/it/cxkf/sf/2021-12-22/pow(2, power) - 1;return value;}/* * Function: shellSort * Description: 希尔排序的实现 * param: array 待排序的序列（数组） * param: n 序列中的元素数量 * param: t 总的趟数，它将用于生成增量序列 */void shellSort(int array[], int n, int t) {/** i、j、k作为循环控制变量，* temp用于移动元素，* increment用于记录当前趟的增量 。*/int i;int j;int k;int temp;int increment;// 外层循环，用于控制第1至第t趟排序，每一趟都对应一个不同的增量；for(i = 1; i <= t; i++) {// 根据总的趟数和当前趟，获取当前的增量increment = incrementValue(t, i);/** 中间层循环，顺序遍历整个序列中需要排序的每一个元素；* 这些元素在整个序列中的下标从increment开始，直到最* 后一个元素 。每遍历到一个元素就在它所有在的子序列中* 对它进行直接插入排序，同一子序列中的相邻元素的下标* 相差increment 。*/for(j = increment; j


推荐阅读


上一篇：TCP/IP 网络模型有几层？分别有什么用？

下一篇：python的面向对象编程