1，简单快速排序，
void Math_Qucik_Sort(T array[], int len) { srand(time(NULL)); Quick_Sort(array, 0, len - 1); } template <typename T> void Quick_Sort(T array[], int l, int r) { if (l - r <= 15) { Math_Insert_Sort(array, l, r); return; } int p = partition2(array, l, r); Quick_Sort(array, l, p - 1); Quick_Sort(array, p+1, r); } int partition(T array[], int l, int r) { T v=array[l]; int j = l; //array[l+1,j]<v array[j+1,i)>v，i即为需要判断的地方 for (int i = l + 1; i <= r; i++) {//都为空 if (array[i] < v) { swap(array[j+1], array[i]); j++; } } swap(array[j], array[l]); return j; }算法说明
快速排序:几个重要数据,对应到partition中的变量 v:标志位，取第一个 [l+1,j]<=v 条件1 [j+1,i)>v 条件2 i从[l+1,r]，是当前需要判断的值 如果，array[i]>v,不需要移动，i++ 如果相反情况，将array[i]与array[j+1]交换 i++,array[j+1]是大于v的，条件2满足 j++,array[i]<=v,条件1满足 这样到最后，保证，[l+1,j]<=v,[j+1,r]>v v是属于前者的，将v和array[j]替换，返回j(j左右满足条件，左边<=，右边>) 递归成立2，问题1，假设数组时基本有序，那么j一侧的数量会远大于另一侧。
如果就是有序的，那么相当于O(n^2)次运算。
优化1
srand(time(NULL)); swap(array[l], array[rand() % (r - l + 1) + l]); T v = array[l]; //标志位取随机的位置3，问题2，假设数组差距较小，比如全部属于[0-10]，那么有大量相等，也会导致一侧远大于另一侧。
优化
int partition2(T array[], int l, int r) { swap(array[l], array[rand() % (r - l + 1) + l]); T v = array[l]; ;//arr[l+1,i) <=v arr(j,r]>=v; int i = l + 1, j = r; while (true) { while (i<=r && array[i] < v) i++; while (j >= l + 1 && array[j] > v) j--; if (i >j) { break; } /* 如过出现i=j取相等，那么相等时，这个值等于v 如果>，取j,这是j为最后一个小于v的值 */ swap(array[i], array[j]); i++; j--; } swap(array[l], array[j]);//l 这个位置小于array[l]的 return j; }说明
从两侧开始遍历， [l+1,i)<v (j,r]>v 保持这样的条件进行遍历， 左侧碰到相等，会放到右侧 右侧碰到相等，放到左侧 将相等的值，分到两侧4，还可以分三段排序
template<typename T> void Math_Qucik_Sort_3Ways(T array[], int l, int r) { /*小于等于大于*/ if (l >= r) { return; } swap(array[l], array[rand() % (r - l + 1) + l]); T v = array[l]; // l < lt = gt i > r int lt = l; //[l+1,lt]<v int gt = r + 1;//[gt .. r]>v int i = l + 1; //[lt+1,i)==v while (i < gt) { if (array[i] < v) { swap(array[i], array[lt + 1]); lt++; i++; }//放到第一个区间最后一部分 else if (array[i] > v) { swap(array[i], array[gt - 1]); gt--; } else { i++; } } swap(array[l], array[lt]); Math_Qucik_Sort_3Ways(array,l, lt-1); Math_Qucik_Sort_3Ways(array,gt, r); }分大于等于小于三部分。
总结，O(nlogn)这种算法，但是分为logn层，每层n的时间复杂的。对于快排来说，每次不是均分，可能会导致实际会大于logn层。
