7.6 希尔排序★3◎4

7.6 希尔排序★3◎4

　　希尔排序又称缩小增量排序，是1959年由D.L.Shell提出来的，较上述几种插入排序方法有较大的改进。
　　希尔排序的基本思想：
　　（1）选择一个步长序列t1，t2，…，ti-1，ti，…，tk，其中，ti-1>ti，tk=1；
　　（2）按步长序列个数k，对序列进行k趟排序；
　　（3）每趟排序，根据对应的步长ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
　　设待排序列为39，80，76，41，13，29，50，78，30，11，100，7，41，86。步长因子分别取5、3、1，则排序过程如下：

　　子序列分别为{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}。
　　第一趟排序结果：

　　子序列分别为{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。
　　第二趟排序结果：
　　p=1　13　7　39　29　11　41　30　76　41　50　86　80　78　100
　　此时，序列基本“有序”，对其进行直接插入排序，得到最终结果：

7　11　13　29　30　39　41　41　50　76　78　80　86　100

【效率分析】
　　希尔排序时效分析很复杂，因为关键码的比较次数与记录移动次数依赖于步长因子序列的选取，但特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有选取最好的步长因子序列的方法。步长因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：步长因子中除1外没有公因子，且最后一个步长因子必须为1。希尔排序方法是一个不稳定的排序方法。