算法说明
希尔排序是插入排序的优化版。
插入排序的最坏时间复杂度是O(n2),但如果要排序的数组是一个几乎有序的数列,那么会降低有效的减低时间复杂度。
希尔排序的目的就是通过一个increment(增量)来对数列分组进行交换排序,最终使数列几乎有序,最后再执行插入排序,统计出结果。
通过increment=n/2, 也就是如果9个数的话,增量为4,2,1。 如果是20个数的话,增量就是10,5,2,1。 当increment为1时,其实对几乎有序的数列进行插入排序啦啦。
时间复杂度
O(n2/3)
空间复杂度
O(1)
代码
使用的是Java
/*
* 希尔排序
*/
public class ShellSort {
public static void main(String[] args) {
int[] arrayData = { 5, 9, 6, 7, 4, 1, 2, 3, 8 };
ShellSortMethod(arrayData);
for (int integer : arrayData) {
System.out.print(integer);
System.out.print(" ");
}
} public static void ShellSortMethod(int[] arrayData) {
int i, j, temp = 0;
int increment = arrayData.length;
do {
increment = increment / 2; //增量
for (i = increment; i < arrayData.length; i++) {
if (arrayData[i] > arrayData[i - increment]) { //判断是否要进行插入排序
temp = arrayData[i]; //将要插入的值存放在临时变量中 //这里其实做的就是插入排序,将以增量为步长,往后移动。
//temp > arrayData[j] 这个是要注意的,只会移动比要插入的值小的数字
for (j = i - increment; j >= 0 && temp > arrayData[j]; j -= increment) {
arrayData[j + increment] = arrayData[j];
}
arrayData[j + increment] = temp;
}
}
} while (increment > 0);
}
}
结果
9 8 7 6 5 4 3 2 1