Access希尔排序算法

来源:原创 点击数:1240 　 | 收藏 | 复制

时　间:2022-11-02 08:06:19
作　者:欧志华 ID：51519 城市：广州
摘　要:希尔排序算法。
正　文:

希尔排序(ShellSort)也称“缩小增量排序”，是将整个无序列分割成若干小的子序列分别进行直接插入排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序，这样大大减少了元素移动的次数提高了排序效率。
希尔排序的过程是: 假定待排序列的数组为R[0…n-1]，先取一个正整数h1(h1 间隔序列的求得: 间隔序列就是在希尔排序中使用的增量的序列。例如，在含有100个数据项的数组中，可能先以40为增量，然后以13为增量，以4为增量，最后以1为增量进行希尔排序。其中[40，13，4，11就是一个间隔序列。

下面介绍两种间隔序列的求得方法:

方法一：

在希尔排序算法中，可以利用公式h=3*h+1 生成序列1，4，13，40等。当间隔数大于数组长度时停止这个过程。例如，对于数组长度为 100 的序列，序系列的第5个数121就超过了数组的长度。因此，使用增量为40作为最大数字来开始这个排序过程，然后每完成一趟排序，用前面提供的公式的倒推式减小间隔: h=(h-1)/3，即按照增量序列为40，13，4，1为增量对序列进行希尔排序。

方法二：

在希尔排序算法中，也可以利用公式n/2 来求得间隔序列。例如，对于数组长度为 100 的序列，

用此公式求得的序列为50，25，12，6，3，1。这个方法的好处是不需要在排序开始之前去找初始的间隔。

附件:

点击下载此附件