排序之一：希尔排序

• 介绍
  希尔排序的原理跟插入排序差不多，但是希尔排序可以减少数据搬移的次数。排序的原则是将数据区分成特定间隔的几个小区块，以插入排序法完成区块内的数据后再渐渐减少间隔的距离。
• 演示
  代码如下：

private static void shellSort() {
    int data[] = {6, 4, 8, 1, 3, 7, 2, 9, 5};
    int i, j, k = 1, tmp, jmp = data.length / 2;
    while (jmp != 0) {
        for (i = jmp; i < data.length; i++) {
            tmp = data[i];
            j = i - jmp;
            while (j >= 0 && tmp < data[j]) {
                data[j + jmp] = data[j];
                j = j - jmp;
            }
            data[jmp + j] = tmp;
        }
        jmp = jmp / 2;
    }
}

排序结果：

希尔排序结果.png

• 分析

1. 在任何情况下的时间复杂度均为P(n³/n²);（3/2的这个幂打不上）；
2. 是稳定排序；
3. 只需要一个额外空间，所以空间复杂度是最佳的；
4. 此排序法适用于数据大部分都已排序完成的情况。

其他排序：插入排序、选择排序、冒泡排序、快速排序、基数排序