簡(jiǎn)單插入排序存在一定的問(wèn)題：
當(dāng)待插入的數(shù)比較小時(shí)倾贰，會(huì)進(jìn)行多次比較并進(jìn)行多次的后移賦值操作，影響效率。
希爾排序也是一種插入排序，是希爾（Donald Shell）在1959年提出的一種排序算法凿歼。它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)后的一個(gè)更高效的版本，也稱為縮小增量排序冗恨。
希爾排序基本思想
希爾排序是把元素按照下標(biāo)的增量進(jìn)行分組答憔，對(duì)每組元素直接使用插入排序。這樣隨著增量的逐步減少掀抹，數(shù)組會(huì)越來(lái)越有序虐拓，當(dāng)增量減至1時(shí)，執(zhí)行完該輪排序后傲武，希爾排序結(jié)束蓉驹。
圖示與代碼
根據(jù)對(duì)有序序列在插入時(shí)采用的方法不同，希爾排序又可分為交換法和移動(dòng)法揪利。
希爾排序 - 交換法
希爾排序-交換法.png
public class ShellSort {
public static void main(String[] args) {
int[] arr = {5, 21, 9, 6, 10, 2, 16};
int len = arr.length;
int temp = 0;
int count = 0;
System.out.println("原數(shù)組：" + Arrays.toString(arr));
for (int gap = len / 2; gap > 0; gap /= 2) {
// 分成的組數(shù)為gap
for (int i = gap; i < len; i++) {
// 遍歷各組中所有的元素戒幔，步長(zhǎng)gap
for (int j = i - gap; j >= 0; j -= gap) {
// 如果當(dāng)前元素大于加上步長(zhǎng)后的那個(gè)元素，交換
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
System.out.println("第"+(++count)+"輪："+Arrays.toString(arr));
}
}
}
打印結(jié)果：
原數(shù)組：[5, 21, 9, 6, 10, 2, 16]
第1輪：[5, 10, 2, 6, 21, 9, 16]
第2輪：[2, 5, 6, 9, 10, 16, 21]
希爾排序 - 移動(dòng)法
該方法跟交換法大體一樣土童，只是進(jìn)行組內(nèi)排序時(shí)采用了移動(dòng)法（可看成一個(gè)插入排序）
public class ShellSort1 {
public static void main(String[] args) {
int[] arr = {5, 21, 9, 6, 10, 2, 16};
int len = arr.length;
int count = 0;
System.out.println("原數(shù)組：" + Arrays.toString(arr));
// 增量為gap，并逐步縮小增量
for (int gap = len / 2; gap > 0; gap /= 2) {
// 從第gap個(gè)元素工坊，逐個(gè)對(duì)其所在組進(jìn)行直接插入排序
for (int i = gap; i < len; i++) {
int j = i;
int temp = arr[j];
while (j - gap >= 0 && temp < arr[j - gap]) {
// 移動(dòng) 這里和插入排序是一樣的原理
arr[j] = arr[j - gap];
j -= gap;
}
// while退出后就給temp找到了插入位置
arr[j] = temp;
}
System.out.println("第"+(++count)+"輪："+Arrays.toString(arr));
}
}
}
