排序算法中碰纬，經(jīng)常見到的有八種排序算法萍聊，這里我們不包括在內(nèi)存的外部進(jìn)行排序。
這八種排序算法分別是：
冒泡排序悦析、選擇排序寿桨、插入排序、歸并排序强戴、快速排序亭螟、堆排序、希爾排序骑歹、基數(shù)排序预烙。
在講具體的排序算法之前，我先給大家推薦一個對學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)非常有幫助的網(wǎng)站：armStrong數(shù)據(jù)結(jié)構(gòu)與算法小動畫道媚，這個網(wǎng)站把各種數(shù)據(jù)結(jié)構(gòu)與算法的原理做成了一個個小動畫扁掸，非常直觀的幫助我們理解和學(xué)習(xí)欢嘿。如果打不開這個網(wǎng)站的話，請切換瀏覽器也糊。
好了，接下來是具體的算法講解部分羡宙。
1. 冒泡排序O(n^2)
先來看原理部分,冒泡排序就是將每個數(shù)與它后面的數(shù)進(jìn)行比較狸剃，如果大于之后的數(shù)，就兩者交換狗热，一直循環(huán)前面的操作钞馁，直到該數(shù)小于后面的數(shù)為止∧涔危口說無憑僧凰，直接看動畫吧，這就用到了我上面推薦的網(wǎng)站了熟丸，直接把冒泡排序的網(wǎng)址貼在這里吧训措！冒泡排序原理動畫 相信現(xiàn)在你已經(jīng)看完了冒泡排序的原理動畫，現(xiàn)在我需要你腦海里回想著剛剛看到的動畫光羞，同時來思考我們下面的代碼
public int[] bubbleSort(int[] A) {
for (int i = 0; i < A.length - 1; i++) {
for (int j = 0; j < A.length - 1 - i; j++) {
if (A[j] > A[j + 1]) {
int temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
}
}
}
return A;
}
這是一段冒泡排序的代碼绩鸣，在第一層循環(huán)里面，因為數(shù)組有A.length個元素纱兑，需要比較 A.length - 1次呀闻，所以我們循環(huán)的次數(shù)是 A.length-1。
在第二層循環(huán)里面潜慎，想象一下你剛才看到的動畫捡多，當(dāng)一個數(shù)往后交換一直到交換不動的時候，是因為它后面的數(shù)都已經(jīng)比它大了铐炫，此時這個數(shù)連同它后面的數(shù)都是有序的垒手，所以我們下一次循環(huán)時就不需要再對這些數(shù)進(jìn)行比較了。所以我們比較的范圍要逐漸減小驳遵，只需要比較 0~A.length-1-i 之間的數(shù)就可以了淫奔。
2. 選擇排序O(n^2)
選擇排序的原理就是，每次從無序的序列中循環(huán)選出最小的數(shù)堤结，將它交換到無序序列的最前面唆迁，最終在數(shù)組中形成一個從前往后排列的有序序列。看動畫選擇排序原理動畫竞穷，同樣的唐责，腦海里帶著剛才看到的畫面，來思考我們下面的代碼
public int[] selectionSort(int[] A) {
for (int i = 0; i < A.length - 1; i++) {
int min = A[i];
int minIndex = i;
for (int j = i + 1; j < A.length; j++) {
if (A[j] < min) {
min = A[j];
minIndex = j;
}
}
A[minIndex] = A[i];
A[i] = min;
}
return A;
}
最外層的循環(huán)中瘾带，i 代表著我們無序序列的第一個元素位置鼠哥，我們先假使它是無需序列中最小的元素，每次循環(huán)，從該位置之后的元素中朴恳，選出最小的元素抄罕，如果這個最小的元素比 i 位置上的元素還小，就將它們兩個交換于颖。而隨著 i 的增加呆贿，我們的無需序列也在不斷減小，最后就形成了一個從小到大排列的有序序列森渐。
3. 插入排序O(n^2)
插入排序和選擇排序有點類似做入，都是把序列前面的部分看成有序的序列，后面部分看成無序的序列同衣。每次會選定無序序列中第一個元素竟块，插入到有序序列中的合適位置，隨著有序序列的長度不斷增加耐齐，最終形成一個完全的有序序列浪秘。
看動畫插入排序原理動畫
接下來放上我們的插入排序代碼
public int[] insertionSort(int[] A) {
// write code here
for (int i = 1; i < A.length; i++) {
int point = i;
for (int j = i - 1; j >= 0; j--) {
if (A[point] < A[j]) {
int temp = A[point];
A[point] = A[j];
A[j] = temp;
point = j;
}
}
}
return A;
}
這段代碼很好理解，首先將將序列的第 0 個元素看作有序的蚪缀，所以 i 的初始值為 1秫逝，A[i] 就是無序序列的第一個元素，然后將 A[i] 和它前面的有序序列中的元素作比較询枚，并且插到合適的位置违帆。這里注意一點，我們的比較是從后往前的金蜀，即 A[i] 首先和它前面的做比較刷后，如果小于它前面的元素就交換位置，然后再和它現(xiàn)在的前面的元素作比較渊抄，直到找到一個小于 A[i] 的元素尝胆，比較結(jié)束。但 i 是一直在改變的啊护桦，那我們怎么才能確保每次都是移動的同一個元素呢含衔？ 加個point指針就好了嘛。
4. 歸并排序O(n * logn)
前面三個都是時間復(fù)雜度為 n 的平方的排序算法二庵，下面來講時間復(fù)雜度為
n * logn的排序算法贪染，首先從歸并排序講起。
看原理圖（剛剛畫的催享，之前沒怎么畫過杭隙，才開始寫博客，都是借別人的圖因妙，但是這個歸并排序人家動畫里沒有痰憎，只能自己動手了）
歸并排序首先將序列看成一個個長度為 1 的有序序列票髓，然后將相鄰的兩個序列歸并，形成一個按照大小排好序的長度為 2 的有序序列铣耘。以此類推洽沟，最后形成完全有序的一個序列。
歸并的過程也就是這個排序算法的關(guān)鍵步驟蜗细，這個人家的動畫里有玲躯，我直接搬過來了歸并相鄰序列的動畫
好了，該放代碼了
public static void mergeSort(int[] list) {
if (list.length > 1) {
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
int[] temp = merge(firstHalf, secondHalf);
System.arraycopy(temp, 0, list, 0, temp.length);
}
}
public static int[] merge(int[] firstHalf, int[] secondHalf) {
int[] temp = new int[firstHalf.length + secondHalf.length];
int firstIndex = 0;
int secondIndex = 0;
int tempIndex = 0;
while (firstIndex < firstHalf.length && secondIndex < secondHalf.length) {
if (firstHalf[firstIndex] < secondHalf[secondIndex]) {
temp[tempIndex++] = firstHalf[firstIndex++];
} else {
temp[tempIndex++] = secondHalf[secondIndex++];
}
}
while (firstIndex < firstHalf.length) {
temp[tempIndex++] = firstHalf[firstIndex++];
}
while (secondIndex < secondHalf.length) {
temp[tempIndex++] = secondHalf[secondIndex++];
}
return temp;
}
代碼開始變得越來越復(fù)雜了鳄乏，不過不用怕，我會一點一點的講明白棘利。
首先這里我們定義了兩個方法橱野，mergeSort() 就是一個遞歸調(diào)用，每次將序列分成兩半善玫，然后再通過merge() 方法對兩個序列進(jìn)行歸并水援。所以merge() 方法就是我們歸并排序的關(guān)鍵。
先來講將序列分成兩半的代碼部分茅郎，也就是mergeSort() 方法部分蜗元。在這個方法里，我們以 list.length > 1 為遞歸的邊界條件（遞歸必須有邊界條件系冗，否則就會報出StackOverflowException）奕扣，代碼很明了，將傳入的 list[] 分成兩部分 firstHalf[] 和 secondHalf[] 兩部分掌敬，然后將這兩個數(shù)組傳入 merge 方法進(jìn)行歸并惯豆。
這里有一個坑，有同學(xué)可能直接會把 merge() 方法的返回值賦給 list奔害。這樣的做法是錯誤的楷兽，先貼一下主方法的代碼：
public static void main(String[] args) { int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12}; mergeSort(list); System.out.println(Arrays.toString(list)); }因為這樣的結(jié)果只是改變了 mergeSort() 方法中 list 的指針，但是我們主方法中的 list[] 并沒有改變华临，還是之前的結(jié)果芯杀。所以我們用到了
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
這個API來對數(shù)組進(jìn)行復(fù)制。
接下來是最關(guān)鍵的 merge() 方法雅潭，剛剛的動畫沒忘吧揭厚，首先建立一個 temp[] 數(shù)組用來存放歸并之后的元素，然后定義三個指針寻馏，在第一個while循環(huán)比較兩個數(shù)組中的第一個元素棋弥，將較小者賦給 temp[] ，然后改變指針诚欠，直到兩個數(shù)組中的某一個遍歷到了末尾顽染。
剩下的兩個 while 循環(huán)就是判斷了一下：上面的兩個數(shù)組中哪一個還沒有遍歷完漾岳，因為兩個數(shù)組可能不是一樣的長度，所以長的那個要把剩下的元素全都拷貝到 temp[] 中粉寞。
5. 快速排序O(n * logn)
現(xiàn)在來講快排尼荆，正如時間復(fù)雜度變得越來越小，換來的卻是算法的復(fù)雜度越來越高唧垦，現(xiàn)在我開始有點力不從心了捅儒。
快排的原理：
在數(shù)組中選取一個稱為主元的（pivot）元素，然后根據(jù)主元對數(shù)組進(jìn)行劃分（partition）振亮，劃分之后的數(shù)組變成兩部分巧还，第一部分中的元素全都小于主元，第二部分中的元素全都大于主元坊秸，然后再分別對第一部分和第二部分遞歸調(diào)用快排算法麸祷。
所以快速排序算法的關(guān)鍵就在于如何劃分。請看動畫
快排劃分過程動畫
清楚了如何劃分褒搔，剩下的就是遞歸調(diào)用了阶牍，我畫了一張原理圖，
正如上面講的星瘾，經(jīng)過一次劃分后走孽， 5 的左邊都是小于它的元素，右邊都是大于它的元素琳状，然后分別對兩邊的數(shù)組遞歸調(diào)用快排算法磕瓷。
萬事俱備，該放代碼了
public static void quickSort(int[] list) {
quickSort(list, 0, list.length - 1);
}
private static void quickSort(int[] list, int first, int last) {
if (first < last) {
int midIndex = partition(list, first, last);
quickSort(list, 0, midIndex - 1);
quickSort(list, midIndex + 1, last);
}
}
private static int partition(int[] list, int first, int last) {
int pivot = list[first];
int low = first + 1;
int high = last;
while (low < high) {
while (low < high && list[low] <= pivot) {
low++;
}
while (low < high && list[high] >= pivot) {
high--;
}
if (low < high) {
int temp = list[low];
list[low] = list[high];
list[high] = temp;
}
}
if (pivot < list[high]) {
high--;
}
list[first] = list[high];
list[high] = pivot;
return high;
}
最上面的 quickSort(int[] list) 就是用于外部調(diào)用的快速排序方法念逞，可以看到里面只有一行代碼生宛，它調(diào)用了我們下面封裝的一個私有的 quickSort(int[] list, int first, int last) 重載方法。
在第二個 quickSort(int[] list, int first, int last) 方法中肮柜，執(zhí)行的就是我們的遞歸過程陷舅。first 代表著 list 的首位置， last 代表著 list 中最后一個元素位置审洞。遞歸以 (first < last) 為邊界莱睁。首先對 list 執(zhí)行一次劃分，然后根據(jù)返回的主元的位置芒澜，再對剩下的兩部分進(jìn)行遞歸仰剿。
最后也是最關(guān)鍵的部分，劃分的代碼痴晦，來看 partition 里面的邏輯南吮。
在這個方法里，我們先假定數(shù)組中的第一個元素為主元誊酌，就如同我畫的圖中的第一行部凑。然后定義兩個指針 low 和 high 露乏，忘了劃分步驟的，趕快回去看動畫涂邀，接下來要飆車了瘟仿。
在動畫里我們看到， low 和 high 不斷往中間移比勉，而 list[low] 代表著小于主元的元素劳较， list[high] 代表著大于主元的元素.
所以當(dāng) list[low] =< pivot <= list[high] 的時候，我們就不斷執(zhí)行 low++ 和 high-- 浩聋，一直遇到 list[low] > pivot 和 list[high] < pivot 的情況,這時候我們就要對 list[low] 和 list[high] 執(zhí)行交換观蜗，使其一直保持 list[low]=< pivot <= list[high] 這樣的姿勢。
注意一點衣洁，在 low++ 和 high-- 這兩個 while 循環(huán)中嫂便，我們附加了一個額外條件 low < high ，這并不多余Ｕ⒂搿！因為主元的右邊可能是全部小于它的數(shù)或者全部大于它的數(shù)岸售，這樣的情況下 low 和 high 繼續(xù)改變下去就會報出數(shù)組越界異常践樱。
當(dāng) low 和 high 相遇后，最外層的 while 循環(huán)結(jié)束凸丸，此時 low = high拷邢， 即 list[low] = list[high]，這時候該做的是把主元移動到它該去的位置屎慢，而不是還呆在數(shù)組的開頭瞭稼。那我們該把它調(diào)到哪里呢？直接和 list[high] （或 list[low]腻惠，它們此時是相等的） 交換嗎环肘？
不行，因為此時 list[low] = list[high] 可能大于 pivot集灌，直接換到數(shù)組的開頭后悔雹，就會出現(xiàn)主元的左邊有大于它的元素的情況，這和我們劃分的思想不符欣喧，那怎么辦呢腌零？
list[low] 雖然大于主元，但是它前邊的 list[low--] 肯定小于主元八舭ⅰ益涧！那我們加個判斷，判斷一下 list[low] （或 list[high]）是不是真的大于主元驯鳖，如果真的大于的話闲询，就讓 low-- （或 high--）久免，最后再執(zhí)行交換。
這樣主元就回到了正確的位置嘹裂，然后我們返回它的位置妄壶，為下一次劃分做準(zhǔn)備。
這就是快速排序寄狼，是不是很啰嗦丁寄？沒關(guān)系，一遍看不太懂的話泊愧，就多看幾遍伊磺，因為后面還有更難的 -_-||
6. 堆排序O(n * logn)
學(xué)過數(shù)據(jù)結(jié)構(gòu)的同學(xué)應(yīng)該對堆不陌生，它就是一個二叉樹删咱，我們這次的堆排序用到的堆比較特殊屑埋，它是一個大根堆，所謂的大根堆就是指父節(jié)點的值永遠(yuǎn)比子節(jié)點的大痰滋。堆頂是堆中所有元素最大的摘能。
所以堆排序的原理就是首先建立一個大根堆，然后每次移除堆頂元素敲街，再把剩下的元素重新調(diào)整成大根堆的過程团搞。因為堆頂是最大的元素，所以每次移除出來的一個個堆頂就構(gòu)成了一個從大到小排好序的序列多艇。
可以看到逻恐，堆排序的關(guān)鍵就在于構(gòu)建堆與移除堆頂后的調(diào)整堆。
先看構(gòu)建堆的動畫構(gòu)建堆的動畫
動畫省略了一些步驟峻黍，它只輸出了結(jié)果复隆，而構(gòu)建是有一個過程的。首先會把新元素追加到堆尾姆涩，然后讓它跟它的父節(jié)點比較挽拂，如果大于父節(jié)點，就和父節(jié)點交換骨饿，然后繼續(xù)和新的父節(jié)點比較轻局。。样刷。一直循環(huán)仑扑，最后重新建成一個大根堆。
然后是移除堆頂后的堆調(diào)整過程置鼻，我畫了一張圖镇饮。
堆調(diào)整的過程分三步，就是我們紅線標(biāo)注的部分箕母。
第一步储藐，移除堆頂俱济，放在一邊，你可以放在一個數(shù)組里邊钙勃，因為每次移除的堆頂都是堆中的最大元素蛛碌，所以數(shù)組最終變成一個從大到小排好序的序列。
第二步辖源，把堆尾元素放到堆頂蔚携。
第三步，從新的堆頂開始往下遍歷克饶，如果小于左右孩子中的最大節(jié)點酝蜒，則進(jìn)行交換，大于的話則不用交換矾湃。如 ② 中 8 大于 3 （3 是 8 的左右孩子中最大的節(jié)點）亡脑，則 8 和 3不用交換，而 3 小于 6邀跃，所以 3 和 6 交換霉咨。
接下來看代碼，這次我換了一個方式拍屑，把代碼的講解放到了代碼注釋里途戒，這對代碼量大的場合很方便。
//建立一個內(nèi)部類Heap
private class Heap{
//用一個List來存放堆中的元素
List<Integer> list = new ArrayList();
//構(gòu)造函數(shù)丽涩，將傳入的數(shù)組最終構(gòu)建成大根堆
private Heap(int[] array) {
for (int i = 0; i < array.length; i++) {
add(array[i]);
}
}
/**
* 功能：每次先把傳入的元素放在堆尾，然后調(diào)整裁蚁，變成一個元素個數(shù)多一的大根堆
* @param num 傳入的元素
*/
private void add(int num) {
list.add(num); //先將傳入的元素追加在堆尾
int currentIndex = list.size() - 1; //從堆尾開始遍歷
while (currentIndex > 0) {
int parentIndex = (currentIndex - 1) / 2; //先找到堆尾元素的父節(jié)點
//因為我們要構(gòu)建的是大根堆矢渊，所以當(dāng)父節(jié)點小于當(dāng)前節(jié)點時，兩者交換枉证。
// 否則說明剛剛追加的元素合適矮男，直接退出循環(huán)
if ((list.get(currentIndex).compareTo(list.get(parentIndex))) > 0) {
int temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
//兩者交換后，我們要繼續(xù)判斷新追加的節(jié)點是不是比剛才的父節(jié)點的父節(jié)點還要大室谚，
// 所以將剛才父節(jié)點的索引賦值給它毡鉴，繼續(xù)剛才的循環(huán)
currentIndex = parentIndex;
} else {
break;
}
}
}
/**
* 每次移除大根堆的堆頂元素，然后調(diào)整秒赤，變成一個元素個數(shù)減一的大根堆
* @return 返回的大根堆堆頂元素
*/
private int remove() {
int removedNum = list.get(0); //先保存堆頂元素
//將堆尾元素賦值給堆頂猪瞬，同時刪除堆尾
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
//要開始調(diào)整堆了，首先從新堆頂開始遍歷
int currentIndex = 0;
while (currentIndex < list.size() - 1) {
int leftIndex = currentIndex * 2 + 1;
int rightIndex = currentIndex * 2 + 2; //先找到當(dāng)前節(jié)點的左右孩子
if (!(leftIndex < list.size())) { //如果不存在左孩子入篮，說明當(dāng)前節(jié)點已經(jīng)最大陈瘦，不需要調(diào)整大根堆，直接退出循環(huán)
break;
}
int maxIndex = leftIndex; //如果存在左孩子潮售，先假設(shè)它是最大的節(jié)點
//如果右孩子也存在的話痊项，那么就要讓它跟左孩子比較一下誰最大了
if (rightIndex < list.size()) {
if ((list.get(maxIndex).compareTo(list.get(rightIndex))) < 0) {
maxIndex = rightIndex;
}
}
//用剛才得到的锅风，左右孩子中的最大節(jié)點，與當(dāng)前節(jié)點進(jìn)行比較
//如果當(dāng)前節(jié)點比最大節(jié)點還要大的話鞍泉，說明當(dāng)前節(jié)點已經(jīng)最大皱埠，不需要調(diào)整大根堆，直接退出循環(huán)
//否則咖驮，交換
if ((list.get(currentIndex).compareTo(list.get(maxIndex))) > 0) {
break;
} else {
int temp = list.get(currentIndex);
list.set(currentIndex, list.get(maxIndex));
list.set(maxIndex, temp);
currentIndex = maxIndex;
}
}
return removedNum; //返回之前保存的堆頂元素
}
}
因為我們的算法是堆排序边器，所以上面的代碼是一個實現(xiàn)堆（Heap）的內(nèi)部類，其中 add 方法用來建堆游沿，就如同動畫里面演示的饰抒。delete 方法用于刪除堆頂和調(diào)整堆。
下面是堆排序的調(diào)用方法
public void heapSort(int[] list) {
//根據(jù)數(shù)組構(gòu)建一個大根堆
Heap heap = new Heap(list);
//每次移除堆頂?shù)淖畲笤鼐魇颍x給數(shù)組（因為我們最后要的數(shù)組是從小到大排列的袋坑，所以從后遍歷）。
for (int i = list.length - 1; i >= 0; i--) {
list[i] = heap.remove();
}
}
堆排序到此結(jié)束眯勾。
7. 希爾排序O(n * logn)
希爾排序是一種特殊的插入排序枣宫，想象一下之前的插入排序：將每個元素前面的序列都看成有序序列，然后對該有序序列從后往前遍歷吃环，如果相鄰元素大于當(dāng)前元素也颤，就與當(dāng)前元素交換。
在遍歷的時候我們每次都是與當(dāng)前元素相鄰的元素做比較郁轻，即步長為 1 翅娶。
所以，如果序列中最小的元素恰巧放在序列末尾的時候好唯，光移動這一個元素就要比較 n - 1 次竭沫，這對于大型的序列來說是非常耗時的！
希爾排序是怎么做的呢骑篙？
它與插入排序的區(qū)別就是希爾排序的步長（step）是改變的蜕提，首先選取為 數(shù)組長度的 1/2 ，之后每次減小一半靶端，當(dāng)最后步長（step）變成 1 的時候谎势，就變成了我們經(jīng)典的插入排序。
別看這么一小點改變杨名，就靠這一點，希爾排序就突破了平方級別的運行時間台谍。它的代碼量小姐霍，而且不占用額外的空間，所以在中等級別的數(shù)組排序中非常推薦用希爾排序！你可能想還會有更高效的排序算法镊折，沒錯胯府，但是它們也只會比希爾排序快兩倍（可能還達(dá)不到），而且更復(fù)雜恨胚。所以骂因，學(xué)好希爾排序吧！
來看一張原理圖
把排序過程在腦海里走一遍赃泡，然后看代碼
public int[] shellSort(int[] A) {
int step = A.length / 2;
while (step > 0) {
for (int i = step; i < A.length; i++) {
for (int j = i; j >= step && (A[j] < A[j - step]); j -= step) {
int temp = A[j];
A[j] = A[j - step];
A[j - step] = temp;
}
}
step /= 2;
}
return A;
}
比快排和堆排序簡單多了吧寒波！首先定義步長為 數(shù)組長度的一半，其實就是在插入排序的兩層 for 循環(huán)外面加一層判斷步長（step）的 while 循環(huán)升熊。
首先進(jìn)行 step = A.length / 2 的插入排序俄烁。i 代表著我們要比較的元素，因為是間隔 step 的插入排序级野，所以 i 從 step 開始页屠，然后每次都和它前面相隔 step 的元素進(jìn)行比較，如果小于前面相隔 step 的元素蓖柔，就交換辰企，然后繼續(xù)和新的與它相隔 step 的元素進(jìn)行比較，直到小于或者前面沒有與它相隔 step 的元素况鸣，結(jié)束循環(huán)牢贸。然后步長縮小一半，循環(huán)上述過程镐捧。
其實希爾排序的關(guān)鍵就是步長的選擇潜索，我們選的步長初始值是數(shù)組長度的一半，然后每次縮小二分之一懂酱。那么最優(yōu)的步長初始值與遞減規(guī)律該怎么選擇呢竹习？？玩焰？由驹？
我也不知道芍锚。
8. 基數(shù)排序
有點累了昔园，不想寫了，我找了一篇別人寫的很不錯的基數(shù)排序博客并炮，貼給大家
