看一下这两种排序的算法。
- 插入排序，其大致实现如下：
public static void insertionSort(int[] array) {
if (SHOW_INFO) {
System.out.printf("insertionSort: before: %st size=%dn", Arrays.toString(array), array.length);
}
for (int i = 1; i < array.length; ++i) {
int val = array[i];
int pos = i;
// search the target position to insert the waiting value;
for (int j = i - 1; j >= 0; --j) {
// compare val with array[j] to found the insert position
if (val < array[j]) {
array[j + 1] = array[j];
pos = j;
}
}
if (pos != i) {
array[pos] = val;
}
if (SHOW_DETAIL) {
System.out.printf("each sort in insertionSort: NO.[%d] -> %s | val =%dn", i, Arrays.toString(array), val);
}
}
if (SHOW_INFO) {
System.out.printf("insertionSort: after: %st size=%dn", Arrays.toString(array), array.length);
}
}
上面的注释写的比较清楚了。这里的插入，是一种很抽象的思考。把一个数组当成两个数组来看，前面的部分当成已经排好序的数组，后面的当成未排序的数组。然后是从前往后的遍历，每次的遍历都会让前面的有序部分长度+1，让无序的部分-1 ， 然后注意这里的一个实现细节就是，它并不是先遍历一次找到这次应该插入的位置，然后进行移位和插入，而是在遍历中去比较和移位，这样可以省去一次查找插入位置的遍历。
- 然后看一下希尔排序：
public static void shellSort(int[] array) {
if (SHOW_INFO) {
System.out.printf("shell: before: %st size=%dn", Arrays.toString(array), array.length);
}
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; ++i) {
int pos = i;
int val = array[i];
for (int j = i; j - gap >= 0; j -= gap) {
// System.out.println();
if (val < array[j - gap]) {
pos = j - gap; // change target pos
array[j] = array[j - gap];
}
}
if (pos != i) {
array[pos] = val;
}
if (SHOW_DETAIL) {
System.out.printf("shell: in sort:[j=%d] %st size=%dn", i - gap, Arrays.toString(array), array.length);
}
//---
}
}
if (SHOW_INFO) {
System.out.printf("shell: after: %st size=%dn", Arrays.toString(array), array.length);
}
}
希尔排序的思想其实很容易理解，它是通过分组的方式，先分成多个组，然后慢慢合成为一个组。在每个组里面进行插入排序，最后合成为一个组的时候，再进行最后一次的插入排序。这么做是为了，在最后一次的插入排序时，移位的操作能减少。每组中的插入排序实现跟直接插入排序是一致，只是这里的步长不一定是1，可能会大于1；也意味着，你要把这种带有间隔的逻辑上的数组当成一个待排序的数组，然后对这个数组进行排序。
