1. 簡介
神說, 要有光. 于是就有了光. 神說要有快排, 于是就有了快排.?
快速排序Quick Sort的發明者 托尼 霍爾 是1980年的圖靈獎得主. 快速排序就是他發明的. 當時發明的背景是: 由于霍爾要高效地對俄語詞匯進行排序以優化翻譯程序, 而當時的排序算法(如冒泡, 插入排序)效率較低, 平均時間復雜度為 O(n2). 霍爾受分治法 (Divide and Conquer)思想啟發, 提出了基于 "分區" (Partition) 的遞歸排序方法. (這段AI獲取)
2. 核心思想
分區 (Partition): 指的是選一個基準值 Pivot, 將比基準值小的放在它的左側, 比它大的放在右側. 然后, 分別在左邊區域 (比基準值小的區域) 和右邊區域 (比基準值大的區域) 做相同的操作即再在左右兩邊選基準值, 再劃分為兩個區域, 一直到劃分的區域即子序列長度為1, 即只有一個元素為止.這個就是快速排序的核心思想.
3.算法實現方式
分區法據我了解到有三種:? ?(因為很早前寫的,細節解釋可能有誤, 注意甄別)
3.1 第一種是 Naive Partition (樸素分區法)
這種方法我用 C++ 實現過, 不過我是看到某個Python的實現, 我根據它的實現, 用 C++ 翻譯而已. 就是我們選一個基準值, 然后遍歷元素, 比它小的我們額外存放到一個臨時空間中, 比它大的也一樣. 然后再將臨時空間中的比基準值小的搬回原來的存儲空間中, 再放基準值, 然后把比基準值大的放到基準值的右邊. 再分別遞歸處理基準值左邊和右邊的區域. 如果某一輪沒有找到比基準值小或大的值, 則左邊或右邊不再遞歸處理.
3.2 第二種是 Lomuto Partition (洛穆托分區法)?
它維護兩個指針 (下標), i 和 j . 依次從最左邊的元素遍歷到最末元素的前一個 (倒數第二個) , 并且選擇最末元素為基準值. i 初始值指向 -1, j 指向第一個元素, 如果當前 j 指向的元素比基準值小, 則增加 i 的值, 并交換 i 和 j 指向的元素, 也就是將比基準值小的元素往后擺放. 如果 j 指向的元素比基準值大, 則不動它.? i 增加只在發生交換時增加, j 是每次無論交換與否都要增加.最終 i + 1 的位置就是返回的基準值的位置, 再遞歸處理 i + 1左邊和右邊.
3.3 第三種是 Hoare Partition (霍爾分區法)
這也是快排原始版本, 由霍爾本人發明, 好像也是最快的實現方式. 它也維護兩個下標 low?和 high, 只是從元素序列的兩邊分別遍歷, 一個往后, 一個往前. 并且一般選第一個元素為基準值. 往后移的下標 low 找到比基準值大于等于的值, 往前移的 high 下標找比基準值小于等于的值, 找到則停止, 此時如果 low 和 high 還沒相遇, 則交換它倆. 即將大的往后放, 小的往前放. 若相遇則返回 high下標. 這個 high 下標的位置就是基準值的位置. 然后遞歸處理基準值左邊和右邊.
(如果文字抽象或這里沒寫正確, 可以看實現代碼在紙上推演, 推兩輪自然明白, 我這里就不畫圖了, 畫圖有點耗時間)
4. 代碼實現
4.1 第一種樸素分區法
注釋也比較詳細, 思想就是剛剛介紹的, std::array 模版類是 C++ 中的一種數組/容器, std::vector可能更適合長度經常變化的數組, std::array 數組長度固定, 效率比 std::vector 高, 而 std::array 又封裝了一些額外的功能 (什么邊界檢查,還有一些方法) 比原始數組好用. ( C++的幾種數組效率可以用百萬級的元素或千萬級的元素來測試) . 這個版本雖不能完全算原創, 但也是半原創, 就是根據某個Python實現, 用 C++ 獨立完成.
/*快速排序 樸素分區法 ?? C++版 08042024 by losangelx*/
#include <iostream>
#include <array>
const int SIZE = 10;/*快速排序函數,start為排序起始下標,len為要排序的范圍*/
bool quickSort(std::array<int, SIZE>& ar, int start, int len);int main(void)
{std::array<int, SIZE> numbers = { 0, 422, 12, 4, 111, 3, 5, 22, 200, 123 };std::array<int, SIZE>::iterator ir; /*array模版類迭代器*/std::cout << "The oringal array: "; /*原始數組*/for (ir = numbers.begin(); ir != numbers.end(); ir++)std::cout << *ir << " ";quickSort(numbers, 0, numbers.size());std::cout << "\nAfter quick sorted: "; /*排序后數組*/for (int x : numbers)std::cout << x << " ";return 0;
}/*快速排序函數,start為排序起始下標,len為要排序的范圍*/
bool quickSort(std::array<int, SIZE>& ar, int start, int len)
{if (len == 1) //基線條件:如果長度為1不再遞歸排序return 1;std::array<int, SIZE> small; /*臨時元素存放區*/std::array<int, SIZE> larger;/*small為比基準因子小的元素*/int i, j, k; /*larger為比基準因子大的元素*//*將原數組中比基準因子小和大的先搬出來*/for (i = start + 1, j = 0, k = 0; i - start < len; i++)if (ar[i] <= ar[start])small[j++] = ar[i];elselarger[k++] = ar[i];/*基準因子arr[start]最終排在由比它小的元素組成的子*//*數組之后并且在比它大的元素組成的子數組之前的位置上*/ar[start + j] = ar[start];/*如果有比基準因子小的元素則搬回原數組,并對子*//*數組(由比基準因子小的組成)執行相同操作(遞歸)*/if (j > 0) {int m = 0;for (i = start; i - start < j; i++)ar[i] = small[m++];quickSort(ar, start, j);//只對長度為j的部分排序} //即只對原數組比基準因子//小的那部分執行相同操作/*若有比基準因子大的元素則執行相同操作*/if (k > 0) {int n = 0;for (i = start + j + 1; (i - (start + j + 1)) < k; i++)ar[i] = larger[n++];quickSort(ar, start+j+1, k);}return 1; /*排序完成返回*/
}我用 Dev C++ 編譯這個代碼遇到下面錯誤, 這里是要在dev c++中添加?C++ 11 支持才行, std::array是 C++ 11 才引入的. 如果你用 VS 應該不用.
#ifndef _CXX0X_WARNING_H
#define _CXX0X_WARNING_H 1
#if __cplusplus < 201103L
#error This file requires compiler and library support for the \
ISO C++ 2011 standard. This support is currently experimental, and must be \
enabled with the -std=c++11 or -std=gnu++11 compiler options.
#endif
#endif
4.1.1 運行結果:
4.2 第二種和第三種 Lomuto 分區法和 Hoare 分區法
/* Quick Sort 快速排序 本程序使用Lomuto/Hoare兩種分區法實現 */
#include <stdio.h>
#define MAX 10void quicksort(long arr[], int low, int high); /* 快速排序主函數 */
int hoare_parti(long arr[], int low, int high); /* 霍爾分區法 */
int lomuto_parti(long arr[], int low, int high); /* 洛穆托分區法 */
void swap(long *pl, long *ph);
void printarr(long arr[], int len);
int main(void)
{long array[MAX] = {50, 80, 10, 70, 100,30, 90, 40, 60, 20};printarr(array, MAX);printf("\n");quicksort(array, 0, MAX - 1);printarr(array, MAX);printf("\n");return 0;
}void quicksort(long arr[], int low, int high)
{if (low < high) { /* 遞歸基線條件: low與high還沒相遇才繼續 */int pindex = lomuto_parti(arr, low, high); /* 這里可選Hoare分區法或洛穆托分區法 */quicksort(arr, low, pindex - 1); /* 遞歸處理左右兩邊的序列 */quicksort(arr, pindex + 1, high);}
}/* Hoare分區法 */
int hoare_parti(long arr[], int low, int high)
{long pivot = arr[low]; /* 選第一個為基準值 */while (1) {while (arr[low] < pivot) { low++; } /* 直到找到比基準值大的停下 */while (arr[high] > pivot) { high--; } /* 直到找到比基準值小的停下 */if (low >= high) { return high; } /* low和high沒相遇繼續否則返回基準值位置 */swap(&arr[low], &arr[high]); /* 交換比基準值大的到后面反之放前面 */}
}/* Lomuto分區法 */
int lomuto_parti(long arr[], int low, int high)
{int i, j;long pivot = arr[high]; /* 選最后一個元素為基準值 */i = low - 1;for (j = low; j < high; j++) { /* i開始指向比基準值小的后一個 */if (arr[j] <= pivot) { /* j從第一個開始, 若小于等于基準值 */i++;swap(&arr[i], &arr[j]); /* 則交換即將小的往前放,大的往后放 */}}swap(&arr[i + 1], &arr[high]); /* 將基準值放到適當位置 */return (i + 1); /* 返回基準值位置 */
}void printarr(long arr[], int len)
{int i;for (i = 0; i < len; i++) {printf("%ld ", arr[i]);}
}void swap(long *pl, long *ph)
{long temp = *pl;*pl = *ph;*ph = temp;
}
上面兩種分區法都測試通過了. 不過如果Dev C++編譯選項還有 C++ 11的話, 會有警告, 應該關閉.因為這是 C. (C 和 C++ 有時候一樣, 但有些特性還是不太一樣, C++ 復雜一些,據大老C++之父本賈尼的說法是 C 的語法檢查太松散. 所以C++檢查也更嚴格)
4.2.1 運行結果:
注意: 以上的三種實現方式代碼如果有錯誤注意甄別, 我并未仔細測試, 通過即停.
5. 結語
快速排序Quick Sort 還有多種優化方式, 感興趣的讀者可以研究一下. 例如基準值的選擇就有多種不同的算法, 比如選第一個和中間, 還有最后一個元素三個取其一等等. 優化空間很大. 如果這篇文章缺少圖示, 就自己在紙上根據代碼推演, 推兩盤就立刻明白是如何實現排序的了.
關于快速排序詳細的時間復雜度分析請搜相關文章了解，不同分區方式它的時間復雜度有些區別，當然樸素分區因為要遞歸創建臨時數組并且要搬運，所以是最慢的。而洛穆托和霍爾分區法因為是在原始數組上處理不用創建臨時空間和搬運要快點，霍爾分區法因為是從兩頭往中間同時雙向遍歷所以最快，比洛穆托的要快。
這里我也人云亦云的給岀快排平均時間復雜度函數是 n * log n，其中 n 是元素個數。這個函數是對數，隨著處理元素數量的增加，函數值增量趨勢沒有n * n 大，也就是說比什么冒泡，插入排序的n * n 要快，花費的時間更少，就是說快排的n*log n讓計算機干的活兒的量比n * n的算法要少。至于如何得岀n * log n是前面也說了去搜相關文章，網上很多，都是分析要干多少活兒得岀的數學函數。
我實在無法理解為什么要把time complexity直譯成時間復雜度這個抽象詞匯，這個直接翻譯為性能不行嗎，反正只是衡量算法性能的一個數學函數。也許計算機科學家和數學家翻譯有講究吧。
喜歡就點贊收藏, 點贊收藏是我創作的動力.
)
