大一计算机的自学总结：随机快速排序及随机快速算法
前言
和归并排序一样，随机快速排序的时间复杂度也是O(n*logn)。
一、随机快速排序
随机快速排序的特点就是“随机”，通过随机选择一个数，从而可以满足在任何情况下时间复杂度都为O(n*logn)。
注意，若过程中选择的数不随机，时间复杂度会根据数据的不同而改变。
1.未优化版
#include<bits/stdc++.h>
using namespace std;
//全局变量
#define n 10
int arr[n];
//划分
int partition(int l,int r,int x)
{
int a=l,xi=0;
for(int i=l;i<=r;i++)
{
if(arr[i]<=x)
{
int t=arr[a];
arr[a]=arr[i];
arr[i]=t;
if(arr[a]==x)
{
xi=a;
}
a++;
}
}
int t=arr[xi];
arr[xi]=arr[a-1];
arr[a-1]=t;
return a-1;
}
//随机快速排序 ——未优化版
void quickSortUnOptimized(int l,int r)
{
if(l>=r)
return ;
//设置[a,b]内随机数 -> rand()%(b-a+1)+a
srand(time(0));
int x=arr[rand()%(r-l+1)+l];
int mid=partition(l,r,x);//找x下标并划分
quickSortUnOptimized(l,mid-1);
quickSortUnOptimized(mid+1,r);
}
int main()
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
//随机快速排序
quickSortUnOptimized(0,n-1);
cout<<"Sorted:"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}对于随机快速排序，也可以使用调递归的方法，只需要注意其中随机生成数的代码。
重点是partition函数，通过这个随机出来的数x，将数组划分成小于等于和大于x的部分。通过不断划分，实现整个排序过程。
首先让a=l，用a来表示小于等于x的边界，然后遍历整个从l到r的部分，若小于等于x，就让该位置的数和a位置的数交换，若等于x，则记一下此时的下标，然后让边界a往下移。最后，将xi位置和边界a位置交换，保证等于x的数位于边界处并返回x的位置。
2.优化版——荷兰国旗问题
可以看出，未优化版中，若有多个等于x的数，则一次划分只能选出一个，不够简便。
#include<bits/stdc++.h>
using namespace std;
//全局变量
#define n 10
int arr[n];
int a,b;//左右范围
//划分 ——荷兰国旗问题
void partition(int l,int r,int x)
{
a=l;
b=r;
int i=l;
while(i<=b)
{
if(arr[i]==x)
{
i++;
}
else if(arr[i]<x)
{
int t=arr[a];
arr[a]=arr[i];
arr[i]=t;
a++;
i++;
}
else if(arr[i]>x)
{
int t=arr[b];
arr[b]=arr[i];
arr[i]=t;
b--;
}
}
}
//随机快速排序 ——优化版
void quickSortOptimized(int l,int r)
{
if(l>=r)
return ;
srand(time(0));
int x=arr[rand()%(r-l+1)+l];
partition(l,r,x);
int left=a;
int right=b;//防止修改a,b值
quickSortOptimized(l,left-1);
quickSortOptimized(right+1,r);
}
int main()
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
//随机快速排序
quickSortOptimized(0,n-1);
cout<<"Sorted:"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}优化之后的划分函数会将数组划分成小于x的部分、等于x的部分和大于x的部分。由于这种划分成三段的方式很像荷兰国旗，所以这个问题就叫“荷兰国旗问题”。
重点依旧是划分函数，为了返回两个边界，所以考虑设置全局变量a,b，每次让a=l,b=r，遍历整个部分，若小于x则交换，并让a++,i++；若等于则只需要让i++；若大于，交换后只让b--，因为此时交换过来的数不清楚大小，需要i维持原位置再比较一次。
注意，为了防止改变两边界的值，需要额外设置left和right两变量。
二、随机快速算法——数组中的第K个最大元素
class Solution {
public:
int a,b;
void swap(vector<int>&nums,int x,int y)
{
int t=nums[x];
nums[x]=nums[y];
nums[y]=t;
}
void partition(vector<int>&nums,int l,int r,int x)
{
a=l;
b=r;
int i=l;
while(i<=b)
{
if(nums[i]==x)
{
i++;
}
else if(nums[i]>x)
{
swap(nums,i,b);
b--;
}
else
{
swap(nums,i++,a++);
}
}
}
int solve(vector<int>&nums,int i)
{
int ans=0;
for(int l=0,r=nums.size()-1;l<=r;)
{
srand(time(0));
int x=nums[rand()%(r-l+1)+l];
partition(nums,l,r,x);
if(i<a)
{
r=a-1;
}
else if(i>b)
{
l=b+1;
}
else
{
ans=nums[i];
break;
}
}
return ans;
}
int findKthLargest(vector<int>& nums, int k) {
return solve(nums,nums.size()-k);
}
};因为要求时间复杂度为O(n)，所以就不能排序。
考虑第k大的这个条件，即找数组第n-k位置的数，此时可以使用荷兰国旗的划分方法和二分搜索的思想，即划分后可以确定一侧必有一侧必没有。
划分函数如上，主函数只要一直循环，每次通过比较n-k位置和边界a,b从而确定去到哪一边继续。
总结
随机快速排序最显著的特点就是随机选数，可以将面对所有数据情况的时间复杂度全变为O(n*logn)。而随机快速算法就是在这一点的基础上，加入二分搜索的思想，在划分后确定一次必有和一侧必没有。