概述：
本文給出常見的幾種排序算法的原理以及java實現，包括常見的簡單排序和高級排序算法，以及其他常用的算法知識。
- 簡單排序：冒泡排序、選擇排序、插入排序
- 高級排序：快速排序、歸并排序、希爾排序
冒泡排序（Bubble Sort）
冒泡排序須知：
作為最簡單的排序算法之一，冒泡排序給我的感覺就像Abandon在單詞書里出現的感覺一樣，每次都在第一頁第一位，所以最熟悉。。。冒泡排序還有一種優(yōu)化算法，就是立一個flag，當在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經有序。但這種改進對于提升性能來說并沒有什么太大作用。。。
原理:
- 從第一個數據開始，與第二個數據相比較，如果第二個數據小于第一個數據，則交換兩個數據的位置。
- 指針由第一個數據移向第二個數據，第二個數據與第三個數據相比較，如果第三個數據小于第二個數據，則交換兩個數據的位置。
- 依此類推，完成第一輪排序。第一輪排序結束后，最大的元素被移到了最右面。
- 依照上面的過程進行第二輪排序，將第二大的排在倒數第二的位置。
- 重復上述過程，沒排完一輪，比較次數就減少一次。
例子:
待排序數據：7, 6, 9, 8, 5,1
第一輪排序過程：
指針先指向7，7和6比較，6<7，交換6和7的位置，結果為：6,7,9,8,5,1
指針指向第二個元素7，7和9比較，9>7，不用交換位置，結果仍為：6,7,9,8,5,1
指針指向第三個元素9，比較9和8，8<9，交換8和9的位置，結果為：6,7,8,9,5,1
指針指向第四個元素9，比較9和5，5<9，交換5和9，結果為：6,7,8,5,9,1
指針指向第五個元素9，比較9和1，1<9，交換1和9的位置，結果為6,7,8,5,1,9
第一輪排序結束后，最大的數字9被移到了最右邊。
進行第二輪排序，過程同上，只是由于最大的9已經放在最右邊了，因此不用在比較9了，少了一次比較，第二輪結束的結果為：6,7,5,1,8,9
第三輪結果：6,5,1,7,8,9
第四輪比較結果：5,1,6,7,8,9
第五輪比較結果：1,5,6,7,8,9
最終排序結果為：1,5,6,7,8,9，由上可知N個數據排序，需要進行N-1輪排序；第i輪排序需要的比較次數為N-i次。
冒泡排序動圖演示：
編碼思路：
需要兩層循環(huán)，第一層循環(huán)end表示排序的輪數（沒循環(huán)一次總次數就會減一，最后一個數不用參與循環(huán)），第二層循環(huán)i表示需要比較的數據個數（上面剩余的有效數據個數）
代碼實現：
public class BubbleSortDemo {
public static void main(String[] args) {
int[] arr = {7, 6, 9, 8, 5,1};
bubbleSort(arr);
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + ",");
}
}
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
// 每輪循環(huán)總次數減一
for(int end = arr.length - 1; end > 0; end--) {
// 循環(huán)和剩余的有效數據比較
for(int i = 0; i < end; i++) {
if(arr[i] > arr[i+1]) {
swap(arr, i, i+1);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
什么時候最快（Best Cases）：O(n2)
當輸入的數據已經是正序時（都已經是正序了，我還要你冒泡排序有何用啊。。。。）
什么時候最慢（Worst Cases）：
當輸入的數據是反序時（寫一個for循環(huán)反序輸出數據不就行了，干嘛要用你冒泡排序呢，我是閑的嗎。。。）
冒泡排序算法總結：
- N個元素需要排序N-1輪；
- 第i輪需要比較N-i次；
- N個元素排序，需要比較n（n-1）/2次；
- 冒泡排序的算法復雜度較高，為O（n2）
選擇排序（Selection Sort）
選擇排序是對冒泡排序的改進，它的比較次數與冒泡排序相同，但交換次數要小于冒泡排序。當數據量較大時，效率會有很大的提升，但時間復雜度仍為O(n*n)
選擇排序須知：
在時間復雜度上表現最穩(wěn)定的排序算法之一，因為無論什么數據進去都是O(n2)的時間復雜度。。。所以用到它的時候，數據規(guī)模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。
原理：
- 從第一個元素開始，分別與后面的元素向比較，找到最小的元素與第一個元素交換位置；
- 從第二個元素開始，分別與后面的元素相比較，找到剩余元素中最小的元素，與第二個元素交換；
- 重復上述步驟，直到所有的元素都排成由小到大為止。
例子：
待比較數據：7, 6, 9, 8, 5,1
第一輪：此時指針指向第一個元素7，找出所有數據中最小的元素，即1，交換7和1的位置，排序后的數據為：1,6,9,8,5,7
第二輪：第一個元素已經為最小的元素，此時指針指向第二個元素6，找到6,9,8,5,7中最小的元素，即5，交換5和6的位置，排序后的結果為：1,5,9,8,6,7
第三輪：前兩個元素為排好序的元素，此時指針指向第三個元素9，找到9,8,6,7中最小的元素，即6，交換6和9的位置，排序后的結果為：1,5,6,8,9,7
第四輪：前三個元素為排好序的元素，此時指針指向第四個元素8，找到8,9,7中最小的元素，即7，交換8和7的位置，排序后的結果為：1,5,6,7,9,8
第五輪：前四個元素為排好序的元素，此時指針指向第五個元素9，找到9,8中最小的元素，即8，交換9和8的位置，排序后的結果為：1,5,6,7,8,9
到此，全部排序完成。
分析：從上面的原理可以看出，與冒泡排序不同，選擇排序每排完一輪都把最小的元素移到了最左面，然后下一輪排序的比較次數比上一輪減少一次，即第i輪排序需要比較N-i次。因此，和冒泡排序一樣，N個數據比較大小，需要排序N-1輪，第i輪排序需要比較N-i次。
選擇排序動圖演示：
編碼思路：
需要兩次循環(huán)，第一層循環(huán)i表示每輪指針指向的位置，將最小值min初始化為第i個元素，第二層循環(huán)從j=i+1開始，分別與min比較，如果小于min，則更新min的值，內層循環(huán)結束后；交換min元素和第i個元素的位置。以此類推進行下一輪循環(huán)，直到i=length時停止循環(huán)。當i=length時，說明小的元素已經全部移到了左面，因此無需進行內層循環(huán)了。
代碼實現：
public class SelectionSortDemo {
public static void main(String[] args) {
int[] arr = {7, 6, 9, 8, 5,1};
selectionSort(arr);
for(int i = 0; i<arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
public static void selectionSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
for(int i = 0; i < arr.length -1; i++) {
int minIndex = i;
for(int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
選擇排序算法總結：
- N個元素需要排序N-1輪；
- 第i輪需要比較N-i次；
- N個元素排序，需要比較n（n-1）/2次；
- 選擇排序的算法復雜度仍為O（n*n）；
- 相比于冒泡排序，選擇排序的交換次數大大減少，因此
速度要快于冒泡`排序
插入排序
插入排序是簡單排序中最快的排序算法，雖然時間復雜度仍然為O(n*n)，但是卻比冒泡排序和選擇排序快很多。
插入排序須知：
插入排序的代碼實現雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。當然，如果你說你打撲克牌摸牌的時候從來不按牌的大小整理牌，那估計這輩子你對插入排序的算法都不會產生任何興趣了。。。
插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。對于這種算法，得了懶癌的我就套用教科書上的一句經典的話吧：感興趣的同學可以在課后自行研究。。。
原理：
- 將指針指向某個元素，假設該元素左側的元素全部有序，將該元素抽取出來，然后按照從右往左的順序分別與其左邊的元素比較，遇到比其大的元素便將元素右移，直到找到比該元素小的元素或者找到最左面發(fā)現其左側的元素都比它大，停止；
- 此時會出現一個空位，將該元素放入到空位中，此時該元素左側的元素都比它小，右側的元素都比它大；
- 指針向后移動一位，重復上述過程。每操作一輪，左側有序元素都增加一個，右側無序元素都減少一個。
例子：
待比較數據：7, 6, 9, 8, 5,1
第一輪：指針指向第二個元素6，假設6左面的元素為有序的，將6抽離出來，形成7,,9,8,5,1，從7開始，6和7比較，發(fā)現7>6。將7右移，形成,7,9,8,5,1，6插入到7前面的空位，結果：6,7,9,8,5,1
第二輪：指針指向第三個元素9，此時其左面的元素6,7為有序的，將9抽離出來，形成6,7,_,8,5,1，從7開始，依次與9比較，發(fā)現9左側的元素都比9小，于是無需移動，把9放到空位中，結果仍為：6,7,9,8,5,1
第三輪：指針指向第四個元素8，此時其左面的元素6,7,9為有序的，將8抽離出來，形成6,7,9,,5,1，從9開始，依次與8比較，發(fā)現8<9，將9向后移，形成6,7,,9,5,1，8插入到空位中，結果為：6,7,8,9,5,1
第四輪：指針指向第五個元素5，此時其左面的元素6,7,8,9為有序的，將5抽離出來，形成6,7,8,9,,1，從9開始依次與5比較，發(fā)現5比其左側所有元素都小，5左側元素全部向右移動，形成,6,7,8,9,1，將5放入空位，結果5,6,7,8,9,1。
第五輪：同上，1被移到最左面，最后結果：1,5,6,7,8,9。
編碼分析:
需要兩層循環(huán)，第一層循環(huán)index表示上述例子中的指針，即遍歷從坐標為1開始的每一個元素；第二層循環(huán)從leftindex=index-1開始，leftindex--向左遍歷，將每一個元素與i處的元素比較，直到j處的元素小于i出的元素或者leftindex<0；遍歷從i到j的每一個元素使其右移，最后將index處的元素放到leftindex處的空位處。
插入排序動圖演示：
代碼實現：
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {7, 6, 9, 8, 5,1};
insertionSort(arr);
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
public static void insertionSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
for (int index = 1; index < arr.length; index++) {
for(int leftindex = index -1; leftindex >= 0 && arr[leftindex] > arr[leftindex + 1]; leftindex--) {
swap(arr, leftindex, leftindex + 1);
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
