quickSort
在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序法
对 arr[l,r] 进行partition（划分操作）
参考标准是首元素arr[l]=v，把整个数组分成两部分，arr[l+1,j]<v，arr[j+1,i-1]>v，arr[i]是即将要进行排序的元素
- 若arr[i]>v，则元素e要放到紫色部分，i++即可
- 若arr[i]<v，则元素e要放到橙色部分，用arr[j+1]与e进行交换，j++即代表橙色部分增加1，i++即可
- 当i>r代表所有元素都已经排序，再把arr[l]与arr[j]进行交换，此时整个数组划分为两部分，partition操作完成
template<typename T>
int __partition(T arr[],int l,int r){
//第一个元素设置为参考标准
T v=arr[l];
//从arr[l+1]开始对元素进行划分
//初始时就要保证arr[l+1,j]<v，arr[j+1,i)>v，arr[i]是即将要排序的元素，那么i=l+1
int j=l,i=l+1;
for(i;i<=r;i++ ){
if(arr[i]<v){
swap(arr[i],arr[j+1]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
template <typename T>
void __quickSort(T arr[],int l,int r) {
if(l>=r)
return;
//二分操作：将arr中的[l,r]划分为两部分，返回参考标准的坐标j
int j=__partition(arr,l,r);
//递归
__quickSort(arr,l,j-1);
__quickSort(arr,j+1,r);
}
//快速排序
template<typename T>
void quickSort(T arr[],int n) {
__quickSort(arr,0,n-1);
}
n = 1000000
quickSort : 0.727 s
优化1：穿插使用插入排序
对于所有高级排序算法，都可以这么进行优化：
快要递归到底时，可以使用插入排序，当递归到数组数量非常小的时候，可以改为使用插入排序来提高性能
template <typename T>
void __quickSort(T arr[],int l,int r) {
// if(l>=r)
// return;
if(r-l<=15){
insertionSort(arr,l,r);
return;
}
int j=__partition(arr,l,r);
__quickSort(arr,l,j-1);
__quickSort(arr,j+1,r);
}
n = 1000000
quickSort : 0.685 s
与归并排序的比较
归并排序
通过二分法达到log(n)这样一个层级，然后在通过O(n)的归并操作，就形成了nlog(n)的归并排序
快速排序
快速排序也是不断的将数组一分为二的过程，不过我们需要找到一个标准点，将标准点左边和右边进行划分。
区别
- 归并排序每次划分都是平均分配
- 快速排序的划分操作无法保证每次都是平均分配，即划分出的子数组可能是一大一小的。即不能完全保证二叉树的高度就是logn，最差情况下，快速排序会退化为O(n^2)
当数组完全有序时，二叉树高度是n，每层处理的复杂度又是n，那么时间复杂度为O(n^2)。
解决在有序数组中慢
上面的快速排序法中我们是使用数组首元素作为参考标准，修改为随机选择元素作为参考标准，此时退化为O(n^2)的概率接近为0
随机化快速排序法
template<typename T>
int __partition(T arr[],int l,int r){
//随机选择一个元素与首元素交换，此时的首元素很大概率是平均值
T random=arr[rand()%(r-l+1)+l];
swap(arr[l],random);
T v=arr[l];
int j=l,i=l+1;
for(i;i<=r;i++ ){
if(arr[i]<v){
swap(arr[i],arr[j+1]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
template <typename T>
void __quickSort(T arr[],int l,int r) {
if(r-l<=15){
insertionSort(arr,l,r);
return;
}
int j=__partition(arr,l,r);
__quickSort(arr,l,j-1);
__quickSort(arr,j+1,r);
}
template<typename T>
void quickSort(T arr[],int n) {
//当前时间戳作为随机数种子
srand(time(0));
__quickSort(arr,0,n-1);
}
缺陷
即使参考标准v选在一个平衡位置，但当数组中有大量重复的元素，等于v的元素也非常多，一样会导致数组被划分为两个极度不平衡的部分，快速排序又退化为O(n^2)级别的算法
解决在含有大量重复元素数组中慢
上述是将partition操作后的两部分都放在数组的一端，i从左到右递增，直到遍历完整个数组。现在将划分的两部分，分别放在数组两端，左右两边的指针同时向内移动，双路快速排序法
游标i和游标j同时向中间移动，直到arr[i]>=v，i停止移动；arr[j]<=v，j停止移动；当两者都停下时交换arr[i]和arr[j]，i++，j--。重复上述操作，直到i>j。此时i在第一个>=v的位置，j在最后一个<=v的位置，参考标准arr[l]是在<=v的部分，所以交换arr[l]和arr[j]，此时j就是参考标准应该处于的位置
左右部分都可以接收等于v的元素，把等于v的元素分散到左右两部分，保证在含有大量重复元素的数组能平均划分为两部分
双路快速排序法
template<typename T>
int __partition2(T arr[],int l,int r) {
swap(arr[l],arr[rand()%(r-l+1)+l]);
T v=arr[l];
//区间：arr[l+1,i)<=v，arr(j,r]>=v，要保证这两部分的区间都为空
int i=l+1,j=r;
while(true) {
while(i<=r&&arr[i]<v) i++;
while(j>=l+1&&arr[j]>v) j--;
if(i>j) break;//当i>j，划分完成，直接跳出循环
swap(arr[i],arr[j]);
i++;
j--;
}
swap(arr[l],arr[j]);
return j;
}
template <typename T>
void __quickSort2(T arr[],int l,int r) {
if(r-l<=15) {
insertionSort(arr,l,r);
return;
}
//二分操作：将arr中的[l,r]划分为两部分，返回参考标准的坐标j
int j=__partition2(arr,l,r);
__quickSort2(arr,l,j-1);
__quickSort2(arr,j+1,r);
}
//双路快速排序法
template<typename T>
void quickSort2(T arr[],int n) {
//当前时间戳作为随机数种子
srand(time(0));
__quickSort2(arr,0,n-1);
}
三路快速排序法
Quick Sort 3 Ways
之前划分都是把数组划分为两部分，而三路快速排序则把数组分为三部分（<v,=v,>v），之后递归对<v；>v两部分继续进行三路快速排序
arr[i]是将要处理的元素
- 如果arr[i]=v，那么直接纳入蓝色部分，i++
- 如果arr[i]<v，那么arr[i]和arr[lt+1]交换，lt++,i++
- 若果arr[i]>v，那么arr[i]和arr[gt-1]交换，gt--，i索引则无需维护，因为跟arr[gt-1]本来就是未处理的元素
- i一直递增直到与gt重合时，将arr[l]与最后一个小于v的arr[lt]交换，此时arr[lt]是数组中第一个等于v的元素
- 调用递归对<v；>v继续进行三路快速排序
//三路快速排序处理arr[l,r]
//将arr[l,r]分为<v；==v；>v三部分
template <typename T>
void __quickSort3(T arr[],int l,int r) {
if(r-l<=15) {
insertionSort(arr,l,r);
return;
}
//partition
swap(arr[l],arr[rand()%(r-l+1)+l]);
int v=arr[l];
//<v:[l+1,lt]
//==v:[lt+1,i)
//>v:[gt,r]
int lt=l,gt=r+1;
for(int i=l+1;i<gt;){
if(arr[i]>v){
swap(arr[i],arr[gt-1]);
gt--;//i无需维护，因为arr[gt-1]本来就是未处理的元素
}else if(arr[i]<v){
swap(arr[i],arr[lt+1]);
i++;
lt++;
}else{
i++;
}
}
swap(arr[l],arr[lt]);
__quickSort3(arr,l,lt-1);
__quickSort3(arr,gt,r);
}
//三路快速排序法
template<typename T>
void quickSort3(T arr[],int n) {
//当前时间戳作为随机数种子
srand(time(0));
__quickSort3(arr,0,n-1);
}
partition操作
参考标准是首元素arr[l]，使得arr[l+1,j]<v，arr[j+1,i)>v，i是将要插入的元素
双路快速排序