算法
希爾排序，希爾排序按其設(shè)計(jì)者唐納德.希爾(Donald Shell）的名字命名，該算法由1959年公布。也稱(chēng)遞減增量排序算法，實(shí)質(zhì)是改進(jìn)插入排序，改進(jìn)為分組插入排序。
| 原始數(shù)組 | 6 | 5 | 4 | 3 | 2 | 1 | 操作 |
|---|---|---|---|---|---|---|---|
| gap=3, i=3, j=3 | 3 | 5 | 4 | 6 | 2 | 1 | num[3]和num[0]值互換 |
| gap=3, i=4, j=4 | 3 | 2 | 4 | 6 | 5 | 1 | num[4]和num[1]值互換 |
| gap=3, i=5, j=5 | 3 | 2 | 1 | 6 | 5 | 4 | num[5]和num[2]值互換 |
| gap=3循環(huán)結(jié)束 | |||||||
| gap=1, i=1, j=1 | 2 | 3 | 1 | 6 | 5 | 4 | num[1]和num[0]值互換 |
| gap=1, i=2, j=2 | 2 | 1 | 3 | 6 | 5 | 4 | num[2]和num[1]值互換 |
| gap=1, i=2, j=1 | 1 | 2 | 3 | 6 | 5 | 4 | num[1]和num[0]值互換 |
| gap=1, i=3, j=3 | 1 | 2 | 3 | 6 | 5 | 4 | num[3]>num[2],跳過(guò) |
| gap=1, i=4, j=4 | 1 | 2 | 3 | 5 | 6 | 4 | num[4]和num[3]值互換 |
| gap=1, i=4, j=3 | 1 | 2 | 3 | 5 | 6 | 4 | num[3]>num[2],跳過(guò) |
| gap=1, i=5, j=5 | 1 | 2 | 3 | 5 | 4 | 6 | num[5]和num[4]值互換 |
| gap=1, i=5, j=4 | 1 | 2 | 3 | 4 | 5 | 6 | num[4]和num[3]值互換 |
| gap=1循環(huán)結(jié)束 |
Java代碼實(shí)現(xiàn)
int[] insertionSort(int[] num) {
int j;
//步長(zhǎng)
int gap;
//步長(zhǎng)遞減循環(huán)
for (gap = num.length; gap > 0; gap /= 2) {
//分組循環(huán)
for (int i = gap; i < num.length; i++) {
int temp = num[i];
//插入排序
for (j = i; j >= gap && temp < num[j - gap]; j -= gap) {
num[j] = num[j - gap];
}
num[j] = temp;
}
}
return num;
}
