1.概念:
希尔排序是对直接插入排序的改进,改进的着眼点:
1)若待排序记录按关键字值基本有序时,直接插入排序的效率可以大大提高;
2)由于直接插入排序算法简单,则在待排序记录数量n较小时效率也很高。
希尔排序的基本思想:
将整个待排序记录分割成若干个子序列,在子序列内分别进行直接插入排序,待整个序列中的记录基本有序时,对全体记录进行直接插入排序。
2.实现:
首先选择一个整数gap < n(待排序的记录数)作为间隔,将全部序列分为若干个子序列,所有距离为gap的记录放在同一个子序列中;在每个子序列内分别进行直接插入排序;然后缩小间隔gap,例如取gap=gap/2(gap=gap/3+1);重复上述的子序列划分和排序工作,直到最后取gap=1,将所有记录放在同一个序列中排序为止。
3.算法性能:
希尔排序开始时增量较大,每个子序列中的记录个数较少,从而排序速度较快;当增量逐渐变小时,虽然每个子序列中记录个数逐渐变多,但整个序列已基本有序,排序速度也较快。
希尔排序的时间性能是所取增量的函数,而到目前为止尚未有人求得一种最好的增量序列。
研究表明,当n在某个特定范围内,希尔排序所需的比较次数和记录的移动次数约为n的1.3次方;当n趋于无穷时可减少到𝒏(𝒍𝒐𝒈𝟐𝒏)²。希尔排序是一种不稳定的排序方法
4.C++程序示例:
1 | #include <iostream> |
运行结果: