歡迎光臨
每天分享高質量文章
當前位置：知識星球 > 後端 > 正文

漫畫：什麼是快速排序？

2018-08-15 分類：後端 閱讀(236) 評論(0)

（點選上方公眾號，可快速關註）


來源：程式員小灰（微訊號：chengxuyuanxiaohui）

—————  第二天  —————




————————————


同氣泡排序一樣，快速排序也屬於交換排序，透過元素之間的比較和交換位置來達到排序的目的。


不同的是，氣泡排序在每一輪只把一個元素冒泡到數列的一端，而快速排序在每一輪挑選一個基準元素，並讓其他比它大的元素移動到數列一邊，比它小的元素移動到數列的另一邊，從而把數列拆解成了兩個部分。



這種思路就叫做分治法。


每次把數列分成兩部分，究竟有什麼好處呢？


假如給定8個元素的數列，一般情況下氣泡排序需要比較8輪，每輪把一個元素移動到數列一端，時間複雜度是O（n^2）。


而快速排序的流程是什麼樣子呢？

如圖所示，在分治法的思想下，原數列在每一輪被拆分成兩部分，每一部分在下一輪又分別被拆分成兩部分，直到不可再分為止。


這樣一共需要多少輪呢？平均情況下需要logn輪，因此快速排序演演算法的平均時間複雜度是 O（nlogn）。



基準元素的選擇


基準元素，英文pivot，用於在分治過程中以此為中心，把其他元素移動到基準元素的左右兩邊。


那麼基準元素如何選擇呢？


最簡單的方式是選擇數列的第一個元素：


這種選擇在絕大多數情況是沒有問題的。但是，假如有一個原本逆序的數列，期望排序成順序數列，那麼會出現什麼情況呢？

……….

我們該怎麼避免這種情況發生呢？


其實很簡單，我們可以不選擇數列的第一個元素，而是隨機選擇一個元素作為基準元素。


這樣一來，即使在數列完全逆序的情況下，也可以有效地將數列分成兩部分。


當然，即使是隨機選擇基準元素，每一次也有極小的機率選到數列的最大值或最小值，同樣會影響到分治的效果。


所以，快速排序的平均時間複雜度是 O（nlogn），最壞情況下的時間複雜度是 O（n^2）。

元素的移動


選定了基準元素以後，我們要做的就是把其他元素當中小於基準元素的都移動到基準元素一邊，大於基準元素的都移動到基準元素另一邊。


具體如何實現呢？有兩種方法：


1.挖坑法

2.指標交換法

何謂挖坑法？我們來看一看詳細過程。


給定原始數列如下，要求從小到大排序：


首先，我們選定基準元素Pivot，並記住這個位置index，這個位置相當於一個“坑”。並且設定兩個指標left和right，指向數列的最左和最右兩個元素：



接下來，從right指標開始，把指標所指向的元素和基準元素做比較。如果比pivot大，則right指標向左移動；如果比pivot小，則把right所指向的元素填入坑中。


在當前數列中，1<4，所以把1填入基準元素所在位置，也就是坑的位置。這時候，元素1本來所在的位置成為了新的坑。同時，left向右移動一位。



此時，left左邊綠色的區域代表著小於基準元素的區域。


接下來，我們切換到left指標進行比較。如果left指向的元素小於pivot，則left指標向右移動；如果元素大於pivot，則把left指向的元素填入坑中。


在當前數列中，7>4，所以把7填入index的位置。這時候元素7本來的位置成為了新的坑。同時，right向左移動一位。



此時，right右邊橙色的區域代表著大於基準元素的區域。


下麵按照剛才的思路繼續排序：


8>4，元素位置不變，right左移


2<4，用2來填坑，left右移，切換到left。


6>4，用6來填坑，right左移，切換到right。


3<4，用3來填坑，left右移，切換到left。


5>4，用5來填坑，right右移。這時候left和right重合在了同一位置。


這時候，把之前的pivot元素，也就是4放到index的位置。此時數列左邊的元素都小於4，數列右邊的元素都大於4，這一輪交換終告結束。


public class QuickSort {

  1. public static void quickSort(int[] arr, int startIndex, int endIndex) {
  2.     // 遞迴結束條件：startIndex大等於endIndex的時候
  3.     if (startIndex >= endIndex) {
  4.         return;
  5.     }
  6.     // 得到基準元素位置
  7.     int pivotIndex = partition(arr, startIndex, endIndex);
  8.     // 用分治法遞迴數列的兩部分
  9.     quickSort(arr, startIndex, pivotIndex - 1);
  10.     quickSort(arr, pivotIndex + 1, endIndex);
  11. }

  14. private static int partition(int[] arr, int startIndex, int endIndex) {
  15.     // 取第一個位置的元素作為基準元素
  16.     int pivot = arr[startIndex];
  17.     int left = startIndex;
  18.     int right = endIndex;
  19.     // 坑的位置，初始等於pivot的位置
  20.     int index = startIndex;
  22.     //大迴圈在左右指標重合或者交錯時結束
  23.     while ( right >= left  ){
  24.         //right指標從右向左進行比較
  25.         while ( right >= left ) {
  26.             if (arr[right] < pivot) {
  27.                 arr[left] = arr[right];
  28.                 index = right;
  29.                 left++;
  30.                 break;
  31.             }
  32.             right--;
  33.         }
  34.         //left指標從左向右進行比較
  35.         while ( right >= left ) {
  36.             if (arr[left] > pivot) {
  37.                 arr[right] = arr[left];
  38.                 index = left;
  39.                 right--;
  40.                 break;
  41.             }
  42.             left++;
  43.         }
  44.     }
  45.     arr[index] = pivot;
  46.     return index;
  47. }

  50. public static void main(String[] args) {
  51.     int[] arr = new int[] {4,7,6,5,3,2,8,1};
  52.     quickSort(arr, 0, arr.length-1);
  53.     System.out.println(Arrays.toString(arr));
  54. }

}

程式碼中，quickSort方法透過遞迴的方式，實現了分而治之的思想。


partition方法則實現元素的移動，讓數列中的元素依據自身大小，分別移動到基準元素的左右兩邊。在這裡，我們使用移動方式是挖坑法。


指標交換法


何謂指標交換法？我們來看一看詳細過程。


給定原始數列如下，要求從小到大排序：



開局和挖坑法相似，我們首先選定基準元素Pivot，並且設定兩個指標left和right，指向數列的最左和最右兩個元素：


接下來是第一次迴圈，從right指標開始，把指標所指向的元素和基準元素做比較。如果大於等於pivot，則指標向左移動；如果小於pivot，則right指標停止移動，切換到left指標。


在當前數列中，1<4，所以right直接停止移動，換到left指標，進行下一步行動。


輪到left指標行動，把指標所指向的元素和基準元素做比較。如果小於等於pivot，則指標向右移動；如果大於pivot，則left指標停止移動。


由於left一開始指向的是基準元素，判斷肯定相等，所以left右移一位。

由於7 > 4，left指標在元素7的位置停下。這時候，我們讓left和right指向的元素進行交換。

接下來，我們進入第二次迴圈，重新切換到right向左移動。right先移動到8，8>2，繼續左移。由於2<8，停止在2的位置。


切換到left，6>4，停止在6的位置。



元素6和2交換。


進入第三次迴圈，right移動到元素3停止，left移動到元素5停止。



元素5和3交換。


進入第四次迴圈，right移動到元素3停止，這時候請註意，left和right指標已經重合在了一起。




當left和right指標重合之時，我們讓pivot元素和left與right重合點的元素進行交換。此時數列左邊的元素都小於4，數列右邊的元素都大於4，這一輪交換終告結束。





public class QuickSort {

  1. public static void quickSort(int[] arr, int startIndex, int endIndex) {
  2.     // 遞迴結束條件：startIndex大等於endIndex的時候
  3.     if (startIndex >= endIndex) {
  4.         return;
  5.     }
  6.     // 得到基準元素位置
  7.     int pivotIndex = partition(arr, startIndex, endIndex);
  8.     // 根據基準元素，分成兩部分遞迴排序
  9.     quickSort(arr, startIndex, pivotIndex - 1);
  10.     quickSort(arr, pivotIndex + 1, endIndex);
  11. }

  14. private static int partition(int[] arr, int startIndex, int endIndex) {
  15.     // 取第一個位置的元素作為基準元素
  16.     int pivot = arr[startIndex];
  17.     int left = startIndex;
  18.     int right = endIndex;
  20.     while( left != right) {
  21.         //控制right指標比較並左移
  22.         while(left pivot){
  23.             right--;
  24.         }
  25.         //控制right指標比較並右移
  26.         while( left
  27.             left++;
  28.         }
  29.         //交換left和right指向的元素
  30.         if(left
  31.             int p = arr[left];
  32.             arr[left] = arr[right];
  33.             arr[right] = p;
  34.         }
  35.     }
  37.     //pivot和指標重合點交換
  38.     int p = arr[left];
  39.     arr[left] = arr[startIndex];
  40.     arr[startIndex] = p;
  42.     return left;
  43. }

  46. public static void main(String[] args) {
  47.     int[] arr = new int[] {4,7,6,5,3,2,8,1};
  48.     quickSort(arr, 0, arr.length-1);
  49.     System.out.println(Arrays.toString(arr));
  50. }

}

和挖坑法相比，指標交換法在partition方法中進行的元素交換次數更少。

非遞迴實現




為什麼這樣說呢？


因為我們程式碼中一層一層的方法呼叫，本身就是一個函式棧。每次進入一個新方法，就相當於入棧；每次有方法傳回，就相當於出棧。


所以，我們可以把原本的遞迴實現轉化成一個棧的實現，在棧當中儲存每一次方法呼叫的引數：


下麵我們來看一下程式碼：


public class QuickSortWithStack {

  1. public static void quickSort(int[] arr, int startIndex, int endIndex) {
  2.     // 用一個集合棧來代替遞迴的函式棧
  3.     Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();
  4.     // 整個數列的起止下標，以雜湊的形式入棧
  5.     Map rootParam = new HashMap();
  6.     rootParam.put("startIndex", startIndex);
  7.     rootParam.put("endIndex", endIndex);
  8.     quickSortStack.push(rootParam);
  10.     // 迴圈結束條件：棧為空時結束
  11.     while (!quickSortStack.isEmpty()) {
  12.         // 棧頂元素出棧，得到起止下標
  13.         Map<String, Integer> param = quickSortStack.pop();
  14.         // 得到基準元素位置
  15.         int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
  16.         // 根據基準元素分成兩部分, 把每一部分的起止下標入棧
  17.         if(param.get("startIndex") <  pivotIndex -1){
  18.             Map<String, Integer> leftParam = new HashMap<String, Integer>();
  19.             leftParam.put("startIndex",  param.get("startIndex"));
  20.             leftParam.put("endIndex", pivotIndex -1);
  21.             quickSortStack.push(leftParam);
  22.         }
  23.         if(pivotIndex + 1 < param.get("endIndex")){
  24.             Map<String, Integer> rightParam = new HashMap<String, Integer>();
  25.             rightParam.put("startIndex", pivotIndex + 1);
  26.             rightParam.put("endIndex", param.get("endIndex"));
  27.             quickSortStack.push(rightParam);
  28.         }
  29.     }
  30. }
  32. private static int partition(int[] arr, int startIndex, int endIndex) {
  33.     // 取第一個位置的元素作為基準元素
  34.     int pivot = arr[startIndex];
  35.     int left = startIndex;
  36.     int right = endIndex;
  38.     while( left != right) {
  39.         //控制right指標比較並左移
  40.         while(left pivot){
  41.             right--;
  42.         }
  43.         //控制right指標比較並右移
  44.         while( left
  45.             left++;
  46.         }
  47.         //交換left和right指向的元素
  48.         if(left
  49.             int p = arr[left];
  50.             arr[left] = arr[right];
  51.             arr[right] = p;
  52.         }
  53.     }
  55.     //pivot和指標重合點交換
  56.     int p = arr[left];
  57.     arr[left] = arr[startIndex];
  58.     arr[startIndex] = p;
  60.     return left;
  61. }
  63. public static void main(String[] args) {
  64.     int[] arr = new int[] {4,7,6,5,3,2,8,1};
  65.     quickSort(arr, 0, arr.length-1);
  66.     System.out.println(Arrays.toString(arr));
  67. }

}

和剛才的遞迴實現相比，程式碼的變動僅僅在quickSort方法當中。該方法中引入了一個儲存Map型別元素的棧，用於儲存每一次交換時的起始下標和結束下標。


每一次迴圈，都會讓棧頂元素出棧，進行排序，並且按照基準元素的位置分成左右兩部分，左右兩部分再分別入棧。當棧為空時，說明排序已經完畢，退出迴圈。





幾點補充：


本漫畫純屬娛樂，還請大家儘量珍惜當下的工作，切勿模仿哦。

【關於投稿】


如果大家有原創好文投稿，請直接給公號傳送留言。


① 留言格式：
【投稿】+《 文章標題》+ 文章連結

② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：http://blog.jobbole.com/94148/


③ 最後請附上您的個人簡介哈~



覺得本文有幫助？請分享給更多人

關註「演演算法愛好者」，修煉程式設計內功

贊(0)
標籤：

相關推薦

熱門標籤

iOS (11238)微軟 (4955)Linux (4274)安全 (4180)Python (4161)效能 (3165)運維 (2774)最佳化 (2419).NET (2262)Google (2136)機器學習 (1795)併發 (1613)分散式 (1559)叢集 (1240)SQL (1174)Mysql (1060)區塊鏈 (1017)Docker (977)微服務 (922)面試 (919)Apache (743)NLP (725)Redis (719)Android (668)Git (640)架構師 (632)Nginx (630)Facebook (599)JVM (595)爬蟲 (476)

熱門文章

分享創造快樂

© 2024 知識星球   網站地圖