[TOC] ## 快速排序 快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。 1.分治法的基本思想 ??? 　分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。 2.快速排序的基本思想 ??? 　設當前待排序的無序區為R\[low..high\]，利用分治法可將快速排序的基本思想描述為：. * **①分解：**? ????在R\[low..high\]中任選一個記錄作為基準(Pivot)，以此基準將當前無序區劃分為左、右兩個較小的子區間R\[low..pivotpos-1)和R\[pivotpos+1..high\]，并使左邊子區間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續的排序。 >注意： ??? 　劃分的關鍵是要求出基準記錄所在的位置pivotpos。劃分的結果可以簡單地表示為(注意pivot=R\[pivotpos\])： ??? 　R\[low..pivotpos-1\].keys≤R\[pivotpos\].key≤R\[pivotpos+1..high\].keys ????????????????? 其中low≤pivotpos≤high。 * **②求解：**? ???　?通過遞歸調用快速排序對左、右子區間R\[low..pivotpos-1\]和R\[pivotpos+1..high\]快速排序。 * **③組合：**? ????因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，"組合"步驟無須做什么，可看作是空操作。 lua代碼實現快速排序 ```lua function quickSort(a, left, right) if left < right then local i = left local j = right local base = a[i] if i > j then return end while i ~= j do while (i < j) and (a[j] > base) do j = j - 1 -- 從右向左找第一個小于base的數 end if i < j then a[i] = a[j] -- 把第一個小于base的數放到索引i上 i = i+1 end while (i<j) and (a[i] < base) do i = i + 1 -- 從左向右找第一個大于base的數 end if i < j then a[j] = a[i] --把第一個大于base的數放到索引j上 j = j-1 end end a[i] = base quickSort(a, left, i-1) quickSort(a, i+1, right) end end function MastSort(array) print("排序前：") for index = 1, #array do print(array[index]) end quickSort(array, 1, #array) print("排序后：") for index = 1, #array do print(array[index]) end end local b= {1000,3,7,1} MastSort(b) ``` 輸出 ``` 排序前： 1000 3 7 1 排序后： 1 3 7 100 ``` C++版本的快速排序 ```cpp int quickSort(int*a, int l, int r) { int i = l; int j = r; int base = a[i]; if (l >= r) return; while (i != j) { while ( (i < j) && (a[j] > base)) j--; if (i < j) a[i++] = a[j]; while ((i < j) && a[i] < base) i++; if (i<j) a[j--] = a[i]; } a[i] = base; quickSort(a, l, i-1); quickSort(a, i+1, r); } int main() { int a[] = {1,333,44,22,55,33}; quickSort(a, 0, 6); for(int i=0;i<6;i++) printf("%4d\n",a[i]); return 1; } ``` 編譯 & 運行 ``` $ gcc -o quicksort quicksort.c $ ./quicksort 1 22 33 44 55 333 ``` ## 算法-股票交易收益 最大化 在股市的交易日中，假設最多可進行一次買賣(即買和賣的次數均小于等于1)，規則是必須一筆成交后進行另一筆(即買-賣-買-賣的順序進行)。給出一天中的股票變化序列，計算一天可以獲得的最大收益。 分析問題： 1. 收益=賣出-買入 2. 最大化收益 3. 先買入才能賣 思路 ``` /** * 計算最多兩次買賣最大收益 * * @param lPrices: 樣本數組； * * 如果樣本個數小于2，不夠一次買賣操作，直接返回； * 步驟一：尋找第一次買賣節點，計算本次交易最大收益； * 步驟二：提取剩余樣本數據，計算第二次交易最大收益； * 步驟三：將兩次交易之和與緩存最大交易收益值比較，緩存最大值。 * * */ ``` lua實現 ``` function FindPost(lPrices) local maxProfit = 0 local minPrices = lPrices[1] local maxPrices = 0 for i = 1, #lPrices do maxProfit = math.max(maxProfit, lPrices[i] - minPrices); minPrices = math.min(minPrices, lPrices[i]); end return maxProfit end local b= {1000,3,7,1} print("FindPost: " .. FindPost(b)) ``` 輸出 ``` FindPost: 4 ```