算法
希尔排序，希尔排序按其设计者唐纳德.希尔(Donald Shell）的名字命名，该算法由1959年公布。也称递减增量排序算法，实质是改进插入排序，改进为分组插入排序。
| 原始数组 | 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循环结束 | |||||||
| 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],跳过 |
| 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],跳过 |
| 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循环结束 |
Java代码实现
int[] insertionSort(int[] num) {
int j;
//步长
int gap;
//步长递减循环
for (gap = num.length; gap > 0; gap /= 2) {
//分组循环
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;
}
网友评论