最后有改進(jìn)版
前情提要
- 插入排序只在數(shù)據(jù)量小渊胸，數(shù)據(jù)有序程度較高的情況下效率高
- 基于上述這點(diǎn)柑晒，D.L.Shell于1959年提出了 "縮小增量排序"(Diminishing Increment Sort)滞项，是一種插入排序的優(yōu)化排序算法
核心思想
- 不同于插入算法眷茁，希爾算法引入了"增量"-gap筷凤，也可以理解為間隔耸携，用處是棵癣，對數(shù)組進(jìn)行按增量進(jìn)行劃分，對每個(gè)劃分進(jìn)行插入排序夺衍，這是為了滿足插入排序高效的一個(gè)條件：數(shù)據(jù)量小
比如狈谊，
int[] nums = {4, 3, 5, 7, 6, 8, 9, 1, 2};
nums長度為9，最開始設(shè)置gap = nums.length / 2也就是gap = 4沟沙，此時(shí)數(shù)組劃分為{4, 6, 2}, {3, 8}, {5, 9}, {7, 1}河劝，第一組也就是nums[0] = 4，nums[0 + gap] = 6, nums[0 + 2 * gap] = 2矛紫，第二組就是nums[1] = 3, nums[1 + gap] = 8赎瞎，后面以此類推，注意索引不要越界
然后對每個(gè)組進(jìn)行插入排序颊咬，四個(gè)組排完分別是{2, 4, 6}, {3, 8}, {5, 9}, {1, 7}务甥，此時(shí)數(shù)組nums = {2, 3, 5, 1, 4, 8, 9, 7, 6}可以明顯看出比原始數(shù)組更符合插入排序高效的第二個(gè)條件：數(shù)據(jù)有序程度較高
- 注意：分組只是邏輯上的分組，在實(shí)際操作中只是特殊處理索引喳篇，比如遍歷一個(gè)分組敞临，
for (int i = 0; i < nums.length; i += gap)類似于這樣，把gap當(dāng)成"步長"去遍歷數(shù)組麸澜，就能"分出"每個(gè)組 - 第一次分組插入排序之后挺尿，把步長
gap /= 2砍掉一半，這樣一下，下一輪每個(gè)分組的元素?cái)?shù)量就翻倍(考慮到奇數(shù)個(gè)编矾，所以只能是近似翻倍)
接著例子熟史，第二輪分組，
{2, 5, 4, 9, 6}, {3, 1, 8, 7}窄俏，分組插入排序后{2, 4, 5, 6, 9}, {1, 3, 7, 8}以故，數(shù)組{2, 1, 4, 3, 5, 7, 6, 8, 9}，而第三輪時(shí)步長gap = 1就變成普通插入排序裆操，但這是數(shù)據(jù)有序性較高怒详，所以性能提高不少
算法實(shí)現(xiàn)
完整代碼
- 建議先復(fù)制完整代碼再對照著看具體步驟
public class ShellSortDemo {
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private static void shellSort(int[] nums) {
for (int gap = nums.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < nums.length; i++) {
for (int j = i; j >= gap; j -= gap) {
if (nums[j] < nums[j - gap]) {
swap(nums, j, j - gap);
} else {
break;
}
}
}
}
}
public static void main(String[] args) {
// int[] nums = {4, 5, 2, 3, 6, 7, 9, 8, 1, 4, 5, 1, 7, 9, 6, 5, 8};
int[] nums = new int[2000000];
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 10000);
}
// System.out.println(Arrays.toString(nums));
long startTime = System.currentTimeMillis();
shellSort(nums);
long endTime = System.currentTimeMillis();
System.out.println("耗時(shí): " + (endTime - startTime) + "ms" );
// System.out.println(Arrays.toString(nums));
}
}
具體步驟
整個(gè)過程其實(shí)在草稿紙上用一個(gè)簡單數(shù)組寫一下過程就很清晰了
-
void swap(int[] nums, int i, int j)是輔助方法，用于交換兩個(gè)數(shù) -
void shellSort(int[] nums)是算法主體-
for (int gap = nums.length / 2; gap > 0; gap /= 2)最外層循環(huán)踪区，設(shè)置每一次大循環(huán)的步長昆烁，更新時(shí)砍掉一半，直到步長為0 -
for (int i = gap; i < nums.length; i++)第二層循環(huán)結(jié)合for (int j = i; j >= gap; j -= gap)第三層循環(huán)就是對每個(gè)分組進(jìn)行插入排序- 比如還是這個(gè)數(shù)組
{4, 3, 5, 7, 6, 8, 9, 1, 2}缎岗，i = gap(i = 4), j = i = 4静尼，此時(shí)就是對第一個(gè)分組{4, 6, 2}進(jìn)行插入排序的第一次，通過判段if (nums[j] < nums[j - gap])也就是比較第一個(gè)組的4和6传泊，如果后者小鼠渺，就交換兩者位置swap(nums, j, j - gap)，否則跳出最內(nèi)層循環(huán)眷细，因?yàn)榇藭r(shí)第一個(gè)分組的第一次插入排序已經(jīng)完成 - 然后
i++ == 5, j = i = 5拦盹，也就是對第二個(gè)分組{3, 8}進(jìn)行插入排序，后面i更新后執(zhí)行的操作以此類推 - 等到第二層循環(huán)的
i = 8溪椎，第三層j = i = 8普舆，則是第一組接著第一次插入排序后的第二次，這時(shí)會比較2和6校读，發(fā)現(xiàn)兩者需要交換沼侣，交換后再比較4和2發(fā)現(xiàn)又得交換，然后第一分組的插入排序就完成了
- 比如還是這個(gè)數(shù)組
-
測試
用隨機(jī)生成的數(shù)據(jù)進(jìn)行測試歉秫，取平均值
4萬個(gè)數(shù)據(jù)蛾洛，用時(shí)9-13毫秒
40萬個(gè)數(shù)據(jù)，用時(shí)90-110毫秒
400萬個(gè)數(shù)據(jù)雁芙，用時(shí)1300-1500毫秒
4000萬個(gè)數(shù)據(jù)轧膘，用時(shí)16000-20000毫秒(16-20秒)
而插入排序
4萬個(gè)數(shù)據(jù)，用時(shí)900-1000毫秒
40萬個(gè)數(shù)據(jù)却特，用時(shí)76000-100000毫秒(70多到100秒)
數(shù)量級再往上都沒那個(gè)耐心等它跑完了
明顯看到希爾排序的效率是高很多很多
再測試了一下快速排序扶供，堆排序這兩種平均時(shí)間復(fù)雜度是
O(n*logn)的排序算法筛圆，發(fā)現(xiàn)希爾排序與這兩種算法用時(shí)幾乎是一樣的裂明，不過希爾排序的平均時(shí)間復(fù)雜度至今仍不能給出確定的答案(O(n*logn), O(n^(1.3)), O(n^(1.5)))，所以就先不管了
---------------------------華麗的分割線---------------------------------
用類似于上篇文章 插入排序 后面所講的改進(jìn)，將希爾排序修改為以下實(shí)現(xiàn)闽晦，性能提高到原來的
140% - 200%
private static void shellSort(int[] nums) {
for (int gap = nums.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < nums.length; i++) {
int insertValue = nums[i];
int insertIndex = i - gap;
while (insertIndex >= 0 && nums[insertIndex] > insertValue) {
nums[insertIndex + gap] = nums[insertIndex];
insertIndex -= gap;
}
if (insertIndex != i - gap) {
nums[insertIndex + gap] = insertValue;
}
}
}
}
