快速排序分为经典快速排序和随机快速排序，因为经典快速排序在工程上使用比较少，因此本文只将随机快速排序，它可以看作是经典快速排序的升级版本。
快速排序：
概述：
(1) 先生成一个随机数，作为下标，此下标对应的元素作为划分值。
(2) 将划分值与元素末尾的数值进行交换，让划分值处于末尾。
(3) 然后用Partition算法，将小于划分值的数放在左边，等于划分值的数放在中间，大于划分值的数放在右边，分为三部分。
Partiton算法三标准如下：
i) 当前数(index)<划分值，小于区下一个数和当前数交换，小于区向右扩一个位置
ii) 当前数＝划分值，index++
iii) 当前数>划分值，当前数和大于区前一个数交换(交换是为了把当前数给大于区)，大于区向左扩一个位置，index原地不动。
原地不动是因为大于区前那个数交换到了当前数的位置，这个数还没有进行判断，所以不动，等待下一次判断。
注意：此函数返回一个两个长度的数组，保存等于区的起始两个index！！！这样就能够很好的处理接下来要进行的递归所需要的参数。
算法稳定性：
不稳定算法。
时间复杂度：
NlogN
代码如下：
#include <iostream>
#include <random>
using namespace std;
class QuickSort_
{
public:
void QuickSort(int array[], int length);
void QuickSort(int array[], int L, int R);
void swap(int array[], int a, int b);
int *Partiton(int array[], int L, int R);
int result[2];
};
void QuickSort_::swap(int array[], int a, int b)
{
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
void QuickSort_::QuickSort(int array[],int length)
{
//如果数组长度为空或者只有一个元素，那么直接进行返回
if (length < 2)
return;
QuickSort(array, 0, length-1);
}
void QuickSort_::QuickSort(int array[], int L, int R)
{
if (L < R)
{
//把划分值放到数组末尾去
//产生一个0到R-L的随机数
uniform_int_distribution<unsigned> u(0, R-L); //产生无符号，0到R-L的随机数
default_random_engine e; //随机数引擎
int index = L+u(e); //将L偏移随机数index处位置的地方和末尾R交换
swap(array, index, R);
int *p = Partiton(array, L, R);
QuickSort(array, L, p[0]-1);
QuickSort(array, p[1]+1, R);
}
}
int* QuickSort_::Partiton(int array[], int L, int R)
{
int less = L-1;
int more = R;
while (L < more)
{
if (array[L] < array[R])
{
swap(array, ++less, L++); //小于区向右扩一个位置就是++less
//同时小于区下一个数就是++less后的对应值，和当前值L交换,L++继续下一次比较
}
else if (array[L] > array[R])
{
swap(array, --more, L); // 同理，大于区向左就是--more
//同时，大于区前一个数就是--more之后对应值和当前数进行交换，L不变，等待下一次判断
}
else
{
L++; //若在等于划分值，就直接进行下一个数的判断。
}
}
swap(array, more, R);
result[0] = less + 1;
result[1] = more;
return result;
}
int main()
{
int array[10] = {0,21,-1,3,3,2,8,6,-9,-5};
QuickSort_ quick;
quick.QuickSort(array, 10);
for (int i = 0; i < 10; i++)
{
cout << array[i] << " ";
}
return 0;
}