希尔排序
一、基本概念
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。本文主要介绍希尔排序用Java是怎样实现的。
希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定，O(1)的额外空间，时间复杂度为O(N*(logN)^2)。最坏的情况下的执行效率和在平均情况下的执行效率相比相差不多。
二、基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
插入排序的缺陷，多次的移动。
假如一个很小的数据在靠右端的位置上，那么要将该数据排序到正确的位置上，则所有的中间数据都需要向右移动一位。
希尔排序的优点。
希尔排序通过加大插入排序中元素之间的间隔，并对这些间隔的元素进行插入排序，从而使得数据可以大幅度的移动。当完成该间隔的排序后，希尔排序会减少数据的间隔再进行排序。依次进行下去。
间隔的计算
间隔h的初始值为1，通过 h=3*h + 1 来循环计算，直到该间隔大于数组的大小时停止，最大间隔为不大于数组大小的最大值。
间隔的减少
可以通过公式h=(h-1)/3来计算。
三、稳定性及复杂度
希尔排序几乎没有最坏情况，无论是正序、逆序、乱序，所用时间都不是很多，附加储存是O(1)。
时间复杂度：理想情况—O(nlog2n)，最坏情况—O(n2)，稳定性：不稳定。
四、示例代码
import java.util.Random;
public class XierPaixu {
public static void main(String[] args) {
// 定义数组大小为5
final int M = 5;
int[] arr = new int[M];
for (int i = 0; i < M; i++) {
arr[i] = new Random().nextInt(100);// 生成100以内的随机数
}
display(arr);
arr = shellSort(arr);
display(arr);
}
/**
* 希尔排序也是一种插入排序方法，实际上是一种分组插入方法 先取一个小于n的整数d1作为一个增量，把表的全部记录分成d1个组，所有
* 距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序，然后 ，取第二个增量d2(<d1),重复上述的分组和排序，
* 直至所取的dt=1,即所有 记录放在同一组中进行直接插入排序为止
*/
public static int[] shellSort(int[] array) {
int gap = array.length / 2;
int temp;
while (gap > 0) {
for (int i = gap; i < array.length; i++) {
temp = array[i];
int j = i - gap;
while (j >= 0 && temp < array[j]) {
array[j + gap] = array[j];
j = j - gap;
}
array[j + gap] = temp;
}
gap = gap / 2;
}
return array;
}
public static void display(int[] R) {
System.out.println();
for (int i = 0; i < R.length; i++) {
System.out.print(R[i] + "->");
}
}
}
参考链接：
http://blog.csdn.net/morewindows/article/details/6668714
http://blog.verypod.com/shell-sort-using-java/
http://www.java63.com/data_structure/shellsort.html
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.2.1.htm