【决战西二旗】|快速排序的优化
1.前言
2.2 快速排序分治示意图
注:快排的过程就不写具体的数字了 仅为达意 点到即可。
可以明显看出来，快速排序在选择基准值时对整个分治过程影响很大，因为下一个环节的分治是基于前一环节的分割结果进行的。
2.3 快速排序划分不均匀情况
考虑一种极端的情况下，如果基准值选取的不合理，比如是最大的或者最小的，那么将导致只有一边有数据，对于已经排序或者近乎有序的数据集合来说就可能出现这种极端情况，还是来画个图看下：
图中展示了每次分治都选择第一个元素作为基准值，但是每次的基准值都是最小值，导致每次基准值左侧没有子序列，除了基准值之外全部元素都在右子序列。
2.4 概率和复杂度计算
每次分割排序之后，只能在有序序列中增加1个元素递归树变成了单支树并且递归深度变大，极端情况的出现概率和最坏复杂度计算如下：
极端情况概率就是每次在剩余所有元素中挑出最小的，这样每次的概率都是1/(n-i)，所以组合起来就是1/(n!)，所以随机数据集合出现最差情况的概率非常低，但是有序数据下固定基准值选择就可能造成极端情况的出现。
最坏复杂度相当于每次从n-i个元素中只找到1个数据，将所有情况累加也就达到了O(n^2)级别，并不是递归过程全都挑选了最值作为基准值才会出现O(n^2)的复杂度，复杂度是一个概率化的期望值，具体的系数不同影响也很大。
3. 快速排序基准值选取优化
3.1 分割越均匀速度越快
从上面的几张图可以清晰看到基准值的不同对于D&C过程的分割会产生很大的影响，为了保证快速排序的在通用数据集的效率，因此我们需要在基准值的选取上做一些决策，换句话说就是让选取的基准值每次都可以尽可能均匀地分割数据集，这样的效率是最高的。
3.2 随机选取基准值
网上有很多选择方法比如固定选取第一个、固定选取最后一个、固定选择中间值、三值平均选取等，不过个人觉得每一次都随机选取某个位置的数据作为基准值，然后与第一个值互换，这样就相当于每次的基准值都是随机选择的，就将固定index带来的问题，大大降低了。
3.3 随机vs固定对比试验
接下来做一组对比试验，生成一个0-100000的有序数组，代码增加了很多选择项和时间测量代码，测试代码如下：
#include<iostream> #include<sys/time.h> #include<stdlib.h>#define SIZE 100000using namespace std; //获取从[start-end)之间的随机indexint getrandom(int start,int end){ srand((unsigned int)time(NULL)); return (rand()%(end-start))+start; } //获得毫秒时间戳long getCurrentTime() { struct timeval tv; gettimeofday(&tv,NULL); return tv.tv_sec*1000 + tv.tv_usec/1000; } template <typename T>void quick_sort_recursive(T arr[], int start, int end, string& method) { if (start >= end) return; //产生随机索引 并与end交换 之后与原来的处理一致 if(method=="random"){ int randindex = getrandom(0,end-start); std::swap(arr[end],arr[randindex]); } T mid = arr[end]; int left = start, right = end - 1; //在整个范围内搜寻比枢纽元值小或大的元素，然后将左侧元素与右侧元素交换 while (left < right) { //试图在左侧找到一个比枢纽元更大的元素 while (arr[left] < mid && left < right) left++; //试图在右侧找到一个比枢纽元更小的元素 while (arr[right] >= mid && left < right) right--; //交换元素 std::swap(arr[left], arr[right]); } if (arr[left] >= arr[end]) std::swap(arr[left], arr[end]); else left++; quick_sort_recursive(arr, start, left-1, method); quick_sort_recursive(arr, left+1, end, method); } //模板化template <typename T>