今天復(fù)習(xí)了五個(gè)排序硅则，分別是冒泡排序冒掌，選擇排序，插入排序蹲盘，哈希排序和快速排序股毫；
然后看了thinking in java的第一章和第二章；
下面就是今天學(xué)的所有知識(shí)
1.冒泡排序：冒泡排序主要是對(duì)鄰近的數(shù)據(jù)進(jìn)行比較召衔，根據(jù)結(jié)果判斷是否進(jìn)行交換铃诬，一輪一輪挑出其中比較大（小）的數(shù)據(jù)放到數(shù)組末尾薄嫡；在一輪一輪比較中氧急，需要比較的數(shù)據(jù)一次減少一個(gè)颗胡，直到最后下標(biāo)為0和1的進(jìn)行比較后毫深，則代表數(shù)組已經(jīng)有序了。
下面是實(shí)現(xiàn)代碼：
在這里面毒姨，upper用來(lái)決定每一輪進(jìn)行排序的數(shù)據(jù)個(gè)數(shù)哑蔫，由于下標(biāo)可以為0且內(nèi)部有sc[i+1]代碼的存在，所以里層for循環(huán)的取值為：0~sc.length-2;
2.選擇排序：這個(gè)選擇排序和冒泡排序進(jìn)行比較的次數(shù)相等弧呐，不過(guò)這里是一次性找出一輪數(shù)據(jù)中最大（姓⒚浴）的數(shù)據(jù)，放在數(shù)組末尾（開(kāi)頭）俘枫，然后下一輪取其他的數(shù)據(jù)再一次進(jìn)行選取最大（行裙痢）值；
下面是實(shí)現(xiàn)代碼：
這里實(shí)現(xiàn)的是一個(gè)從小到大的排序鸠蚪。首先upper和上面一樣取值：1~sc.length-1今阳，在表循環(huán)中，將sc[0]設(shè)置為最大值茅信，然后數(shù)據(jù)判斷從下標(biāo)1開(kāi)始盾舌，若有sc[n]<sc[0]則把最大值的下標(biāo)由0換成n，最后判斷一下最后的數(shù)據(jù)是否是下標(biāo)代表的最大值蘸鲸，不是則把下標(biāo)代表的最大值和最后面的值做一個(gè)交換妖谴，這樣就完成了一次排序；
這里的子循環(huán)中的i可以為1酌摇，這代表sc[0]和sc[1]進(jìn)行比較膝舅；
3.插入排序：插入排序是把一個(gè)數(shù)組分成了三個(gè)部分：有序部分，待插入值窑多，無(wú)序部分铸史；有序部分的個(gè)數(shù)由1~sc.length-1；當(dāng)最后一個(gè)數(shù)據(jù)也進(jìn)入了有序隊(duì)列怯伊，則排序完成琳轿；插入排比價(jià)序主要是將待插入值放入有序隊(duì)列中去判沟，通過(guò)比較，將它插入到隊(duì)列中形成一個(gè)有序的新隊(duì)列崭篡；
下面是插入排序的代碼：
其中count代表待插入值的下標(biāo)挪哄，1~sc.length-1；然后子循環(huán)中用num來(lái)存儲(chǔ)待插入值琉闪，讓每一個(gè)值和他比較迹炼，若待插入值小于比較的值，則把比較的值直接后移一位颠毙；i=1時(shí)代表前面所有數(shù)據(jù)都大于待插入值斯入，所以就把該值放在0下標(biāo)處；
4.哈希排序：哈希排序是一個(gè)改良版的插入排序蛀蜜，它主要是通過(guò)選取一定的間隔刻两，在早期就把離正確位置很遠(yuǎn)的數(shù)據(jù)直接一次性轉(zhuǎn)移過(guò)去，而不需要插入排序一樣一次一次比較復(fù)制慢慢地轉(zhuǎn)移過(guò)去滴某。在大量數(shù)據(jù)中磅摹，他的速度要比插入排序好很多，而且它在數(shù)據(jù)逆行的情況下霎奢，速度比插入排序快了很多户誓；下面是哈希排序的代碼，這個(gè)我自己也不是很明白幕侠；
這里的num就是選取的固定間隔帝美，num遵循一種算式，讓每一個(gè)num互成質(zhì)數(shù)晤硕，這樣的效率是最高的悼潭；第一次排序，對(duì)下標(biāo)為：num~sc.length-1的數(shù)據(jù)進(jìn)行了間隔為num的數(shù)組的排序窗骑，注意這里子循環(huán)判斷條件已經(jīng)發(fā)生改變了女责；然后按公式慢慢減小num,最后直到為1時(shí)，代表數(shù)據(jù)已經(jīng)排序完成创译；
哈希排序和插入排序最大的不同之處在于 ?sc[i] = sc[i-1] ?和 ?sc[i] = sc[i-num]抵知；
5.快速排序：快速排序主要是應(yīng)用了一個(gè)遞歸和劃分的概念。劃分指的是取一個(gè)值软族，將數(shù)組中的數(shù)據(jù)分成兩部分刷喜，左邊的全部小于該數(shù)據(jù)，右邊的全部大于等于該數(shù)據(jù)立砸；然后又把左邊和右邊兩個(gè)數(shù)組用這個(gè)方法掖疮，分到最后，所有數(shù)據(jù)已經(jīng)做到了有序狀態(tài)了颗祝；這個(gè)排序要分成兩個(gè)部分浊闪，一個(gè)是遞歸的部分恼布，另一個(gè)是劃分的部分；
這個(gè)函數(shù)采用的是直接把數(shù)組最右邊的數(shù)據(jù)作為他的中間值（樞紐）搁宾，然后在劃分后折汞，把樞紐放在兩個(gè)部分中間，此時(shí)該數(shù)據(jù)已經(jīng)存在了正確排序的位置了盖腿，然后對(duì)兩邊兩組新數(shù)組進(jìn)行排序……
在劃分階段爽待，我們?cè)O(shè)置了一個(gè)左指針和右指針，分別判斷兩頭的數(shù)據(jù)和樞紐的關(guān)系翩腐，若左側(cè)存在大于樞紐的值并且右側(cè)存在小于樞紐的值鸟款，則將兩個(gè)值進(jìn)行交換，然后繼續(xù)判斷茂卦，直到兩個(gè)指針相等或擦肩而過(guò)何什，則代表該已經(jīng)劃分成功，這時(shí)候把最右端數(shù)據(jù)和右數(shù)組的第一個(gè)數(shù)據(jù)進(jìn)行交換疙筹，則完成了劃分的功能了富俄。返回的是中間樞紐的下標(biāo)值禁炒；
