[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 ```