=================
== Time Stream ==
=================
一个小学生

算法之希尔排序学习

希尔排序算法重新学习。

插入排序可以类比打扑克牌时整理扑克牌顺序的场景,插入排序算法的思想是:将待排序的序列分为两段,前面一段是排序好的序列,后面一段是未排序的序列,每次只拿一个元素,将这个元素按照其值的大小插入到前面一段已经排序好的序列中去。

插入排序算法有以下几种:

  • 直接插入排序
  • 二分插入排序
  • 希尔排序

希尔排序算法

希尔排序又称缩小增量排序,是进行分组的直接插入排序。

希尔排序是对直接插入排序的优化,通过分析直接插入排序算法可知道:

  • 直接插入排序如果序列接近有序,则效率更高,时间复杂度接近O(n)
  • 直接插入排序的序列元素越少,排序效率越高

基于这两点,希尔排序对直接插入排序进行了优化,希尔排序算法描述如下:

  1. 将原序列进行分组,对每一组分别进行直接插入排序,这样每个组的元素就会比较少,排序速度快。分组并不是真的分出多个序列来,是在原来的序列上,将相隔一段距离(称为增量)的若干个元素在逻辑上归为一组。
  2. 在每一组都排序完后,这些组内都是有序的小序列,从整体上来看整个序列也比原序列会有序很多。经过把所有组都进行一次排序之后,将相隔的距离(称为增量)减少,这样又分为了若干个小组,但这次组里的元素比之前的元素多,并且也会更有序,这样继续再次排序,然后重复分组、排序直到结束。
  3. 距离的选择,也就是增量的选择,通常第一次是原数据序列的长度的一半,之后每次选择增量都是之前增量的一半,最后增量会变成1,也就是最后只剩一组,这一组内包含序列全部元素,但是这时候元素的有序性会更好,最后经过一次直接插入排序就能完成排序。
  4. 关于距离选择,也不并不是如上面所说必须要是每次的一半,也可以是其他规则。

希尔排序代码示例

/**
 * 希尔排序
 */
public class ShellSort {

    public void shellSort(Integer[] source) {
        // 先确定增量,隔着相同增量的元素都在一个组里
        for (int gap = source.length >> 1; gap > 0; gap >>= 1) {
            // 每个组进行插入排序
            for (int i = gap; i < source.length; i++) {
                Integer temp = source[i];
                int j = 0;
                for (j = i; j >= gap && temp < source[j - gap] ; j = j - gap) {
                    source[j] = source[j - gap];
                }
                source[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
        System.out.println("before: " + Arrays.asList(array));
        new ShellSort().shellSort(array);
        System.out.println("after: " + Arrays.asList(array));
    }
}

希尔排序算法分析

时间复杂度

希尔排序的执行时间依赖于增量序列。但效率还是优于直接插入排序的。一般来说:

  • 最好情况,时间复杂度$O(n^{1.5})$
  • 最坏情况,时间复杂度$O(n^2)$

空间复杂度

算法中使用一个temp变量占用一个存储单元,空间复杂度为O(1)

算法的稳定性

希尔排序中小组的直接插入排序是稳定的,但是组与组是不同的插入排序,不同的插入排序过程中相同元素可能会被移动,因此希尔排序是不稳定的。

适用场景

  • 希尔排序是对直接插入排序的优化,所以适用于大型数组。

参考内容

  • 《数据结构(Java版)》