前言：
数据序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1;
数据序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3;
如果数据序列基本有序，使用插入排序会更加高效。
基本思想：
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
过程：
希尔排序
平均时间复杂度：
java代码实现：
/**
* 希尔（Shell）排序
*
* @author Administrator
*
*/
public class ShellSort { /*
* 数据序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1; 数据序列2：
* 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3;
* 如果数据序列基本有序，使用插入排序会更加高效。
*
* 基本思想： 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
* 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = new int[] { 2, 3, 2, 5, 6, 1, -2, 3, 14, 12, 3, 8, 55, 44,
-10 };
shellSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
} private static void shellSort(int[] arr) {
int incre = arr.length;
while (incre > 0) {
incre = incre / 2;
for (int i = 0; i < incre; i++) {
for (int j = i + incre; j < arr.length; j += incre) {
for (int k = j; k > i; k -= incre) {
if (arr[k] < arr[k - incre]) {
int temp = arr[k];
arr[k] = arr[k - incre];
arr[k - incre] = temp;
} else {
break;
}
}
}
}
}
} }