目录
1.快速排序
1.1 版本1：
1.2 版本2：
1.3 版本3：
1.4 版本4：
1.5 版本5：
2 归并排序和快速排序的衍生问题
2.1逆序对问题
2.2 取数组中第n大的元素
1.快速排序
1.1 版本1：
中间过程：
最终：
此时，只需将l和j位置的元素交换：
//对arr[left...right}部分进行partition操作
//返回p，使得arr[left...p-1]<arr[p],arr[p+1...r]>arr[p]
int __partition(int arr[],int left,int right)
{
int v=arr[left];
int j=left; //i和j的初值参考图片
for(int i=left+1;i<=right;i++)
{
if(arr[i]<v)
{
swap(arr[i],arr[j+1]);
j++;
}
}
swap(arr[left],arr[j]);
return j;
}
//对arr[left...right}部分进行快速排序
void __quickSort(int arr[],int left,int right)
{
if(left>=right)
return;
int p=__partition(arr,left,right);
__quickSort(arr,left,p-1);
__quickSort(arr,p+1,right);
return;
}
void quickSort(int arr[],int n)
{
__quickSort(arr,0,n-1);
return;
}1.2 版本2：
和归并排序的改进一样，可以当数据规模比较小的时候采用插入排序来改进性能
只需修改__quickSort函数，其他相同：
//对arr[left...right}部分进行快速排序
void __quickSort(int arr[],int left,int right)
{
if(right-left<=15)
{
insertionSort(arr,left,right);
return;
}
int p=__partition(arr,left,right);
__quickSort(arr,left,p-1);
__quickSort(arr,p+1,right);
return;
}1.3 版本3：
快速排序生成的递归树的平衡度比归并排序要差，并且不能保证树的高度是logn
快速排序最差的情况，也就是数组近乎有序的时候，退化为O(n^2)
因为现在我们固定的选择最左侧的元素做为标定元素，所以出现了这种情况。
改进：随机选择一个元素做为标定元素：
//对arr[left...right}部分进行partition操作
//返回p，使得arr[left...p-1]<arr[p],arr[p+1...r]>arr[p]
int __partition(int arr[],int left,int right)
{
swap(arr[left],arr[rand()%(right-left+1)+left]); //改动2：随机找一个元素和arr[left]交换
int v=arr[left];
int j=left; //i和j的初值参考图片
for(int i=left+1;i<=right;i++)
{
if(arr[i]<v)
{
swap(arr[i],arr[j+1]);
j++;
}
}
swap(arr[left],arr[j]);
return j;
}
//对arr[left...right}部分进行快速排序
void __quickSort(int arr[],int left,int right)
{
if(right-left<=15)
{
insertionSort2(arr,left,right);
return;
}
int p=__partition(arr,left,right);
__quickSort(arr,left,p-1);
__quickSort(arr,p+1,right);
return;
}
void quickSort(int arr[],int n)
{
srand(time(NULL));//改动1：设置随机种子
__quickSort(arr,0,n-1);
return;
}1.4 版本4：
对于有大量重复元素的数组，前面的版本效率较差
从下图可以得知，对于有大量重复元素的数组，partition操作很可能将数组分成极度不平衡的两部分
新的思路：
之前把小于v、大于v的全都放在了数组的一边，现在将它们分别放在左右两边：
i从前往后扫描，直到碰到一个大于等于v的元素
j从后往前扫描，直到碰到一个小于等于v的元素
这种方法和之前的区别是把等于v的元素分散到了左右两边，更加平衡了
//对arr[left...right}部分进行partition操作
//返回p，使得arr[left...p-1]<=arr[p],arr[p+1...r]>=arr[p]
int __partition(int arr[],int left,int right)
{
swap(arr[left],arr[rand()%(right-left+1)+left]); //随机找一个元素和arr[left]交换
int v=arr[left];
int i=left+1; //i和j的初值参考图片
int j=right;
/*while(i<j)
{
while(i<j&& arr[i]<v)
i++;
while(i<j&& arr[j]>v)
j--;
if(i<j)
{
swap(arr[i],arr[j]);
i++;
j--;
}
}*/
while(true)
{
while(i<=right && arr[i]<v)
i++;
while(j>=left && arr[j]>v)
j--;
if(i>j)
break;
swap(arr[i],arr[j]);
i++;
j--;
}
swap(arr[left],arr[j]);
return j;
}
//对arr[left...right}部分进行快速排序
void __quickSort(int arr[],int left,int right)
{
if(right-left<=15)
{
insertionSort2(arr,left,right);
return;
}
int p=__partition(arr,left,right);
__quickSort(arr,left,p-1);
__quickSort(arr,p+1,right);
return;
}
void quickSort(int arr[],int n)
{
srand(time(NULL));//设置随机种子
__quickSort(arr,0,n-1);
return;
}1.5 版本5：
针对有大量元素的另一种改进方法-------三路快速排序
将整个数组分成三部分，在递归过程中，等于v的部分就不用考虑了，只需要同样的对另外两部分递归就可以了。
//对arr[left...right}部分进行快速排序
void __quickSort(int arr[],int left,int right)
{
if(right-left<=15)
{
insertionSort(arr,left,right);
return;
}
//partition
swap(arr[left],arr[rand()%(right-left+1)+left]);
int v=arr[left];
int lt=left;
int gt=right+1;
int i=left+1;
while(i<gt)
{
if(arr[i]==v)
i++;
else if(arr[i]>v)
{
swap(arr[i],arr[gt-1]);
gt--;
}
else
{
swap(arr[i],arr[lt+1]);
lt++;
i++;
}
}
swap(arr[i],arr[lt]);
lt--;
__quickSort(arr,left,lt);
__quickSort(arr,gt,right);
return;
}
void quickSort(int arr[],int n)
{
srand(time(NULL));//设置随机种子
__quickSort(arr,0,n-1);
return;
}2 归并排序和快速排序的衍生问题
2.1逆序对问题
（衡量数组的有序程度）
思路：类似merge sort
例题：数组中的逆序对
2.2 取数组中第n大的元素
思路之一：类似quick sort
例题：力扣215、数组中的第K个最大元素
代码示例：力扣215代码参考
