【正厚软件】如何理解希尔排序的过程?
2019-08-16

此次分享为专业分享,可能对于基础知识有跳跃感,希望大家能够看得懂!

1,有关插入排序

(1)插入排序的基本方法是:每步将一个待排序的元素,按其排序码大小插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止。

(2)可以选择不同的方法在已经排好序的有序数据表中寻找插入位置,依据查找方法的不同,有多种插入排序方法。下面是常用的三种。

1>直接插入排序

2>折半插入排序

3>希尔排序

(3)直接插入排序基本思想:当插入第ii>1)个元素时,前面的data[0],data[1]……data[i-1]已经排好序。这时用data[i]的排序码与data[i-1],data[i-2],……的排序码顺序进行比较,找到插入位置即将data[i]插入,原来位置上的元素向后顺序移动。

(4)折半插入排序基本思想:设元素序列data[0],data[1],……data[n-1]。其中data[0],data[1],……data[i-1]是已经排好序的元素。在插入data[i]时,利用折半搜索法寻找data[i]的插入位置。

(5)希尔排序的过程相比前两种有些不同,下面我们主要介绍希尔排序的过程实现。

 

2,希尔排序

(1)希尔排序(shell sort)这个排序方法又称为缩小增量排序,是1959D·L·Shell提出来的。该方法的基本思想是:设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,所有距离为increment的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。

 

(2)由于开始时,increment的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期increment取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。

 

(3)希尔排序举例:

1>下面给出一个数据列:

 

2>第一趟取increment的方法是:n/3向下取整+1=3(关于increment的取法之后会有介绍)。将整个数据列划分为间隔为33个子序列,然后对每一个子序列执行直接插入排序,相当于对整个序列执行了部分排序调整。图解如下:

 

3>第二趟将间隔increment= increment/3向下取整+1=2,将整个元素序列划分为2个间隔为2的子序列,分别进行排序。图解如下:

 

4>第3趟把间隔缩小为increment= increment/3向下取整+1=1,当增量为1的时候,实际上就是把整个数列作为一个子序列进行插入排序,图解如下:

 

5>直到increment=1时,就是对整个数列做最后一次调整,因为前面的序列调整已经使得整个序列部分有序,所以最后一次调整也变得十分轻松,这也是希尔排序性能优越的体现。

 

(4)希尔排序算法的代码实现(C++

 //函数功能,希尔排序算法对数字递增排序

//函数参数,数列起点,数列终点

void shell_sort(const int start, const int end) {

    int increment = end - start + 1;    //初始化划分增量

    int temp{ 0 };

    do {    //每次减小增量,直到increment = 1

        increment = increment / 3 + 1;

        for (int i = start + increment; i <= end; ++i) {    //对每个划分进行直接插入排序

            if (numbers[i - increment] > numbers[i]) {

                temp = numbers[i];

                int j = i - increment;

                do {    //移动元素并寻找位置

                    numbers[j + increment] = numbers[j];

                    j -= increment;

                } while (j >= start && numbers[j] > temp);

                numbers[j + increment] = temp;  //插入元素

            }

        }

    } while (increment > 1);

}

 

上面的函数的第一个do……while控制increment每次的缩小,其内部便是直接插入排序算法的使用,与直接插入排序算法稍有不同的一点是:其j每次的变化量是increment而不是1

 

(5)关于希尔排序increment(增量)的取法。

增量increment的取法有各种方案。最初shell提出取increment=n/2向下取整,increment=increment/2向下取整,直到increment=1。但由于直到最后一步,在奇数位置的元素才会与偶数位置的元素进行比较,这样使用这个序列的效率会很低。后来Knuth提出取increment=n/3向下取整+1.还有人提出都取奇数为好,也有人提出increment互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。

 

(6)希尔排序应该注意的问题

从上面图解希尔排序的过程可以看到,相等的排序码25在排序前后的顺序发生了颠倒,所以希尔排序是一种不稳定的排序算法。

 

未完待续……

 

如果需要详细了解试听或培训课程费用可留下 姓名+联系方式(手机号或微信号),我们会在第一时间为您解答服务!

 

软件测试零基础班

软件测试周末精品班

java开发班

ISTQB考试班

 

更多资讯尽在官方网站

www.njzhenghou.com