数组排序-希尔排序(Shell's Sort)

介绍：

    希尔排序是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因Donald Shell于1959年提出而得名。

历史：

    希尔排序按其设计者希尔(Donald Shell)的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner,即包含Marlene Metzner Norton 的名字，但是根据Metzner本人的说法：“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中”。
    希尔排序是基于插入排序的以下两点性值而提出改进方法的：
      1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
      2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

基本思想：

    取一个小于n的整数d1作为一个增量，把文件的全部记录数组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2     该方法实质上是一种分组插入方法。
    比较相隔较远距离(增量)的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。Donald Shell于1959年在以他的名字命名的派苏算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d，对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
    一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
    给定实例的shell排序的排序过程。
    假设待排序的文件有10个记录，其关键字分别是：
     86,11,54,34,53,12,45,81,19,65
    增量序列的取值依次为：
     5,2,1

稳定性：

    由于多次插入排序，我们知道一次插入排序是不稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

排序过程：

    缩小增量
    希尔排序属于插入类排序，是将整个有序序列分割成若干小的子序列分别进行插入排序。
    排序过程：先取一个正整数d1

示例：

package com.lxj.cnblogs;

/**
 * @author 刘小将
 * 测试希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] a = {86,11,54,34,53,12,45,81,19,65};  //声明一个数组并给定值
        printArray(a);                              //输出原始数组到控制台
        int k = 3;
        while (k >= 1){
            shellSort(a,k);
            printArray(a);
            k--;
        }
    }

    /**
     * 希尔排序算法
     * @param a
     * @param k
     */
    public static void shellSort(int[] a,int k){
        int i = 0;
        int j = 0;
        for(i = k;i < a.length;i+=k){
            int temp = a[i];
            if(a[i-k]>a[i]){
                for (j = i-k;j >= 0; j-=k){
                    if(temp

86 11 54 34 53 12 45 81 19 65 
34 11 54 45 53 12 65 81 19 86 
19 11 34 45 53 12 54 81 65 86 
11 12 19 34 45 53 54 65 81 86