1 问题描述
给定一组数据，请使用希尔排序获取这组数据的非降序序列。
2 解决方案
2.1 希尔排序原理简介
希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小,即增量大小为1）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
我们来通过以下示意图，更深入的理解一下具体原理（PS：图中gap为增量）：
package com.liuzhen.chapterFour;
public class ShellSort {
public static void getShellSort(int[] A){
int len = A.length;
int x = 0; //定义进行希尔排序的次数
for(int gap = len/2;gap >= 1;gap = gap/2){ //步长
System.out.print("第"+x+"次希尔排序序列：");
for(int p = 0;p < len;p++)
System.out.print(A[p]+" ");
System.out.println();
x++;
for(int i = 0;i < gap;i++){ //按照步长进行分组
for(int j=i+gap;j < len;j += gap){ //对每个分完的小组进行直接插入排序
if(A[j] < A[j-gap]){
int temp = A[j];
int k = j - gap;
while(k >= 0 && A[k] > temp){
A[k+gap] = A[k];
k -= gap;
}
A[k+gap] = temp;
}
}
}
}
System.out.print("第"+x+"次希尔排序序列：");
for(int p = 0;p < len;p++)
System.out.print(A[p]+" ");
System.out.println();
}
public static void main(String[] args){
int[] A = {49, 38, 65, 97, 26, 13, 27, 49, 55, 4};
getShellSort(A);
}
}
运行结果：
第0次希尔排序序列：49 38 65 97 26 13 27 49 55 4
第1次希尔排序序列：13 27 49 55 4 49 38 65 97 26
第2次希尔排序序列：4 26 13 27 38 49 49 55 97 65
第3次希尔排序序列：4 13 26 27 38 49 49 55 65 97