快速排序 Quick Sort
1. 演算法程序
快速排序(Quick Sort)使用分治法策略，
它的基本思想是：選擇一個基準數，通過一趟排序將要排序的資料分割成獨立的兩部分；其中一部分的所有資料都比另外一部分的所有資料都要小，然后，再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列，
快速排序流程：
(1) 從數列中挑出一個基準值，
(2) 將所有比基準值小的擺放在基準前面，所有比基準值大的擺在基準的后面(相同的數可以到任一邊)；在這個磁區退出之后，該基準就處于數列的中間位置，
(3) 遞回地把"基準值前面的子數列"和"基準值后面的子數列"進行排序，
上述文字來源： https://www.cnblogs.com/skywang12345/p/3596746.html
推薦幫助理解的文章： https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html
2.可視化展示
圖源：https://timewentby.com/language/java/543.html
3. 代碼實作
python版本：
1 # 對nums[l...r]部分進行partition操作 2 # 回傳j, 使得nums[l...j-1] < arr[j] ; nums[j+1...r] > arr[j] 3 def __partition(nums, left, right): 4 refer = nums[left] # 參照數值，這里取傳入的最左邊部分 5 6 j = left 7 for i in range(left + 1, right + 1): 8 if nums[i] < refer: 9 nums[j + 1], nums[i] = nums[i], nums[j + 1] 10 j += 1 11 nums[left], nums[j] = nums[j], nums[left] 12 13 return j 14 15 16 def __quick_sort(nums, left, right): 17 if left >= right: 18 return 19 20 p = __partition(nums, left, right) 21 __quick_sort(nums, left, p) 22 __quick_sort(nums, p + 1, right) 23 24 25 def quick_sort(nums): 26 __quick_sort(nums, 0, len(nums) - 1)
C++版本：
1 // 對arr[l...r]部分進行partition操作 2 template<typename T> 3 int __partition(T arr[],int l, int r) { 4 5 T refer = arr[l]; 6 7 int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v 8 for (int i = l + 1; i <= r; i++) { 9 if (arr[i] < refer) 10 swap(arr[++j], arr[i]); 11 } 12 swap(arr[l], arr[j]); 13 14 return j; 15 } 16 17 // 對arr[l...r]部分進行快速排序 18 template<typename T> 19 void __quickSort(T arr[], int l, int r) { 20 21 if (l >= r) 22 return; 23 24 int p = __partition(arr, l, r); 25 __quickSort(arr, l, p); 26 __quickSort(arr, p + 1, r); 27 } 28 29 template<typename T> 30 void quickSort(T arr[], int n) { 31 32 __quickSort(arr, 0, n - 1); 33 }
4. 演算法優化
類似于歸并排序，快速排序也是將整個陣列一分為二（小于標定點的部分和大于標定點的部分），整個程序也會行程一棵二叉樹，但區別在于，歸并排序的劃分是均勻地一分為二，產生的二叉樹高度近乎為logn，而上面實作的快速排序有在順序性較強的時候，劃分的兩個部分是極度偏斜的，就會產生平衡性很差的樹，最差的情況會退化成O（n2）級別的演算法，（形成的二叉樹退化成了鏈表）
改進方式：在partition操作之前先隨機選擇一個元素與最左邊元素交換， 也可以再加入對小規模陣列進行插入排序的優化，
C++ 實作：
// 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot swap( arr[l] , arr[rand()%(r-l+1)+l] );
5. 雙路快速排序
上述的實作方法是默認把等于標定元素的值都放在了右半部分，如果等于標定元素的數值過多，即陣列中存在大量的重復元素時，此時partition的劃分仍會十分偏斜，再次退化，
雙路快排的程序：
圖源：https://segmentfault.com/a/1190000021726667
python版本：
1 def insertion_sort(nums, left, right): 2 for i in range(left + 1, right + 1): 3 pre = i - 1 4 cur_num = nums[i] 5 while pre >= left and nums[pre] > cur_num: 6 nums[pre + 1] = nums[pre] 7 pre -= 1 8 nums[pre + 1] = cur_num 9 10 11 # 雙路快速排序的partition 12 # 回傳j, 使得arr[l...j-1] < arr[j] ; arr[j+1...r] > arr[j] 13 def __partition_two_way(nums, left, right): 14 # 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot 15 rand_index = random.randint(left, right) 16 nums[left], nums[rand_index] = nums[rand_index], nums[left] 17 refer = nums[left] 18 19 i, j = left + 1, right 20 """ 21 注意這里的邊界：用小于和大于號，遇到大量相等的partition元素的時候， 22 15 程式可以通過i++,j++使得樹的分裂點更居中，因此樹也更趨于平衡 23 16 而用小于等于和大于等于方式則會將連續出現的這些值歸為其中一方，使得兩棵子樹不平衡 24 """ 25 while True: 26 while i <= right and nums[i] < refer: 27 i += 1 28 while j >= left + 1 and nums[j] > refer: 29 j -= 1 30 if i > j: 31 break 32 nums[i], nums[j] = nums[j], nums[i] 33 i += 1 34 j -= 1 35 nums[left], nums[j] = nums[j], nums[left] 36 return j 37 38 39 def __quick_sort(nums, left, right): 40 if right - left <= 15: # 當資料規模很小的時候采用插入排序 41 insertion_sort(nums, left, right) 42 return 43 44 p = __partition_two_way(nums, left, right) 45 __quick_sort(nums, left, p) 46 __quick_sort(nums, p + 1, right) 47 48 49 def quick_sort(nums): 50 __quick_sort(nums, 0, len(nums) - 1)
C++版本：
1 // 雙路快速排序的partition 2 // 回傳j, 使得arr[l...j-1] < arr[j] ; arr[j+1...r] > arr[j] 3 template<typename T> 4 void __partitionTwoWay(T arr[], int l, int r) { 5 6 // 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot 7 swap(arr[l], arr[rand() % (r - l + 1) + l]); 8 T refer = arr[l]; 9 10 // arr[l+1...i) <= v; arr(j...r] >= v 11 int i = l + 1, j = r; 12 while (true) 13 { 14 // 注意這里的邊界：用小于和大于號，遇到大量相等的partition元素的時候， 15 // 程式可以通過i++,j++使得樹的分裂點更居中，因此樹也更趨于平衡 16 // 而用小于等于和大于等于方式則會將連續出現的這些值歸為其中一方，使得兩棵子樹不平衡 17 while (i<=r && arr[i] < refer) i++; 18 while (j >= l && arr[j] > refer) j--; 19 if (i > j) break; 20 swap(arr[i], arr[j]); 21 i++; 22 j--; 23 } 24 25 swap(arr[l], arr[j]); 26 return j; 27 } 28 29 // 對arr[l...r]部分進行快速排序 30 template <typename T> 31 void _quickSort(T arr[], int l, int r) { 32 33 // 對于小規模陣列, 使用插入排序進行優化 34 if (r - l <= 15) { 35 insertionSort(arr, l, r); 36 return; 37 } 38 39 int p = _partitionTwoWay(arr, l, r); 40 _quickSort(arr, l, p - 1); 41 _quickSort(arr, p + 1, r); 42 } 43 44 template <typename T> 45 void quickSort(T arr[], int n) { 46 47 srand(time(NULL)); 48 _quickSort(arr, 0, n - 1); 49 } 50 51 // 對arr[l...r]范圍的陣列進行插入排序 52 template<typename T> 53 void insertionSort(T arr[], int l, int r) { 54 55 for (int i = l + 1; i <= r; i++) { 56 57 T e = arr[i]; 58 int j; 59 for (j = i; j > l && arr[j - 1] > e; j--) 60 arr[j] = arr[j - 1]; 61 arr[j] = e; 62 } 63 64 return; 65 }
6 三路快速排序
圖源：https://segmentfault.com/a/1190000021726667
python版本：
1 def __partition_three_ways(nums, left, right): 2 # 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot 3 rand_index = random.randint(left, right) 4 nums[left], nums[rand_index] = nums[rand_index], nums[left] 5 refer = nums[left] 6 7 less_than, great_than = left, right + 1 8 i = left 9 while i < great_than: 10 if nums[i] < refer: 11 nums[i], nums[less_than + 1] = nums[less_than + 1], nums[i] 12 i += 1 13 less_than += 1 14 elif nums[i] > refer: 15 nums[i], nums[great_than - 1] = nums[great_than - 1], nums[i] 16 great_than -= 1 17 else: 18 i += 1 19 nums[left], nums[less_than] = nums[less_than], nums[left] 20 21 return less_than, great_than 22 23 24 def __quick_sort(nums, left, right): 25 if right - left <= 15: # 當資料規模很小的時候采用插入排序， 具體程序在上面 26 insertion_sort(nums, left, right) 27 return 28 29 lt, gt = __partition_three_ways(nums, left, right) 30 __quick_sort(nums, left, lt - 1) 31 __quick_sort(nums, gt, right) 32 33 34 def quick_sort(nums): 35 __quick_sort(nums, 0, len(nums) - 1)
C++版本：
1 template<typename T> 2 void __quickSort3Ways(T arr[], int l, int r) { 3 // 對于小規模陣列, 使用插入排序進行優化， 具體程序在上面實作中有 4 if (r - l <= 15) { 5 insertionSort(arr, l, r); 6 return; 7 } 8 9 // 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot 10 swap(arr[l], arr[rand() % (r - l + 1) + l]); 11 12 T refer = arr[l]; 13 14 int lt = l; // arr[l+1...lt] < refer 15 int gt = r + 1; // arr[gt...r] > refer 16 int i = l + 1; // arr[lt+1...i) == refer 17 while (i < gt) { 18 if (arr[i] < refer) { 19 swap(arr[i], arr[lt + 1]); 20 i++; 21 lt++; 22 } 23 else if (arr[i] > refer) { 24 swap(arr[i], arr[gt - 1]); 25 gt--; 26 } 27 else { // arr[i] == refer 28 i++; 29 } 30 } 31 32 swap(arr[l], arr[lt]); 33 34 __quickSort3Ways(arr, l, lt - 1); 35 __quickSort3Ways(arr, gt, r); 36 37 } 38 39 template <typename T> 40 void quickSort3Ways(T arr[], int n) { 41 42 srand(time(NULL)); 43 __quickSort3Ways(arr, 0, n - 1); 44 }
7
- 時間復雜度：O(nlogn) （平均）
- 空間復雜度：O(1)
- 不穩定排序
- 原地排序
- 分治思想
8 用快速排序的思想解決topK問題
在lintcode的上刷過這道題，當時使用堆排序的思路進行解題，故晚些時候另設一篇博客來記錄兩種思路，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/75829.html
標籤：其他
上一篇：spark 輸出到Elasticsearch 報錯，請大神指導一下！謝謝
下一篇：簡單實用演算法— 冒泡排序