|
|
希尔排序(Shell Sort)的基本思路为:把直接插入方法分成插入步长由大到小不同的若干趟来进行,一开始步长较大,相当于把序列分成几个子表。对每个子表来说,因为其结点少,直接插入排序的效率会很高。以后各趟逐步减小步长,子表的结点也越来越多,但是子表中的结点已经进行过前一趟的大步长的直接插入排序,有相当多的结点已基本有序。这使得后一趟的插入排序能充分利用前一趟的排序结果。当步长降到1时,只要对基本有序的线性表进行一趟直接插入排序即可。
|
|
|
初次取线性表的一半长度为步长,以后每次减半,直到步长为1,希尔排序的算法如下:
|
|
|
|
|
|
|
|
|
|
|
|
|