• 快速排序是對冒泡排序的改進。
• • 快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序，它采用一種分治(Divide-and-ConquerMethod)的方法
  • 快速排序的思想：
  • • 在數(shù)組中找到一個基準數(shù)（pivot）
    • 分區(qū)，將數(shù)組中比基準數(shù)大的放到它的右邊，比基準數(shù)小的放到它的左邊
    • 繼續(xù)對左右區(qū)間重復(fù)第二步，直到各個區(qū)間只有一個數(shù)，這時候，數(shù)組也就有序了。
  • 代碼：
  • 1 int Partition(vector<int> &v, int head, int rear){ 2 int key = v[head]; 3 while (head < rear){ 4 while (v[rear] <= key && head < rear){ 5 --rear; 6 } 7 swap(v[head], v[rear]); 8 while (v[head] >= key && head < rear){ 9 ++head; 10 } 11 swap(v[rear], v[head]); 12 13 } 14 v[head] = key; 15 ++my_count; 16 return head; 17 } 18 19 void QuickSort(vector<int> &v, int head, int rear){ 20 int pivot = -1; 21 if (head < rear){ 22 pivot = Partition(v, head, rear); 23 QuickSort(v, head, pivot - 1); 24 QuickSort(v, pivot + 1, rear); 25 } 26 }
  • Note:?Partition函數(shù)中 v[rear] <= key 以及 v[head] >= key 表達式必須包含等于的判斷，否則當數(shù)組兩頭的數(shù)相等時將會造成死循環(huán) ?例如 {5,2,6,2,9,10,5}
  • Partition函數(shù)：最慢情況下快速排序會進行 size(）- 1 次 Partition函數(shù)，而每次調(diào)用，Partition函數(shù)會選擇一個基準數(shù)，例如v[head]或者v[rear]，或者任意一個數(shù)組中的數(shù)。之后分別從兩頭掃描，碰到比基準數(shù)大或者小的數(shù)就與上一個head或rear交換，或者直到head大于等于rear時，此次循環(huán)結(jié)束。
  • QuickSort函數(shù)：該函數(shù)采用遞歸的方法，每次調(diào)用一次Partition函數(shù)，得到一個基準數(shù)的索引和相對基準數(shù)有序的數(shù)列，之后將該基準數(shù)左邊的數(shù)組和右邊的數(shù)組分別調(diào)用QuickSort函數(shù)，也就是它本身。直到數(shù)組中只有一個數(shù)時，這條遞歸序列便結(jié)束。
• 基于快速排序的查找前k個最大數(shù)
• • 由上可知，快排的思想是每次找到一個基準數(shù)，將數(shù)組排列成基準數(shù)左邊的每個數(shù)都比基準數(shù)大，右邊的每個數(shù)都比基準數(shù)小的序列。
  • 通過這個思想，我們可以稍微修改QuickSort函數(shù)，使它變成QuickSearch函數(shù)，使之擁有快速查找前k個最大的數(shù)。
  • 1 int QuickSearch(vector<int> &v, int head, int rear, int k){ 2 int pivot = -1, len = 0; 3 if (head < rear){ 4 pivot = Partition(v, head, rear); 5 len = pivot - head + 1; 6 if (len < k){ 7 pivot = QuickSearch(v, pivot + 1, rear, k - len); 8 } 9 else if (len > k){ 10 pivot = QuickSearch(v, head, pivot - 1, k); 11 } 12 } 13 return pivot; 14 }
  • 上圖中，我們可以發(fā)現(xiàn)，函數(shù)參數(shù)多了一個k，這個值是表示要獲取前k個最大數(shù)。
  • 函數(shù)中多了一些邏輯，每次執(zhí)行完P(guān)artition函數(shù)，根據(jù)獲取的基準值索引，計算基準值左邊數(shù)組的長度。
  • 若len < k，則說明，在基準值左邊的數(shù)組中已經(jīng)有了len個最大數(shù)，此時，我們只需在基準值右邊的數(shù)組再找k - len個最大數(shù)即可，所以只要再次調(diào)用QuickSearch函數(shù)，并傳入k-len參數(shù)以及基準值右邊的數(shù)組索引。
  • 若len > k，則說明，此時基準值左邊已經(jīng)有了len個最大值，然而len大于k，我們并不需要那么多的最大值，所以再次調(diào)用QuickSearch函數(shù)，傳入基準值左邊的數(shù)組索引，以及k，獲得這個長度len的最大數(shù)集的子集

轉(zhuǎn)載于:https://www.cnblogs.com/macher/p/5317439.html

總結(jié)

以上是生活随笔為你收集整理的快速排序以及基于快排思想的找前k个最大数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。