希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
我们可以看到通过第一趟之后,我们得到的数组是: 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 之后,我们再以3为步长进行排序:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后再以1位步长进行排序,这时候就是个一个简单的插入排序了。
public void sort() {
int number = array.length / 2;
int i;
int j;
int temp;
while (number >= 1) {
for (i = number; i < array.length; i++) {
temp = array[i];
j = i - number;
while (j >= 0 && array[j] > temp) { //需要注意的是,这里array[j] > temp将会使数组从小到到排序。
array[j + number] = array[j];
j = j - number;
}
array[j + number] = temp;
}
number = number / 2;
}
}
Java和Kotlin代码我均放在了GitHub上,欢迎Star!