入秋的第一篇数据结构算法：看看归并与快排的风采
程序猿正能量
靠代碼行數來衡量開發進度,就像是憑重量來衡量飛機制造的進度。—比爾·蓋茨
前言
作為開發人員，尤其是三年以上工作經驗的 ，如果整天都是在CRUD，這個時候，你是不是需要憧憬一下35歲之后的生活呢？退休送外賣還是回老家種田呢？因為你除了CRUD，其他你一概不會，所以這個時候，你需要改變一下自己，比如：學習數據結構與算法俗話說的好，算法是程序員的靈魂，只有觸及到靈魂深處，你才能看見詩和遠方，加油吧，騷年！
目錄
- 程序猿正能量
- 前言
- 一、我們這篇文章講什么呢？
- 二、歸并排序
- 1.什么是歸并排序
- 3.時間空間復雜度分析
- 三、快速排序
- 1.什么是快速排序
- 2.時間空間復雜度分析
- 總結
一、我們這篇文章講什么呢？
既然都說了算法是一個程序猿的靈魂，那么我們當然是要沖擊一下靈魂了，沒錯，這篇文章我們將算法：歸并排序和快速排序。
二、歸并排序
1.什么是歸并排序
歸并排序（Merge Sort）是建立在歸并操作上的一種有效，穩定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
根據概念和動圖，你是否能看明白呢？也許還有點懵吧，其實歸并就是借助了分治的思想，把一個大問題拆分成許多個小問題，然后解決小問題，小問題解決了，大問題自然就解決了，這個時候你可能有點疑惑了,剛剛說的這個不就是遞歸嗎？為什么又成分治了呢？這里大家要搞明白一點：分治是一種思想，遞歸是一種實現技巧。
也許上面的動圖不太好理解，那么請看下圖
先將需要排序的數組進行拆解，拆解到只有兩個元素二點之后進行排序，然后在合并，如此反復，即可得到一個完全有序的數組。
下面我們就一起來使用分治思想、遞歸方案來實現歸并排序。
## 2.利用遞歸實現歸并排序 package com.liuxing.sort;import com.liuxing.util.Print;/*** @author liuxing007* @ClassName MergeSort* @Description 歸并排序（Merge Sort）* 歸并排序的核心思想還是蠻簡單的。如果要排序一個數組，* 我們先把數組從中間分成前后兩部分，然后對前后兩部分分別排序，* 再將排好序的兩部分合并在一起，這樣整個數組就都有序了。** 時間復雜度：O(nlogn)* 空間復雜度：O(n)* 不是原地排序算法* @date 2020/9/17 15:04*/public class MergeSort {public static void main(String[] args) {int[] arr = new int[]{6,4,1,7,2,5,8,3};int length = arr.length;System.out.println("排序前數組===========");Print.print(arr, length);sort(arr, length);System.out.println("排序后數組===========");Print.print(arr, length);}/*** 排序算法* @param arr 數組* @param l 數組長度*/private static void sort(int[] arr,int l){sortMerge(arr,0,l-1);}/*** 遞歸* @param arr 數組* @param p 開始位置下表* @param r 結束位置下表*/private static void sortMerge(int[] arr,int p,int r){if(p >= r){return ;}//分治的下標，這里我采用p到r的中間位置index。int index = p + (r-p)/2;//左側遞歸sortMerge(arr,p,index);//右側遞歸sortMerge(arr, index + 1, r);merge(arr, p, index,r);System.out.println("排序后數組===========");Print.print(arr, length);}/*** 合并計算* @param arr 原素組* @param l 左側數組開始位置下標* @param index 左側數組結束位置下標* @param r 右側數組結束位置下標*/private static void merge(int[] arr, int l,int index, int r) {//臨時數組，這里可以優化，數組的頻繁創建會降低程序運行的效率，// 所以這里可以將這個臨時數組改成參數傳遞進來，在數量較大的時候執行效率變化變焦顯著int[] temp = new int[r-l+1];//左側開始下標int i= l;//右側開始下標int j = index+1;//臨時數組下標int k=0;// 左側數組與右側數組進行對比，將小的元素放入臨時數組中while(i<=index && j<=r){if(arr[i]<arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}//對比完成之后，需要把兩側數組中還沒有對比的數據加入到臨時數組中//把左邊剩余元素加入臨時數組中while(i<=index){temp[k++] = arr[i++];}//把右邊剩余元素加入臨時數組中while(j<=r){temp[k++] = arr[j++];}//將臨時數組的元素拷貝原數組中for(int x=0;x<temp.length;x++){arr[x+l] = temp[x];}}} package com.liuxing.util;/*** @author liuxing007* @ClassName Print* @Description 打印* @date 2020/9/17 11:13*/ public class Print {/**** 打印數據* @param arr 數組* @param length 數組長度*/public static void print(int[] arr, int length) {for (int i = 0; i < length; ++i) {System.out.print(arr[i] + " ");}System.out.println("");}} 排序前數組=========== 6 4 1 7 2 5 8 3 合并后的數據 4 6 1 7 2 5 8 3 合并后的數據 4 6 1 7 2 5 8 3 合并后的數據 1 4 6 7 2 5 8 3 合并后的數據 1 4 6 7 2 5 8 3 合并后的數據 1 4 6 7 2 5 3 8 合并后的數據 1 4 6 7 2 3 5 8 合并后的數據 1 2 3 4 5 6 7 8 排序后數組=========== 1 2 3 4 5 6 7 8 Process finished with exit code 0
3.時間空間復雜度分析
我們假設對 n 個元素進行歸并排序需要的時間是 T(n)，那分解成兩個子數組排序的時間都是 T(n/2)。我們知道，merge() 函數合并兩個有序子數組的時間復雜度是 O(n)。所以，套用前面的公式，歸并排序的時間復雜度的計算公式就是：
T(1) = C； n=1時，只需要常量級的執行時間，所以表示為C。 T(n) = 2*T(n/2) + n； n>1通過這個公式，如何來求解 T(n) 呢？還不夠直觀？那我們再進一步分解一下計算過程。
T(n) = 2*T(n/2) + n = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n = 8*(2*T(n/16) + n/8) + 3*n= 16*T(n/16) + 4*n...... = 2^k * T(n/2^k) + k * n ......通過這樣一步一步分解推導，我們可以得到 T(n) = 2k2^k2k T(n/2k2^k2k)+kn。當 T(n/2kn/2^kn/2k)=T(1) 時，也就是 2k2^k2k=1，我們得到 k=log2nlog_2nlog2?n 。我們將 k 值代入上面的公式，得到 T(n)=Cn+log2nlog_2nlog2?n 。如果我們用大 O 標記法來表示的話，T(n) 就等于 O(nlogn)。所以歸并排序的時間復雜度是 O(nlogn)。從我們的原理分析和偽代碼可以看出，歸并排序的執行效率與要排序的原始數組的有序程度無關，所以其時間復雜度是非常穩定的，不管是最好情況、最壞情況，還是平均情況，時間復雜度都是 O(nlogn)-----摘自-極客時間-數據結構與算法-王爭
歸并排序的時間復雜度已經很優秀了，但為什么我們在日常開發中卻很少看到他的身影呢？我們先來分析一下歸并排序的空間復雜度。
我們需要注意的是合并方法，這個方法中我們使用了一個臨時數組用來存儲數據，但是合并之后這個臨時數組就會釋放，又因為臨時數組的最大長度不會超過原始數組長度n，所以歸并排序的空間復雜度為：O(n)
為什么開發中很少人使用到歸并排序呢？原因很簡單，因為它不是一個原地排序算法，這個時候你可能會有疑惑了，什么是原地排序算法？簡單來說：不通過其他空間來完成的排序，我們稱它為原地排序算法，但歸并排序很明顯借用了一個臨時數組，所以它不是一個原地排序算法，即使它的時間復雜都很穩定，使用的人也比較少。
三、快速排序
1.什么是快速排序
如果要排序數組中下標從 p 到 r 之間的一組數據， 我們選擇 p 到 r 之間的任意一個數據作為 pivot（分區點）。我們遍歷 p 到 r 之間的數據，將小于 pivot 的放到左邊， 將大于 pivot 的放到右邊，將 pivot 放到中間。經過這一步驟之后， 數組 p 到 r 之間的數據就被分成了三個部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的.根據分治、遞歸的處理思想，我們可以用遞歸排序下標從 p 到 q-1 之間的數據和下標從 q+1 到 r 之間的數據，直到區間縮小為 1，就說明所有的數據都有序了。（摘自-極客時間-數據結構與算法-王爭）
快速排序的思想和歸并排序有點類似，都是通過分治的思想，利用遞歸實現排序，只不過實現的細節有所不同，快排（快速排序）需要一個分區點，可以在數組中隨便去一個元素作為分區點即可，后面就是前面講到的概念了，歸并的核心在于合并，而快排的核心在于分區點，所以我們就一起來看看在獲取分區點的時候快排都干了些啥？
之前說過，快排選擇一個分區點（pivot）之后，將小于分區點（pivot）的元素放左邊，分區點（pivot）放中間，大于分區點（pivot）的放右邊，這個一看就很好解決嘛，和歸并排序一樣，我先申請兩個臨時數組，一個存放小于分區點元素的數組，一個存放大于分區點元素的數組，這樣，就能完美的解決了，非常簡單，但是這個就和歸并排序面臨這同一樣的一個問題：它不是一個原地排序算法，那如果我希望快排是一個原地排序算法呢？我們應該如何實現呢？其實也不難，我們可以參考一下選擇排序：【數據結構與算法】常見的三種排序（冒泡排序、插入排序、選擇排序）
我們定義一個游標 i (數組下標) 把數組a[p-(r-1)]分成兩部分，A[p-(i-1)]都是小于分區點（pivot）的，我們叫他“已排序區間”。a[(i+1) - (r-1)]都是大于分區點（pivot）元素的，我們叫他“未排序區間”，只要從未排序區間去值與分區點（pivot）進行比較，如果小于分區點（pivot），那么將此元素追加到已排序區間中（a[i]），否者不需要變動。
我還是準備了一張圖給大家參考，也許大家就能明白了。
這是一次分區交換的結果，當把所有分區都交換完成之后，整個數組也就有序了，既然快速排序的思想已經講的差不多了，下面我們一起來看看代碼怎么實現
快排代碼實現
package com.liuxing.sort;import com.liuxing.util.DataUtil; import com.liuxing.util.Print;/*** @author liuxing007* @ClassName Quicksort* @Description 快速排序** 如果要排序數組中下標從 p 到 r 之間的一組數據，* 我們選擇 p 到 r 之間的任意一個數據作為 pivot（分區點）。* 我們遍歷 p 到 r 之間的數據，將小于 pivot 的放到左邊，* 將大于 pivot 的放到右邊，將 pivot 放到中間。經過這一步驟之后，* 數組 p 到 r 之間的數據就被分成了三個部分，* 前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，* 后面的 q+1 到 r 之間是大于 pivot 的.* 根據分治、遞歸的處理思想，* 我們可以用遞歸排序下標從 p 到 q-1 之間的數據和下標從 q+1 到 r 之間的數據，* 直到區間縮小為 1，就說明所有的數據都有序了（摘自-極客時間-數據結構與算法-王爭）** 時間復雜度：O(nlogn)* 空間復雜度：O(1)* 原地排序算法，但不是穩點排序算法* @date 2020/9/18 10:22*/ public class Quicksort {public static void main(String[] args) {int[] arr = new int[]{6, 5, 4, 3, 2, 1}; // int[] arr = DataUtil.createIntArrData();int length = arr.length;System.out.println("排序前數組===========");Print.print(arr, length);sort(arr, length);System.out.println("排序后數組===========");Print.print(arr, length);}/*** 排序算法* @param arr 數組* @param l 數組長度*/private static void sort(int[] arr,int l){sortRec(arr,0,l-1);}/*** 遞歸* @param arr* @param p* @param r*/private static void sortRec(int[] arr, int p, int r) {//遞歸終止條件if (p >= r){return;}//獲取分區點int q = partition(arr, p, r);//左側遞歸sortRec(arr, p, q-1);//右側遞歸sortRec(arr, q+1, r);}/*** 分區* @param arr 原始數組* @param p 數組起始下標* @param r 數組結束下標* @return 分區下標*/private static int partition(int[] arr, int p, int r) {//取最后一個元素作為分區的值int pivot = arr[r];int i = p;for(int j = p; j < r; ++j) {if (arr[j] < pivot) {if (i == j) {++i;} else {//交換位置int tmp = arr[i];arr[i++] = arr[j];arr[j] = tmp;}}}//交換位置int tmp = arr[i];arr[i] = arr[r];arr[r] = tmp;return i;}} 排序前數組=========== 6 5 4 10 2 1 排序后數組=========== 1 2 4 5 6 10 Process finished with exit code 02.時間空間復雜度分析
快排的實現方式與歸并排序一樣，都是通過遞歸實現，所以他們的時間復雜度是一樣的：O(nlogn)，但是它是一種不穩定的排序算法，當極端條件下，他的時間復雜度將會衰減到O(n^2)，為什么這樣說呢？如果我們的原始數組就是一個有序數組，分區點還是選擇最后一個，那么就會出現一邊有數據，一邊沒有數據，這樣性能會急速下滑，所以在使用快排的時候分區點很重要。
然后我們再來看看快排的空間復雜度，快排在交換的的時候沒有使用到其他數組或者空間，所以他是一個原地排序算法，交換的時候只涉及到兩個元素，所以不難分析空間復雜度為：O(1)，
所以快排時間復雜度：O(nlogn)，龍劍復雜度：O(1)，極端情況下時間復雜度會退化到O(n^2)，優化過的快排除外。
總結
歸并排序是一種穩定、非原地的排序算法，時間復雜度：O(nlogn)，空間復雜度：O(n)。
快排時間是一種非穩定，原地排序算法，復雜度：O(nlogn)，空間復雜度：O(1)，極端情況下時間復雜度會退化到O(n^2)，優化過的快排除外。
雖然歸并排序算法比快速排序算法穩定，但是日常開發中，使用較多還是快排，為什么呢？原因很簡單，歸并排序不是原地排序。
源碼地址：https://github.com/361426201/java_TIPS/tree/master/data-structures-and-algorithms
好了騷年，看完了，不點贊收藏嗎？
總結
以上是生活随笔為你收集整理的入秋的第一篇数据结构算法：看看归并与快排的风采的全部內容，希望文章能夠幫你解決所遇到的問題。
