希尔排序
希尔排序 (Shell's Sort)是 插入排序 的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
稳定性
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
import java.util.Arrays;
import java.util.Random;//希尔排序 ***是用来优化插入排序***
public class Shell_Sort {public static void main(String[] args) {int a[] = new int[10000];Random r = new Random();for (int i = 0; i < a.length; i++) {a[i] = r.nextInt(10000);//随机产生一个10000以内的整数}int[] b = Arrays.copyOf(a, a.length);//拷贝一份long a1 = System.currentTimeMillis();Arrays.sort(a);//调用java提供的排序 进行排序long b1 = System.currentTimeMillis();shellSort(b);//希尔排序long c1 = System.currentTimeMillis();System.out.println(b1-a1);//java排序的时间（单位是毫秒）System.out.println(c1-b1);//希尔排序的时间（单位是毫秒）boolean isOk = true;//a[200]=200;for (int i = 0; i < b.length; i++) {if (a[i]!=b[i]) {//判断 希尔排序是否出错isOk = false;break;}}System.out.println(isOk);}//希尔排序3：分组+插入排序public static void shellSort(int a[]){//分组--分成gap组，每组a.length/2个元素for (int gap = a.length/2; gap>0; gap/=2) {//进行插入排序for (int i = 0; i < a.length-gap; i++) {int temp = a[i+gap];int j = i;for (; j >=0; j-=gap) {if (temp < a[j]) {a[j+gap] = a[j];}else{break;}}a[j+gap] = temp;}}}
}