快速排序的簡單理解

優質資源分享

學習路線指引（點擊解鎖）	知識定比特	人群定比特
🧡 Python實戰微信訂餐小程序 🧡	進階級	本課程是python flask+微信小程序的完美結合，從項目搭建到騰訊雲部署上線，打造一個全棧訂餐系統。
Python量化交易實戰	入門級	手把手帶你打造一個易擴展、更安全、效率更高的量化交易系統

詳細描述

快速排序通過一趟排序將待排序列分割成獨立的兩部分，其中一部分序列的關鍵字均比另一部分序列的關鍵字小，則可分別對這兩部分序列繼續進行排序，以達到整個序列有序的目的。

快速排序詳細的執行步驟如下：

1. 從序列中挑出一個元素，稱為 “基准”（pivot）；
2. 重新排序序列，所有比基准值小的元素擺放在基准前面，所有比基准值大的元素擺在基准的後面（相同的數可以到任一邊）。在這個分區退出之後，該基准就處於序列的中間比特置。這個稱為分區（partition）操作；
3. 遞歸地（recursive）把小於基准值元素的子序列和大於基准值元素的子序列排序。

算法圖解

問題解疑

快速排序可以怎樣選擇基准值？

第一種方式：固定比特置選擇基准值；在整個序列已經趨於有序的情况下，效率很低。

第二種方式：隨機選取待排序列中任意一個數作為基准值；當該序列趨於有序時，能够讓效率提高，但在整個序列數全部相等的時候，隨機快排的效率依然很低。

第三種方式：從區間的首、尾、中間，分別取出一個數，然後對比大小，取這 3 個數的中間值作為基准值；這種方式解决了很多特殊的問題，但對於有很多重複值的序列，效果依然不好。

快速排序有什麼好的優化方法？

首先，合理選擇基准值，將固定比特置選擇基准值改成三點取中法，可以解决很多特殊的情况，實現更快地分區。

其次，當待排序序列的長度分割到一定大小後，使用插入排序。對於待排序的序列長度很小或基本趨於有序時，插入排序的效率更好。

在排序後，可以將與基准值相等的數放在一起，在下次分割時可以不考慮這些數。對於解决重複數據較多的情况非常有用。

在實現上，遞歸實現的快速排序在函數尾部有兩次遞歸操作，可以對其使用尾遞歸優化（簡單地說，就是尾比特置調用自身）。

代碼實現

|  | package cn.fatedeity.algorithm.sort; |
|  |  |
|  | import java.util.Random; |
|  |  |
|  | /** |
|  |  * 快速排序算法 |
|  |  */ |
|  | public class QuickSort { |
|  | private static void swap(int[] numbers, int src, int target) { |
|  | int temp = numbers[src]; |
|  |  numbers[src] = numbers[target]; |
|  |  numbers[target] = temp; |
|  |  } |
|  |  |
|  | private static int[] sort(int[] numbers, int low, int high) { |
|  | if (low > high) { |
|  | return numbers; |
|  |  } |
|  | // 隨機數取基准值 |
|  | Random random = new Random(); |
|  | int pivotIndex = random.nextInt(low, high + 1); |
|  | int pivot = numbers[pivotIndex]; |
|  |  swap(numbers, pivotIndex, low); |
|  |  |
|  | int mid = low + 1; |
|  | for (int i = low + 1; i <= high; i++) { |
|  | if (numbers[i] < pivot) { |
|  |  swap(numbers, i, mid); |
|  |  mid++; |
|  |  } |
|  |  } |
|  |  swap(numbers, low, --mid); |
|  |  sort(numbers, low, mid - 1); |
|  |  sort(numbers, mid + 1, high); |
|  | return numbers; |
|  |  } |
|  |  |
|  | public static int[] sort(int[] numbers) { |
|  | return sort(numbers, 0, numbers.length - 1); |
|  |  } |
|  | } |