算法

  希尔排序是对直接插入排序的改进，但其本质上仍然是插入排序，只不过它设置了步长，就变成了跨步长的插入排序。当步长为1时，它就是直接插入排序。
  初始时设置步长d为n/2，按照直接插入排序进行，若a[i]<a[i-d]表名a[i]为待排序元素，从后向前与a[i-d],a[i-2d]……比较，若待排序元素小于比较元素，则比较元素向后移位，腾出位置。一趟结束后将待排序元素赋值到空出位置。而后不断更新d=d/2，直到步长为0，排序结束。

例子

仍以序列4,3,1,2,5为例

示例

Codes

package com.fairy.InnerSort;

import java.util.Scanner;
/**
 * 希尔排序
 * @author Fairy2016
 *
 */
public class SheerSort {
    
    public static void sort(int a[], int n) {
        int denSity = n / 2;//步长，初始为n/2
        int i, j;
        while(denSity >= 1) {
            for(i = denSity+1; i <= n; i++) {
                if(a[i] < a[i-denSity]) {
                    a[0] = a[i];//非探针，仅作存储
                    for(j = i-denSity; j > 0 && a[j] > a[0]; j-=denSity) {
                        a[j+denSity] = a[j];//依然是边比较边移位
                    }
                    a[j+denSity] = a[0];//赋值到位置
                }
            }
            denSity /= 2;//更新步长
        }
    }

    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, n);
                Print(a, n);
            }
        }
        scanner.close();
    }
}