排序_插入排序之希尔排序(缩小增量排序)

概述

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

代码实现

/**
 * 基本思想：
 * 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
 * 所有距离为d1的倍数的记录放在同一个组中。
 * 先在各组内进行直接插入排序；然后，取第二个增量d2<d1
 * 重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，
 * 即所有记录放在同一组中进行直接插入排序为止。
 * 
 * 
 * 
 * 
 * @author yeoggc
 *
 */
public class 希尔排序 {

    private void shellSort(int[] array) {

        int gap = array.length / 2;// 初始化gap为数组长度/2

        while (1 <= gap) {// 中止条件是gap<1

            // 对步长为gap的元素进行分组
            // 交替的对每组进行直接插入排序
            for (int i = gap; i < array.length; i++) {

                int temp = array[i];// 待排序的数据
                int j = 0;// 有序区中待比较元素的下标，初始时，从有序区中最后一个元素开始比较起

                // 对步长为 gap 的元素组进行排序
                for (j = i - gap; j >= 0 && temp < array[j]; j = j - gap) {
                    array[j + gap] = array[j];
                }

                array[j + gap] = temp;

            }
            System.out.format("gap = %d:\t", gap);
            printAll(array);
            gap = gap / 2; // 减小增量
        }

    }

    public static void main(String[] args) {
        int[] array = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };

        // 调用希尔排序方法
        希尔排序 shell = new 希尔排序();
        System.out.print("排序前:\t\t");
        shell.printAll(array);
        shell.shellSort(array);
        System.out.print("排序后:\t\t");
        shell.printAll(array);
    }

    // 打印完整序列
    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + "\t");
        }
        System.out.println();
    }

}

算法分析

这例子希尔排序的步长选择都是从n/2开始，每次再减半，直到最后为1。这并不是最高效的步长选择。

希尔排序是不稳定的：我们知道一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，即希尔排序中相等数据可能会交换位置。

希尔排序的平均时间复杂度为O(nlog2n)。

直接插入排序和希尔排序的比较

直接插入排序是稳定的；而希尔排序是不稳定的。
直接插入排序更适合于原始记录基本有序的集合。
希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。
直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。