希尔排序

排序过程

 

 

基本原理

 

 直接插入排序在处理规模较小、有序程度较高的序列时效率较高，希尔排序以此为出发点，对直接插入排序进行优化，其基本原理为：

    （1）确定增量，将序列从逻辑上划分成若干个子序列。

    （2）使用直接插入排序处理子序列。

    （3）增量缩半，重复上述过程。

一开始增量较大，划分出来的子序列规模较小，使用直接插入排序比较高效；

随着增量的减小，划分出来的子序列规模变大，但是序列有序程序较高，因此，使用直接插入排序依然高效。

 

思考

1、稳定性？
    虽然直接插入排序是稳定的，但希尔排序不是稳定的。