排序

排序就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作

排序的穩定性

假若有以下數組，數組中存在兩個5，這里區分標記

如果排序之后，紅色的5仍然在藍色的5前面，我們就認為該排序是穩定的

穩定

反之如果打亂了原本紅色5在前的順序，我們就認為該排序是不穩定的排序

?不穩定

常見的排序

插入排序

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。在生活中我們玩斗地主的時候，洗牌就是用到了插入排序。

具體流程如下

第一個數據本身不用排序，從第二個數據開始，把前面兩個數據看成一組，然后讓1和該組的每一個元素進行比較如果找到合適的位置就插入

然后到第三個數據，這里發現已經有序則不進行改動

然后是第四個數據，一樣的，把第四個數據和該組內的所有數據比較，然后找到合適的位置插入

后面也同理

對數組排序完成之后我們發現，插入排序是一種穩定的排序

插入排序的特性

1. 元素集合越接近有序，直接插入排序算法的時間效率越高

2. 時間復雜度：O(N^2)（此篇幅里說到時間復雜度代表平均復雜度）

3. 空間復雜度：O(1)

4. 穩定性：穩定

代碼實現

 public static void insertSort(int[] array){for (int i = 1; i < array.length; i++) {int temp = array[i];int j = i-1;for (; j >= 0; j--) {if(array[j]>temp){array[j+1] =array[j];}else{break;}}array[j+1]=temp;}}

希爾排序

希爾排序法也叫做，縮小增量法。體現在排序當中就是對待排序列進行分組，每一組內分別排序，然后減少組數，直至減少到為一組，然后整體再進行排序，這樣做的好處是，在縮小為一整組之前，帶排序列的數據會基本趨近于有序的，這樣就可以減小復雜度。

這里有一組待排的數組，我們把數組分為五組，組內數據的間隔為5，然后進行分組排序。

然后再分為兩組，組內數據的間隔為2，然后再進行分組排序

可以發現當分量縮小為2的時候，數組內的數據已經基本趨于有序了，這個時候再縮小增量，就是一整組進行排序

代碼實現

 public static void shellSort(int[] array){int gap = array.length;while(gap>1){gap/=2;Shell(array,gap);}}private static void Shell(int[] array,int gap){for (int i = gap; i < array.length; i++) {int temp = array[i];int j = i-gap;for (; j >= 0; j-=gap) {if(array[j]>temp){array[j+gap] =array[j];}else{break;}}array[j+gap]=temp;}}

希爾排序的特性

1.?希爾排序是對直接插入排序的優化，當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很 快。這樣整體而言，可以達到優化的效果。

2. 時間復雜度：

最好情況：O(N)

平均情況：O(N^1.3)?希爾排序的時間復雜度并不是穩定的，N的1.3次方是Knuth在進行大量的實驗和測試得出了結論，所以我們認為希爾排序的時間復雜度是O(N^1.3)

最壞情況：O(N^2)

3. 空間復雜度：O(1)

4. 穩定性：不穩定

選擇排序

每一次從待排序的數據元素中選出最小的一個元素，存放在序列的起始位置，放完之后，然后再從第二個元素開始找到后面最小的元素，以此循環，直到全部待排序的數據元素排完。

我們要對這組數據進行選擇排序，先找第一個最小的數據，這里最小的數據為1，然后我們交換1?和 4

然后從第二個位置往后，再找最小的數據，最小數據為2，2?和 6交換

以此往復，得到結果

代碼實現

這里的selectSort2是另一種選擇排序的思路

 public static void selectSort(int[] array){for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i+1; j < array.length; j++) {if(array[j]<array[minIndex]){minIndex = j;}}swap(array,i,minIndex);}}public static void selectSort2(int[] array){int left = 0 ;int right = array.length-1;while(left<right){int minIndex = left;int maxIndex = left;for (int i = left+1; i <=right; i++) {if(array[i]<array[minIndex]){minIndex = i;}if(array[i]>array[maxIndex]){maxIndex = i;}}swap(array,left,minIndex);if(maxIndex==left){maxIndex = minIndex;}swap(array,right,maxIndex);left++;right--;}}private static void swap(int[] array,int a,int b){int temp = array[a];array[a] = array[b];array[b] = temp;}

選擇排序的特性

1. 直接選擇排序思考非常好理解，但是效率不是很好，實際中很少使用

2. 時間復雜度：O(N^2)

3. 空間復雜度：O(1)

4. 穩定性：不穩定

堆排序

前面了解堆這種數據結構的時候提到過堆分為大根堆和小根堆，這里要說到的堆排序就是基于大根堆和小根堆的特性來實現的。如果要求數據從小到大排序就建立大根堆，反之小根堆。

流程為：將一組數據建堆，這里以從小到大的排序為目標，建立一個大根堆，然后把堆頂元素和最后的元素進行交換，交換完成之后對堆頂進行向下調整，然后縮小調整的范圍，這樣堆的最后一個元素就是最大的元素了。

這里畫圖舉例，假若有一組數據為 1? 6? 2? 4? 10? 9? 3，對這組數據建立大根堆

然后交換堆頂元素和數組的最后一個元素

交換完成之后我們縮小調整的范圍，這樣10就不會受到后面調整的影響了，這里用紅圈標起來

調整為大根堆

然后再交換堆頂元素和最后一個元素

再對堆進行調整

以此往復

代碼實現

public static void heapSort(int[] array){createBigHeap(array);int end = array.length-1;while(end>0){swap(array,0,end);siftDown(array,0,end);end--;}}private static void createBigHeap(int[] array){for(int parent = (array.length-1-1)/2;parent>=0;parent--){siftDown(array,parent,array.length);}}private static void siftDown(int[] array,int parent,int end){int child=parent*2+1;while(child<end){if(child+1<end&&array[child+1]>array[child]){child++;}if(array[child]>array[parent]){swap(array,child,parent);parent = child;child= parent*2 +1;}else{break;}}}

堆排序的特性

1. 堆排序使用堆來選數，效率就高了很多。

2. 時間復雜度：O(N*logN)

3. 空間復雜度：O(1)

4. 穩定性：不穩定

冒泡排序

冒泡排序很簡單，這里不細細展開

代碼實現

這里進行了一點優化，可以減小復雜度

 public static void bubbleSort(int[] array) {for (int i = 0; i < array.length; i++) {boolean flag = false;//標記for (int j = 0; j < array.length-i-1; j++) {if(array[j]>array[j+1]){swap(array,j+1,j);flag=true;//如果走不到這一步}}if(flag==false){//說明已經有序，則從這里退出方法return ;}}}

冒泡排序的特性

1. 冒泡排序是一種非常容易理解的排序

2. 時間復雜度：O(N^2)

3. 空間復雜度：O(1)

4. 穩定性：穩定

快速排序

快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元 素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有 元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

快速排序的核心圍繞著定基準來進行

先說說第一種方法：Hoare法

以第一個數據為基準，然后定義兩個下標，先移動右下標，找到比key小的元素就停止，然后到左下標，移動左下標，找到比key大的元素就停止。

這里找到了9比6大，5比6小，然后交換兩個元素。

繼續移動，先右再左，找到目標

然后交換，先移動右下標

當左右下標相遇時停止，讓left或者right下標元素和最左邊的元素交換

此時發現以6為基準，6的左邊所有的元素都小于6，6右邊的所有元素都大于6

然后在把數組分為兩個部分，左邊的一組再以4為基準來定基準，右邊的一組再以8為基準來定基準以此循環，最終達到排序的效果。

第二種方法：挖坑法

同樣的順序，先移動右邊，遇到比key小的元素停下

然后把5挖起來蓋住左下標的位置

然后再移動左下標，找到比6大的元素

然后挖起來放到右下標的位置

然后右下標

然后左下標

然后右下標

當左右下標相遇時，把key放入相遇的位置

第三種方法：前后指針法

定義兩個下標，

然后按照以下規則移動和交換

取左邊下標為key，這里是6，如果J下標的元素小于key，移動I下標，如果I下標和J下標重合，則繼續移動J下標，直至不滿足條件位置，最后I下標和左邊的元素交換即可。

可以發現三種方法定基準的左右數據都把一樣，這里更加推薦使用挖坑法進行定基準

代碼實現

 private static int partition2(int[] array,int left ,int right) {//Hoare交換法求基準int key = array[left];//選left下標的數作為基準int i = left;//記錄下左邊下標while(left<right){while(left<right && array[right]>=key){//多加個判斷防止越界right--;//沒遇到比key小的就往前走}while(left<right && array[left]<=key){left++;//沒遇到比key大的就往后走}swap(array,left,right);//遇到大的在前，小的再后，此時就可以交換兩個下標的值}swap(array,i,right);//相遇之后交換基準和相遇的地方return left;//返回基準，這樣就可以做到，調整順序，和找基準}private static int partition(int[] array,int left ,int right) {//挖坑法int key = array[left];//選left下標的數作為基準while(left<right){while(left<right&&array[right]>key){right--;}array[left] = array[right];while(left<right&&array[left]<key){left++;}array[right] = array[left];}array[left]=key;return left;//挖坑法的優先度更高，因為會省去交換的操作，從而達到減小復雜度的效果}private static int partition3(int[] array,int left,int right){//前后指針法int front = left;int rear = left +1;while(rear<=right){if(array[rear]<array[left]&&array[++front]!=array[rear]){swap(array,rear,front);}rear++;}swap(array,front,left) ;return front;}

這里有一種特殊的情況，如果一組數據為 1 2 3 4 5 6 7? 這樣有序或者趨于有序的數據，此時還將左邊的第一個數據作為基準，就會使數據變成一顆單分支的二叉樹結構，此時的時間復雜度會增大，所以我們為了避免這樣的情況，這里需要盡可能的使基準定到數組中間的位置。

public static void quickSort(int[] array) {quick(array,0,array.length-1);}private static void quick(int[] array,int start,int end ){if(start>=end){return ;}int index = midOfThree(array,start,end);swap(array,index,start);int pivot = partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}private static int midOfThree(int[] array, int left , int right){//三數取中，優化基準的位置int mid = (left+right)/2;if (array[left] < array[right]) {if(array[mid]<array[left]){return left;}else if(array[mid]>array[right]){return right;}else{return mid;}}else{if(array[mid]>array[left]){return left;}else if(array[mid]<array[right]){return right;}else{return mid;}}}

快速排序的特性

1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序

2. 時間復雜度：O(N*logN)

3. 空間復雜度：O(logN)

4. 穩定性：不穩定

歸并排序

歸并排序是一種二叉樹結構的排序，核心思想就是把一組數據分成多分，然后再合并成有序的數組

代碼實現

public static void mergeSort(int[] array) {mergeSortFunction(array,0,array.length-1);}private static void mergeSortFunction(int[] array , int left ,int right) {if(left >=right){return ;}int mid = (left + right )/2;mergeSortFunction(array,left,mid);mergeSortFunction(array,mid+1,right);merge(array,left,right,mid);}private static void merge(int[] array,int left , int right , int mid) {int[] tempArray = new int[right-left+1];int s1 = left;int s2 = mid +1 ;int i = 0 ;while(s1<=mid&&s2<=right){if(array[s1]>=array[s2]){tempArray[i] = array[s2];i++;s2++;}else{tempArray[i] = array[s1];i++;s1++;}}while (s1<=mid){tempArray[i]=array[s1];i++;s1++;}while (s2<=right){tempArray[i]=array[s2];i++;s2++;}for (int j = 0; j < tempArray.length; j++) {array[j+left] = tempArray[j];}}

歸并排序的特性

1. 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。

2. 時間復雜度：O(N*logN)

3. 空間復雜度：O(N)

4. 穩定性：穩定