如何将快速排序、归并排序、小和问题、逆序对问题、荷兰国旗问题改写为长尾关键词？

本文共计2456个文字，预计阅读时间需要10分钟。

递归行为时间复杂度计算：master公式 + T(N)=a * T(N/b) + O(Nd) + N：子问题模型 + a：子问题计算次数 + N/b：子问题规模 + O(Nd)：每次递归除子问题外的其他操作时间复杂度 + log(b, a) * d：T(N)=O(Nlogb(a) * d)

递归行为时间复杂度计算：master公式

T(N) = a * T(N/b) + O(N^d)

N：母问题规模

a：子问题计算次数

N/b：子问题规模

O(N^d)：每次递归除子问题外其他操作时间复杂度

1）log(b,a) > d : T(N) = O(N^log(b,a))

2）log(b,a) < d : T(N) = O(N^d)

3）log(b,a) == d : T(N) = O(N^d * logN)

使用master公式的前提：子问题等规模

如使用递归求数组最大值：

// 将数组分为左右两个子数组，分别求两个子数组最大值，返回两个最大值中更大者 int process(vector<int>& nums, int l,int r){ if(l == r){ // 递归结束条件 return nums[l]; } int m = l + ((r - l) >> 1); // 括号保证 >> 运算先于 + int leftMax = process (nums, l, m); int rightMax = process (nums, m+1, r); //是 m+1 不是 m return max(leftMax, rightMax); } int getMax(vector<int>& nums){ return process(nums, 0, nums.size() - 1); } /* 此递归中 a = 2 ,b = 2, d = 0 log(b,a) > d : T(N) = O(N ^ log(b,a)) = O(N) 此递归算法的时间复杂度与遍历数组找最大值算法相同 如果递归算法改为： 计算数组前2/3部分和后2/3部分最大值，返回两个最大值中更大者 由于子问题都是 2*N/3 规模，依然可以使用master公式 */

归并排序

1）整体就是一个简单递归，左边排好序，右边排好序，让其整体有序

2）让其整体有序的过程采用了外排序的方法（排到外部数组里再拷贝回来）

时间复杂度O(N*logN) 空间复杂度O(N)

void merge(vector<int>& nums, int l, int m, int r){ // 存放两半数组merge后结果，最后拷贝到nums数组 vector<int> help(r - l + 1, 0); // 三个指针，分别指向help数组，左右两半数组 int i = 0; int p1 = l; int p2 = m +1; // 两半数组中最小的放入help while(p1 <= m && p2 <= r){ help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++]; } // 两半数组中一个已遍历完，另一个数组中还未遍历的依次拷贝到help while(p1 <= m){ help[i++] = nums[p1++]; } while(p2 <= r){ help[i++] = nums[p2++]; } // 将排好序的help数组拷贝到nums相应位置 for(i = 0; i < help.size(); i++){ nums[l + i] = help[i]; } } void process(vector<int>& nums, int l,int r){ if(l == r){ // 递归结束条件 return; } int m = l + ((r - l) >> 1); // 先把左右两半部分排好序 process(nums, l, m); process(nums, m+1, r); // 是 m + 1 不是 m // 左右两半部分都已排好序，最后merge在一起 merge(nums, l, m, r); } int mergeSort(vector<int>& nums){ process(nums, 0, nums.size() - 1); } /* 计算mergeSort时间复杂度：master公式 a = 2 ,b = 2, d = 1 log(b,a) == d : T(N) = O((N ^ d) * logN) = O(N*logN) */

为什么选择、冒泡、插入排序时间复杂度为O(N^2)，归并排序为O(N*logN):

因为它们浪费了许多比较行为，以选择排序为例：

第一次在0~N-1范围比较，只搞定了一个数

第二次在1~N-1范围比较，只搞定了一个数

第三次在2~N-1范围比较，只搞定了一个数。。。

每次比较都是独立的，第一次比较的结果不会用到第二次比较中去

而归并排序没有浪费比较行为：

归并排序每次比较的信息留下来了，每次比较得到一个有序的部分

这个有序的部分会在下次比较里与另一个有序部分merge出一个更大有序部分

每次比较后的信息是一层层往下传递的

小和问题

在一个数组中，每一个数的左边比当前数小的所有数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：[1,3,4,2,5]

1左边比1小的数，没有

3左边比3小的数，1

4左边比4小的数，1,3

2左边比2小的数，1

5左边比5小的数，1,3,4,2

所以小和为1+1+3+1+1+3+4+2=16

使用归并排序，边排序边求小和。

与归并排序唯一的不同是：

只有在左边与右边相等时把右边的数移到help数组

即只有左边数比右边小时才把左边数记到help数组，同时计算小和(因为此时左边数比所有右边数都小)

int merge(vector<int>& nums, int l, int m, int r){ vector<int> help(r - l + 1, 0); int i = 0; int p1 = l; int p2 = m + 1; int res = 0; while(p1 <= m && p2 <= r){ /* 找左边数小于右边数，找到则左边数小于右边数及右边数以右所有数 左右边数相等时让右边数右移增大，因为我们找的是左边数小于右边数 也只有这样，右边数以右的所有数大于左边数的事实才能被检测到 */ res += nums[p1] < nums[p2] ? nums[p1] * (r - p2 + 1) : 0; help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++]; } while(p1 <= m){ help[i++] = nums[p1++]; } while(p2 <= r){ help[i++] = nums[p2++]; } for(i = 0; i < help.size(); i++){ nums[l + i] = help[i]; } return res; } int process(vector<int>& nums, int l,int r){ if(l == r){ return 0; } int m = l + ((r - l) >> 1); return process(nums, l, m) + process(nums, m+1, r) + merge(nums, l, m, r); } int smallSum(vector<int>& nums){ if(nums.empty() || nums.size() < 2){ return 0; } return process(nums, 0, nums.size() - 1); }

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有的逆序对。

边排序边检测：

小和问题是左边的数比右边所有数小，则。。。

逆序对问题是左边的数比右边的数大，则。。。

int merge(vector<int>& nums, int l, int m, int r){ vector<int> help(r - l + 1, 0); int i = 0; int p1 = l; int p2 = m + 1; int res = 0; while(p1 <= m && p2 <= r){ /* 左边数比右边数大，则左边数及左边数以右所有数都大于右边数 因为要找左边数大于右边数，所以左右边数相等时左边数右移增大 只有这样，左边数以右所有数大于右边数这一事实才能被检测到 */ res += nums[p1] > nums[p2] ? (m - p1 + 1) : 0; help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++]; } while(p1 <= m){ help[i++] = nums[p1++]; } while(p2 <= r){ help[i++] = nums[p2++]; } for(i = 0; i < help.size(); i++){ nums[l + i] = help[i]; } return res; } int process(vector<int>& nums, int l,int r){ if(l == r){ return 0; } int m = l + ((r - l) >> 1); return process(nums, l, m) + process(nums, m+1, r) + merge(nums, l, m, r); } int inversePair(vector<int>& nums){ if(nums.empty() || nums.size() < 2){ return 0; } return process(nums, 0, nums.size() - 1); }

荷兰国旗问题

给定一个数组arr和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于数组的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

维护一个 < 区域右边界指针和 > 区域左边界指针

初始边界分别在数组首元素左边和最后一个元素右边

从左到右遍历arr[i]：

1）arr[i] < num : arr[i]和 < 区域下一个元素交换，<区域右扩，i++

2）arr[i] == num ：i++

3）arr[i] > num ：arr[i]和 > 区域前一个元素交换，i原地不动

当i和有边界重合，算法结束

void swap(vector<int>& nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } void flag(vector<int>& nums, int value){ int less = -1; int more = nums.size(); int i = 0; while(i < more){ if(nums[i] < value){ swap(nums, i++, ++less); } else if(nums[i] == value){ i++; } else{ swap(nums, i, --more); } } }

快速排序

随机选一个数放在数组最后作划分，把前面的数组划分为小于等于大于划分值的三部分，再对大于和小于部分作上述操作，递归

时间复杂度O(N*logN)

注:最坏状况复杂度O(N²),但这种情况并不常见

划分数有N种可能，对应数组中N个元素

N种情况等概率，都为1/N

N种情况下时间复杂度不同

对这N种情况下时间复杂度取数学期望:O(N*logN)

快速排序通常比其他O(N*logN)算法更有效率

void swap(vector<int>& nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } pair<int, int> partition(vector<int>& nums, int l, int r){ // less:小于区域最右一个元素 more:大于区域最左一个元素 int less = l - 1; int more = r; int i = l; while(i < more){ if(nums[i] < nums[r]){ swap(nums, i++, ++less); } else if(nums[i] == nums[r]){ i++; } else{ swap(nums, i, --more); } } swap(nums, more, r); return pair<int, int>{less + 1, more}; } void quickSort(vector<int>& nums, int l, int r){ if(l < r){ swap(nums, r, l + (rand() % (r - l + 1))); // #include <utility> pair<int, int> p = partition(nums, l, r); quickSort(nums, l, p.first - 1); quickSort(nums, p.second + 1, r); } }