插入排序與希爾排序
前言
本篇文章是排序算法系列的第二篇帕翻，學(xué)習(xí)插入排序和希爾排序
后面這段話將作為排序算法系列博客每一篇的開(kāi)頭：
為避免文中過(guò)多贅述似芝，寫在最前面：
- 接下來(lái)所有的排序算法講解中漓穿，無(wú)論是思路梳理，還是代碼實(shí)現(xiàn)，都是最終實(shí)現(xiàn)從小到大排序疙渣，從大到小可以學(xué)會(huì)后自行類推。
- 都是使用int數(shù)組進(jìn)行排序堆巧，數(shù)據(jù)總量為n
插入排序
核心理念
插入排序妄荔，是將排序問(wèn)題轉(zhuǎn)化成了一個(gè)插入數(shù)據(jù)的問(wèn)題泼菌，假設(shè)有一個(gè)亂序的數(shù)組，我們創(chuàng)建一個(gè)新的數(shù)組啦租，讓它始終都是一個(gè)有序數(shù)組哗伯，也就是每添加一個(gè)數(shù)據(jù)進(jìn)入數(shù)組，都將它按照有序的排列插入進(jìn)數(shù)組篷角。
根據(jù)這個(gè)想法焊刹，可以將無(wú)序的待排序數(shù)組，挨個(gè)取出來(lái)内地，按照那個(gè)始終有序的數(shù)組規(guī)則插入進(jìn)有序數(shù)組伴澄，當(dāng)待排序數(shù)組的所有數(shù)字都插入完成，就完成了排序阱缓。
這樣解釋起來(lái)非凌，并不難理解，也確實(shí)能夠完成排序
我在第一次學(xué)習(xí)到這里的時(shí)候荆针，就自己思考去寫代碼了敞嗡，創(chuàng)建了一個(gè)新的數(shù)組，將老數(shù)組的元素挨個(gè)取出來(lái)插入新數(shù)組航背，最終完成排序喉悴，下面這個(gè)就是我當(dāng)初寫的代碼，最終的結(jié)果確實(shí)正確的給數(shù)組排序了玖媚，但我看了書(shū)上標(biāo)準(zhǔn)的實(shí)現(xiàn)后箕肃，震驚了，書(shū)中的實(shí)現(xiàn)并沒(méi)有創(chuàng)建新的數(shù)組今魔。
所以不要著急去看下面這個(gè)代碼（你肯定不會(huì)看勺像，因?yàn)槲乙矝](méi)怎么寫注釋??），容我在后面先分析一下為什么不用創(chuàng)建新的數(shù)組错森，真正最完美的插入排序思路
/**
* 自己思考時(shí)寫的吟宦，創(chuàng)建了一個(gè)新的數(shù)組去插入，但其實(shí)沒(méi)必要
*/
public static void insertSort1(int[] arr){
//新數(shù)組涩维，有序插入無(wú)序數(shù)組的數(shù)據(jù)
int[] sortArr = new int[arr.length];
sortArr[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
for (int j = i-1; j >= 0; j--) {
if (sortArr[j]>arr[i]){
sortArr[j+1] = sortArr[j];
if (j==0){
sortArr[j] = arr[i];
}
}else {
sortArr[j+1] = arr[i];
break;
}
}
}
arr = sortArr;
}
我們來(lái)分析一下殃姓，一個(gè)有序數(shù)組，如何保持插入數(shù)據(jù)后依然有序：
- 首先我們已知當(dāng)前數(shù)組是有序的瓦阐，從小到大排列
- 那么我們新的要插入的數(shù)據(jù)蜗侈，有兩種辦法找到自己的位置
- 第一種是從前往后遍歷有序數(shù)組，挨個(gè)比較與待插入數(shù)字的大小睡蟋，當(dāng)找到第一個(gè)大于等于待插入數(shù)據(jù)的宛篇，這里就是待插入數(shù)據(jù)的位置，之前從這個(gè)位置開(kāi)始的所有數(shù)據(jù)都要后移一位
- 第二種是從后向前遍歷有序數(shù)組薄湿，挨個(gè)比較與待插入數(shù)字的大小，當(dāng)找到第一個(gè)小于等于待插入數(shù)據(jù)的，這個(gè)數(shù)字的后一個(gè)就是待插入數(shù)據(jù)的位置豺瘤，之前從這個(gè)位置開(kāi)始的所有數(shù)據(jù)都要后移一位
- 可以發(fā)現(xiàn)關(guān)鍵點(diǎn)三個(gè)步驟吆倦，第一步找到待插入數(shù)據(jù)的位置，第二步將從該位置開(kāi)始的數(shù)據(jù)全部后移一位坐求，第三步將待插入數(shù)據(jù)插入找到的位置
- 那么應(yīng)該從前向后遍歷還是從后向前遍歷呢蚕泽，如果從前向后，執(zhí)行第二步回避從后向前麻煩桥嗤，因?yàn)槿绻岩粋€(gè)數(shù)字后移须妻，需要提前將他的下一個(gè)數(shù)字用臨時(shí)變量存起來(lái)，否則就被直接覆蓋了泛领，而從后向前只需要最后一個(gè)數(shù)字的后面有一個(gè)空位即可順利的挨個(gè)后移荒吏，而且可以一邊尋找位置一邊就后移，當(dāng)發(fā)現(xiàn)遍歷到的數(shù)字大于待插入數(shù)字渊鞋，就直接后移绰更，再遍歷下一個(gè)，直到找到第一個(gè)小于待插入數(shù)據(jù)的锡宋，將數(shù)字插入到這個(gè)位置的后一個(gè)就完成了
- 這樣一想儡湾，有序數(shù)組新插入一個(gè)數(shù)據(jù)，只需要在最后邊多一個(gè)空位执俩，那我們的插入排序其實(shí)可以不用創(chuàng)建新的數(shù)組
- 我們從前向后遍歷整個(gè)無(wú)序數(shù)組徐钠，讓數(shù)組從第一個(gè)到遍歷到的數(shù)據(jù)保持有序，每遍歷到下一個(gè)數(shù)字就將它插入到前面的有序部分去役首，被遍歷到的數(shù)字抽出來(lái)正好可以提供那個(gè)需要的空位
- 我們其實(shí)可以從無(wú)序數(shù)組的第二個(gè)開(kāi)始遍歷尝丐，因?yàn)樗那斑呏挥幸粋€(gè)數(shù)字，必然是有序的宋税，從第二個(gè)數(shù)字開(kāi)始向前插入即可
接下來(lái)用代碼實(shí)現(xiàn)一下摊崭，外層循環(huán)從第二個(gè)開(kāi)始向后遍歷，內(nèi)層循環(huán)從第i個(gè)開(kāi)始向前遍歷
/**
* 將之前那個(gè)自己的實(shí)現(xiàn)代碼優(yōu)化后杰赛，排序過(guò)程只用原來(lái)的數(shù)組
*/
public static void insertSort2(int[] arr){
//從第二個(gè)數(shù)開(kāi)始遍歷
for (int i = 1; i < arr.length; i++) {
//待插入的數(shù)存進(jìn)臨時(shí)變量（相當(dāng)于空出一個(gè)位置方便后移）
int temp = arr[i];
//是否在循環(huán)內(nèi)找到了位置
boolean index = false;
//內(nèi)層遍歷待插入數(shù)前面的所有數(shù)去找到他的位置
for (int j = i-1; j >= 0; j--) {
/*
* 依次向下標(biāo)i之前的數(shù)據(jù)呢簸，挨個(gè)比較
* 如果當(dāng)前位置數(shù)據(jù)比自己大就將其后移
* 直到找到比自己小的，說(shuō)明這個(gè)數(shù)的下一個(gè)位置就是屬于待插入數(shù)據(jù)的乏屯，將數(shù)據(jù)插入后跳出內(nèi)層循環(huán)
* 如果一直到索引0的位置還沒(méi)有找到比自己小的根时，說(shuō)明自己就是最小的了，將數(shù)據(jù)插入即可
*/
if (arr[j]>temp){
arr[j+1]=arr[j];
}else {
arr[j+1] = temp;
index = true;
break;
}
}
//如果沒(méi)有在循環(huán)結(jié)束前找到辰晕，說(shuō)明這個(gè)數(shù)字在前邊是最小的蛤迎，直接插入在索引0的位置
if (!index){
arr[0] = temp;
}
}
}
上面這個(gè)代碼，還不是最優(yōu)的寫法含友，但其實(shí)效率上和數(shù)中的標(biāo)準(zhǔn)實(shí)現(xiàn)替裆，已經(jīng)沒(méi)有什么區(qū)別了校辩，我還是先把這段代碼貼出來(lái)，因?yàn)檫@個(gè)讀起來(lái)應(yīng)該能更好理解一些
下面再看看書(shū)中的標(biāo)準(zhǔn)實(shí)現(xiàn)辆童，內(nèi)層循環(huán)用了while的宜咒，更簡(jiǎn)短更優(yōu)雅的代碼
/**
* 表中的寫法——內(nèi)層用了while
*/
public static void insertSort3(int[] arr){
for (int i = 1; i < arr.length; i++) {
//臨時(shí)遍歷保存待插入的數(shù)
int insertVal = arr[i];
//要遍歷的數(shù)索引
int insertIndex = i-1;
/*
* 1.insertIndex>=0保證插入位置索引不越界
* 2.insertVal < arr[insertIndex]表示待插入數(shù)據(jù)還沒(méi)有找到應(yīng)該插入的位置
* 滿足這兩個(gè)條件，需要將arr[insertIndex]后移把鉴，insertIndex--
*/
while (insertIndex>=0 && insertVal < arr[insertIndex]){
arr[insertIndex+1] = arr[insertIndex];
insertIndex--;
}
//退出while循環(huán)后故黑，說(shuō)明當(dāng)前insertIndex+1就是待插入數(shù)據(jù)的位置
arr[insertIndex+1] = insertVal;
}
}
其實(shí)這個(gè)while也可以用for來(lái)寫
/**
* 看了標(biāo)準(zhǔn)寫法的while后
* 進(jìn)一步優(yōu)化我自己的代碼，將循環(huán)中的if庭砍，提到for循環(huán)的條件表達(dá)式中
*/
public static void insertSort4(int[] arr){
long start = System.currentTimeMillis();
//從第二個(gè)數(shù)開(kāi)始遍歷
for (int i = 1; i < arr.length; i++) {
//待插入的數(shù)存進(jìn)臨時(shí)變量
int temp = arr[i];
//記錄待插入數(shù)應(yīng)該插入的位置(初始化為要被插入的數(shù)據(jù)本身的位置)
int index = i;
//內(nèi)層遍歷待插入數(shù)前面的所有數(shù)去找到他的位置
for (int j = i-1; j >= 0 && arr[j]>temp; j--) {
/*
* 依次向下標(biāo)i之前的數(shù)據(jù)场晶，挨個(gè)比較
* 如果當(dāng)前位置數(shù)據(jù)比自己大就將其后移，記錄下當(dāng)前這個(gè)位置的索引
* 后續(xù)有兩種情況會(huì)退出這個(gè)循環(huán)：
* 1.當(dāng)前要遍歷的數(shù)字比自己小時(shí)就不會(huì)再進(jìn)入循環(huán)了怠缸，而那個(gè)上一次循環(huán)中記錄下來(lái)的索引位置就是要插入的位置
* 2.如果一直到索引0的位置還沒(méi)有找到比自己小的诗轻，下一次也會(huì)退出循環(huán)，上一次循環(huán)中記錄的索引位置必然為0凯旭，也是要插入的位置
*/
arr[j+1]=arr[j];
index = j;
}
//綜上只要是退出了循環(huán)概耻，index就是指向數(shù)據(jù)要插入的位置，直接插入就好
arr[index] = temp;
}
System.out.println("總執(zhí)行時(shí)長(zhǎng)(毫秒)："+(System.currentTimeMillis()-start));
// System.out.println(Arrays.toString(arr));
}
我一共貼出了四段代碼罐呼，我們來(lái)比較一下他們的排序效率
首先已經(jīng)測(cè)試過(guò)了鞠柄，排序結(jié)果都是沒(méi)有問(wèn)題的
還是8w隨機(jī)數(shù)據(jù)，分別排序五次嫉柴，記錄排序時(shí)間
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
-
insertSort1()厌杜，這個(gè)是最初自行實(shí)現(xiàn)的，用到兩個(gè)數(shù)組的代碼
2175计螺、1334夯尽、1877、2039登馒、1911 （可以發(fā)現(xiàn)并不穩(wěn)定匙握，在1.3s到2.1s之間）
-
insertSort2()，這個(gè)是自己優(yōu)化成只使用一個(gè)數(shù)組后的代碼
483陈轿、492圈纺、470、471麦射、471 （比起兩個(gè)數(shù)組效率提升四倍左右）
-
insertSort3()蛾娶，這是書(shū)中的標(biāo)準(zhǔn)實(shí)現(xiàn)
434、463潜秋、454蛔琅、443、470 （比自己的代碼效率上稍有提升）
-
insertSort4()峻呛，說(shuō)這個(gè)是看了標(biāo)準(zhǔn)實(shí)現(xiàn)后罗售，內(nèi)層繼續(xù)使用for但優(yōu)化的更簡(jiǎn)潔后的代碼
470辜窑、457、466莽囤、473谬擦、468（效率介于2、3之間）
2朽缎、3、4效率對(duì)比實(shí)在不太明顯谜悟，改為20w數(shù)據(jù)測(cè)試
2： 2943话肖、2934、2930葡幸、2981最筒、2925
3： 2820、2837蔚叨、2843床蜘、2828、2837
4： 2953蔑水、2958邢锯、2957、2950搀别、2935
確實(shí)還是標(biāo)準(zhǔn)寫法效率上有一定的優(yōu)勢(shì)
拆解來(lái)看丹擎，標(biāo)準(zhǔn)寫法使用了while的優(yōu)勢(shì)就在下面
while執(zhí)行一句：index--；
用for再怎么優(yōu)化這里也是兩句：j--歇父；index = j蒂培；
希爾排序
核心理念
希爾排序是在插入排序的基礎(chǔ)上進(jìn)行的優(yōu)化
首先來(lái)說(shuō)一下插入排序有一個(gè)什么樣的問(wèn)題
對(duì)插入排序來(lái)說(shuō)，我們分析一下它最好情況和最壞情況排序速度差別有多大
最好情況：待排序數(shù)組已經(jīng)是有序的
最壞情況：就是待排序數(shù)組正好是逆序的
8w數(shù)據(jù)測(cè)試排序來(lái)看榜苫，隨機(jī)數(shù)組插入排序大概450毫秒左右完成排序护戳，最壞情況則需要平均950毫秒左右，而最好情況只需要1-2毫秒
可以見(jiàn)得垂睬，2毫秒到950毫秒媳荒，差距非常之大
這種情況產(chǎn)生的原因在于，如果很小的數(shù)字在很靠后的位置羔飞，插入排序每次只能將數(shù)據(jù)移動(dòng)一位來(lái)從最后面移動(dòng)到最前面
有沒(méi)有什么辦法可以解決這個(gè)問(wèn)題呢肺樟？
有一個(gè)叫做希爾的人，想到了辦法逻淌，用分組的方式么伯，增加移動(dòng)的步長(zhǎng)，分組越多移動(dòng)的步長(zhǎng)越大
最多分成兩兩一組也就是n/2組
比如用一個(gè)數(shù)組舉例[5卡儒，8田柔，12俐巴，4，15硬爆，1欣舵，7，6]
將它分成四組缀磕，第一個(gè)和第五個(gè)缘圈，第二個(gè)和第六個(gè)，第三個(gè)和第七個(gè)袜蚕，第四個(gè)和第八個(gè)
分別把他們想象成一個(gè)數(shù)組進(jìn)行插入排序糟把，排序后會(huì)變成下面的樣子
[5，1牲剃，7遣疯，22，4凿傅，8缠犀，12，6]
雖然沒(méi)有完成排序聪舒，但是偏小一些的數(shù)字被很快的移動(dòng)到了更靠前的位置
如果再將分組數(shù)降低為上一次的1/2辨液，也就是分為2組，第一個(gè)第三個(gè)第五個(gè)第七個(gè)一組过椎，第二個(gè)第四個(gè)第六個(gè)第八個(gè)一組室梅，再次對(duì)兩組分別進(jìn)行插入排序后如下
[5，1疚宇，7亡鼠，4，12敷待，6间涵，15，8]
這兩次過(guò)后雖然還是沒(méi)有排序完成榜揖，但是整個(gè)數(shù)組更加趨向于有序了
分為兩組后勾哩，再縮小分組數(shù)為之前的1/2，就是分為1組了举哟，相當(dāng)于對(duì)全部進(jìn)行插入排序
開(kāi)始有點(diǎn)抽象思劳，有人就有疑惑了，那不還是插入排序嗎妨猩，接著向后分析
比較最開(kāi)始的數(shù)組和現(xiàn)在的數(shù)組
[5潜叛，8，12，4威兜，15销斟，1，7椒舵，6]
[5蚂踊，1，7笔宿，4犁钟，12，6措伐，15特纤，8]
發(fā)現(xiàn)更多小一些的數(shù)字到了更前面，大一點(diǎn)的數(shù)字到了更后面
那么之前的這些操作侥加，相當(dāng)于將本來(lái)要每次移動(dòng)一位移動(dòng)到這里來(lái)的數(shù)字，更快的放在了前面一些的位置
此時(shí)再執(zhí)行插入排序就會(huì)少了非常多移動(dòng)操作粪躬，因此排序的效率會(huì)得到提升
上述這個(gè)思想就是希爾排序担败，也稱之為縮小增量排序
我們來(lái)用代碼實(shí)現(xiàn)一下上述這個(gè)思路
大家可以結(jié)合注釋讀懂這段代碼
/**
* 自己根據(jù)希爾排序概念分析思路實(shí)現(xiàn)：
* 1.插入排序的問(wèn)題在于，如果很小的數(shù)字在很后邊镰官，那么它從最后邊移動(dòng)到前面來(lái)提前，需要非常多次的比較和移動(dòng)操作
* 2.如果遞減步長(zhǎng)的分組進(jìn)行插入排序可以有效減少比較和移動(dòng)的次數(shù)
* 3.具體方式為，分組數(shù)g = 數(shù)據(jù)量/2泳唠，分組方式為第i個(gè)和第i+g個(gè)狈网、...第i+(數(shù)據(jù)量/2)g個(gè)，一組笨腥，i <= g;
* 4.每一組進(jìn)行插入排序后拓哺，再次分組，這次的 分組數(shù)g = 上次分組數(shù)/2脖母，分組方式為第i個(gè)和第i+g士鸥、第i+2g...第i+(數(shù)據(jù)量/2)g為一組
* 5.直到進(jìn)行到g=1，相當(dāng)于最后是執(zhí)行一次完整的插入排序谆级，1/2=0不大于0烤礁，下一次就不會(huì)再進(jìn)入循環(huán)了，至此排序完成
*/
public static void shellSort(int[] arr){
//只要分組數(shù)大于1肥照，進(jìn)進(jìn)行分組插入排序
for (int groups = arr.length/2; groups > 0; groups/=2){
//外層循環(huán)分組
for (int i = 0; i < groups; i++) {
//內(nèi)層循環(huán)把每一組執(zhí)行插入排序(從第二個(gè)數(shù)開(kāi)始遍歷),出循環(huán)說(shuō)明第i組插入排序完成了
for (int x = i+groups; x < arr.length; x+=groups) {
//待插入的數(shù)存入臨時(shí)變量
int temp = arr[x];
//記錄待插入數(shù)應(yīng)該插入的位置的前一個(gè)（從當(dāng)前待插入數(shù)據(jù)的上一個(gè)開(kāi)始）
int index = x-groups;
//插入排序的內(nèi)層循環(huán)脚仔，將要插入的數(shù)據(jù)向前比較找到位置，出循環(huán)說(shuō)明位置找到了
while (index >= 0 && temp<arr[index]){
//遍歷到的數(shù)后移
arr[index+groups] = arr[index];
//將要遍歷的數(shù)移動(dòng)到再上一個(gè)位置舆绎，方便下一次遍歷
index-=groups;
}
//退出循環(huán)說(shuō)明上一次循環(huán)找到了位置鲤脏，應(yīng)該是index的下一個(gè)，也就是加上一個(gè)步長(zhǎng)groups
arr[index+groups] = temp;
}
}
}
}
代碼讀懂了嗎亿蒸？如果我告訴你這個(gè)不是最完美的希爾排序凑兰，你應(yīng)該不會(huì)想揍我吧??
這段代碼其實(shí)是筆者當(dāng)初自己學(xué)的時(shí)候掌桩，根據(jù)希爾排序的思路自行實(shí)現(xiàn)出來(lái)的，測(cè)試了排序結(jié)果是沒(méi)有問(wèn)題的姑食，8w數(shù)據(jù)排序也一下子提速到了10毫秒波岛，比起插入排序是一個(gè)質(zhì)的飛躍，我當(dāng)初非常驚喜音半。之后去看了網(wǎng)上的標(biāo)準(zhǔn)實(shí)現(xiàn)则拷，但我已經(jīng)鉆進(jìn)我自己的實(shí)現(xiàn)思路這個(gè)圓圈當(dāng)中出不來(lái)，甚至有點(diǎn)沒(méi)看懂標(biāo)準(zhǔn)實(shí)現(xiàn)代碼為什么可以完成排序
于是我先粘下來(lái)標(biāo)準(zhǔn)實(shí)現(xiàn)的代碼曹鸠，運(yùn)行測(cè)試了一下煌茬，毫無(wú)疑問(wèn)排序結(jié)果是沒(méi)有任何問(wèn)題的
然后我又試了一下標(biāo)準(zhǔn)代碼8w數(shù)據(jù)的效率，發(fā)現(xiàn)也是10ms左右彻桃，我又釋懷了坛善，覺(jué)得我這個(gè)也沒(méi)問(wèn)題，可能就是思路不太一樣
都是10ms有點(diǎn)看不出差距邻眷，我嘗試將數(shù)據(jù)量提升到了800w數(shù)字的排序
這時(shí)出現(xiàn)差距了眠屎，800w數(shù)據(jù)排序，我的野雞實(shí)現(xiàn)方式肆饶，平均下來(lái)比標(biāo)準(zhǔn)實(shí)現(xiàn)方式慢了近200ms
我必須弄清楚改衩，這個(gè)差距出在哪里
首先第一件事就是看懂標(biāo)準(zhǔn)的希爾排序是怎么完成排序的
我沒(méi)有加注釋，大家先自行隨便看一下代碼
public static void shellSort2(int[] arr) {
int temp, j;
for (int path = arr.length / 2; path > 0; path /= 2) {
for (int i = path; i < arr.length; i++) {
j = i;
temp = arr[j];
while (j - path >= 0 && temp < arr[j - path]) {
arr[j] = arr[j - path];
j -= path;
}
arr[j] = temp;
}
}
}
只看代碼驯镊，標(biāo)準(zhǔn)實(shí)現(xiàn)只用了三層循環(huán)葫督，而我的代碼出現(xiàn)了四層循環(huán)。
我發(fā)現(xiàn)最中間第二個(gè)for循環(huán)板惑，和我的代碼中第三層的for循環(huán)橄镜，都是在進(jìn)行插入排序
但我百思不得其解，為什么分組的插入排序洒放，他可以從i=groups開(kāi)始每次i++蛉鹿，遍歷到n去做
于是new了一個(gè)簡(jiǎn)單一些的數(shù)組，debug看了一下排序過(guò)程
終于被我看到問(wèn)題所在了
原來(lái)是我沒(méi)有抓住本質(zhì)
分組進(jìn)行插入排序往湿，我就將一組和一組隔離開(kāi)妖异，進(jìn)行排序，但其實(shí)不用這樣
本質(zhì)上無(wú)論你屬于哪一個(gè)分組领追，都是在做步長(zhǎng)為組數(shù)的插入排序
也就是說(shuō)他膳，按每一組插入排序，本質(zhì)上就是從第 組數(shù)+1 個(gè)元素開(kāi)始一直到最后一個(gè)數(shù)字绒窑，按 組數(shù) 為 步長(zhǎng) 進(jìn)行插入排序
還用上面那個(gè)數(shù)組舉例[5棕孙，8，12，4蟀俊，15钦铺，1，7肢预，6]
第一次將它分成四組
第一個(gè)和第五個(gè)執(zhí)行插入排序矛洞，本質(zhì)上是第五個(gè)元素執(zhí)行步長(zhǎng)為4的插入排序；
第二個(gè)和第六個(gè)執(zhí)行插入排序烫映，本質(zhì)上是第六個(gè)元素執(zhí)行步長(zhǎng)為4的插入排序
第三個(gè)和第七個(gè)執(zhí)行插入排序沼本，本質(zhì)上是第七個(gè)元素執(zhí)行步長(zhǎng)為4的插入排序
第四個(gè)和第八個(gè)執(zhí)行插入排序，本質(zhì)上是第八個(gè)元素執(zhí)行步長(zhǎng)為4的插入排序
完成后：[5锭沟，1抽兆，7，6族淮，15辫红，8，12祝辣，8]
第二次分為兩組
第一個(gè)第三個(gè)第五個(gè)第七個(gè)一組厉熟，依次對(duì)第三、五较幌、七個(gè)數(shù)做步長(zhǎng)為2的插入排序
第二個(gè)第四個(gè)第六個(gè)第八個(gè)一組，依次對(duì)第四白翻、六乍炉、八個(gè)數(shù)做步長(zhǎng)為2的插入排序
其實(shí)還是3、4滤馍、5岛琼、6、7巢株、8都做了步長(zhǎng)為2的插入排序
也就是從 組數(shù)+1 數(shù)字開(kāi)始到最后一個(gè)數(shù)組槐瑞，做 組數(shù) 為 步長(zhǎng) 的插入排序
完成后：[5，1阁苞，7困檩，4，12那槽，6悼沿，15，8]
這樣才算是真的弄明白了這個(gè)標(biāo)準(zhǔn)希爾排序骚灸，不得不說(shuō)想出算法和優(yōu)化代碼的人太厲害了
沒(méi)有抓住本質(zhì)的我糟趾，所以設(shè)計(jì)實(shí)現(xiàn)代碼時(shí)，多了一層按組隔離的循環(huán)，多執(zhí)行了一些循環(huán)體判斷和i++的操作义郑，導(dǎo)致了和標(biāo)準(zhǔn)實(shí)現(xiàn)方式出現(xiàn)的效率差距
再看一下給標(biāo)準(zhǔn)實(shí)現(xiàn)加上注釋的代碼吧
public static void shellSort3(int[] arr) {
//存放待插入數(shù)據(jù)的臨時(shí)變量
int temp;
//記錄待插入數(shù)據(jù)將要插入的位置
int index;
//外層控制蝶柿，分組方式的執(zhí)行次數(shù)，只要分組數(shù)大于1非驮，就進(jìn)行分組插入排序交汤，每排完一次，分組/=2
for (int groups = arr.length / 2; groups > 0; groups /= 2) {
//內(nèi)層進(jìn)行插入排序院尔，每一個(gè)分組分開(kāi)進(jìn)行插入排序蜻展，其本質(zhì)上，無(wú)論你是屬于第幾個(gè)分組的數(shù)字邀摆，從第組數(shù)個(gè)數(shù)字開(kāi)始纵顾，你都需要以組數(shù)為步長(zhǎng)進(jìn)行插入排序
for (int i = groups; i < arr.length; i++) {
index = i;
temp = arr[index];
//尋找要插入的位置，每次向前去遍歷隔一個(gè)組數(shù)的數(shù)字栋盹，尋找插入位置
while (index - groups >= 0 && temp < arr[index - groups]) {
arr[index] = arr[index - groups];
index -= groups;
}
//找到了位置就插入
arr[index] = temp;
}
}
}
比起上一章施逾，冒泡和選擇，插入和希爾難理解了一些例获，但按思路跟下來(lái)應(yīng)該還是可以理解到位的
下面說(shuō)一下測(cè)試結(jié)果：
我的電腦來(lái)測(cè)試汉额，希爾排序，8w數(shù)據(jù)只需要10毫秒左右榨汤，比起插入排序快了40多倍蠕搜，質(zhì)的飛躍
可見(jiàn)學(xué)好算法對(duì)程序性能提升可以有多恐怖
從這里開(kāi)始呢，我的機(jī)器性能可以采用800w數(shù)據(jù)排序來(lái)記錄執(zhí)行時(shí)間了
希爾排序（根據(jù)思路自己實(shí)現(xiàn)的）——1822收壕、1876妓灌、1850、1896蜜宪、1836
希爾排序（標(biāo)準(zhǔn)實(shí)現(xiàn)的）——1678虫埂、1614、1734圃验、1639掉伏、1666
下一篇我們將學(xué)習(xí)一種還要更快的排序，快速排序
