希尔排序是对直接插入排序的改进,其实质就是分组插入排序,该方法又称缩小增量排序。 该算法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的一系列元素组成)分别进行直接插入排序,然后依次缩减增量再进行排序,直到增量为1(即对全体数据元素进行一次直接插入排序)。 希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。
希尔排序图示(来自百度图片,若侵权,请告知):
在实现希尔排序的时候,我们先看一眼直接插入排序的实现,然后在看希尔排序的实现,我们会发现,其实希尔排序就比直接插入排序多了一个基于步长的外层循环。 直接插入排序Java版:
public static void insertSort(int[] numbers) {
for (int i = 1; i < numbers.length; i++) {
int number = numbers[i];
int j = i - 1;
while (j >= 0 && numbers[j] > number) j--;
for (int k = i; k > j + 1; k--)
numbers[k] = numbers[k - 1];
numbers[j + 1] = number;
}
}
希尔排序Java版:
public static void shellSort(int[] numbers) {
for (int gap = numbers.length / 2; gap > 0; gap /= 2) {
for (int i = 1; i < numbers.length; i += gap) {
int number = numbers[i];
int j = i - gap;
while (j >= 0 && numbers[j] > number) j -= gap;
for (int k = i; k > j + gap; k -= gap)
numbers[k] = numbers[k - gap];
numbers[j + gap] = number;
}
}
}
可以看到,希尔排序就增加了一个外层的基于步长的循环,然后内部是直接插入排序,只不过循环的增量不是1,而是外层的那个gap步长。