多种算法合在一起的编程基础学习

上节对直接插入排序进行了优化，我们暂且把优化算法称为二分直接插入排序，这种算法仅仅事对寻找插入点的过程做了优化。如果我们能找到另一中方法，可同为减少寻找插入点的次数和移动结点的次数，就可显著的提高排序的运算速度。
本节介绍的希尔排序算法是直接插入排序法的一种变种，它能有效的减少这两个方面的运算量，从而显著的提高排序操作的运算速度。
原理： 先取一个小于结点数的整数k作为分组单位，把表上的所有相距k的结点逻辑上看成一组。在个组内进行直接插入排序；减小k的取值，把表上的所有相距k的结点逻辑上看成一组。在个组内进行直接插入排序；重复以上步骤；最后一次k取1，即对整个表做直接插入排序。
其中k称为增量，增量的取值集合称为增量表。

例，无序数组[4,5,8,2,6,8,9,2,4,5,1,6,1,5,4,2] 增量表我们取成“5，3，1”（k的取值集合）

1.当k＝5为，表上的逻辑分组情况为：【1，6，11。16】【2，7，12】【3，8，13】【4，9。14】【5，10，15】（【 】内均是数组的下标值）。
k＝5为的组内进行直接插入排序过程为：
第一组：数组成员分别为“4”，“8”，“1”，“2”。排序后的数组[1,5,8,2,6,2,9,2,4,5,4,6,1,5,4,8]
第二组：数组成员分别为“5”，“9”，“6”。 排序后的数组[1,5,8,2,6,2,6,2,4,5,4,9,1,5,4,8]
第三组：数组成员分别为“8”，“2”，“1”。 排序后的数组[1,5,1,2,6,2,6,2,4,5,4,9,8,5,4,8]
第四组：数组成员分别为“2”，“4”，“5”。 排序后的数组[1,5,1,2,6,2,6,2,4,5,4,9,8,5,4,8]
第五组：数组成员分别为“6”，“5”，“4”。 排序后的数组[1,5,1,2,4,2,6,2,4,5,4,9,8,5,6,8]
此趟运算后数组为[1,5,1,2,4,2,6,2,4,5,4,9,8,5,6,8]

2.当k＝3为，表上的逻辑分组情况为：【1，4，7，10，13，16】【2，5，8，11，14】【3，6，9，12，15】（【 】内均是数组的下标值）。
k＝3为的组内进行直接插入排序过程为：
第一组：数组成员分别为“1”，“2”，“6”，“5”，“8”，“8”
排序后的数组[1,5,1,2,4,2,5,2,4,6,4,9,8,5,6,8]
第二组：数组成员分别为“5”，“4”，“2”，“4”，“6”。
排序后的数组[1,2,1,2,4,2,5,4,4,6,5,9,8,6,6,8]
第三组：数组成员分别为“1”，“2”，“4”，“9”，“6”。
排序后的数组[1,2,1,2,6,2,6,2,4,5,4,6,8,5,9,8]
此趟运算后数组为[1,2,1,2,6,2,6,2,4,5,4,6,8,5,9,8]

3.当k＝1为，表上的逻辑分组情况为：【1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16】（【 】内均是数组的下标值）。即整个表分为一个组，此时对整个表做直接插入表排序，可以发现此趟运算时结点移动是非常少的。此趟运算后数组为有序数组。

通过以上详细的运算过程描述，我们可以发现：当k值很大时，组很小，查找和移动量都很小，随着k值增大，组虽然增大，查找运算量增大了，但最耗时间的移动结点运算量却在减小。总的排序运算耗时是显著的减小，效率成倍提高。

希尔排序法的整体性能与增量表的取值有密切的关系。最佳的增量表取值组合，在数学上还没有证明出来。