快速排序及其优化【图文详解】
恐惧是生物的本能，勇气是人类的赞歌
经典快速排序
一次划分：
什么是快速排序的一次划分？
一次划分就是，找到一个基准x，经过调整，也就是一次划分过后，可以把数组分为两个部分，一个都是大于x的，一个都是小于x的部分。
比如给你一个数组，以6为基准的话,经过一次划分后，变成如下图：左边部分是都是小于6的，右边部分都是大于6的，这就是一次划分的作用。
-
找到一个基准x(可以是第一个数据)
-
从后往前找比基准小的数据往前移动
-
从前往后找比基准大的数据往后移动
-
重复1)和2)直到找到基准位置 这个就是快速排序的 一次划分，也叫partition过程，时间复杂度是O(n)
int Partion(int* arr, int low, int high)//O(n)
{
while (low < high)
{
//从后往前找小的，大的往后挪动
while (low<high && arr[high]>tmp)
{
high--;
}//找到了
if (low < high)
arr[low] = arr[high];//把小的数值往前挪
//从前往后找小的，小的往前挪动
while (low < high && arr[low] < tmp)
{
low++;
}//找到了
if (low < high)//把大的数值往后挪动
arr[high] = arr[low];
}
arr[low] = tmp;
return low;
}
void Quick(int* arr, int low, int high)
{
if(low>=high)return ;
int par = Partion(arr, low, high);//par是下标，是经过一次划分过后的下标
Quick(arr, low, par - 1);
Quick(arr, par + 1, high);
}
//递归地调用快速排序
void QuickSort(int* arr, int len)//对外表现都是两个参数，自己内部需要三个参数，自己内部解决
{
Quick(arr, 0, len - 1);//把下标传进去
}
int main()
{
int arr[] = { 12,3,4,5 };
QuickSort(arr, sizeof(arr) / sizeof(arr[0]));
for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++)
printf("%d ", arr[i]);
return 0;
}
快速排序的优化
-
一.在选择基准的时候，随机选择数字，而不是挨个选
int x = nums[l + rand() % (r - l + 1)]; -
二.一次划分的过程，如果有大量的重复元素存在，那么经典的快速排序就会降低速度，我们可以每次把同一个数字全都整理好，比如数字1，每次全都处理了，左边的数字全都是小于1的，中间的数字全都是大于1的，右边的数字全都是大于1的。也叫荷兰国旗划分！
-
接下来举个例子，代码是如何操作的！
-
比如有一个数组是
2,1,3,4,2,0，以2为基准
-
最后目标是变成这个样子
-
定义三个变量，i，L，R分别表示遍历的下标，左边界，和右边界，i一个一个遍历，如果当前数字小于基准，那么往左边界发货，如果等于基准，i++，如果大于基准，那么往右边发货。具体来说；
-
如果
nums[i]==x那么i++ -
如果
nums[i]<x，那么交换nums[i],nums[L],i++，L++ -
如果
nums[i]>x,那么交换nums[i],nums[R],R--
-
图解：i开始遍历
-
最后一次划分就就得到了2的左边界都是小于2的，2的右边界都是大于2的。把2这个数字全都处理好了
class Solution {
public:
static int first;
static int last;
public:
//三路划分，一次性把x划分好
void partition(vector<int>&nums,int l,int r,int x){
first=l;
last=r;
int i=l;
while(i<=last){
if(nums[i]==x){
i++;
} jcmelse if(nums[i]<x){
swap(nums[first++],nums[i++]);
}else{
swap(nums[i],nums[last--]);
}
}
}
void Qsort(vector<int>&nums,int l,int r)
{
if(l>=r){
return ;
}
//随机
int x = nums[l + rand() % (r - l + 1)];
partition(nums,l,r,x);
int left=first;
int right=last;
Qsort(nums,l,left-1);
Qsort(nums,right+1,r);
}
int sort+(vector<int>& nums, int k) {
Qsort(nums,0,nums.size()-1);
}
};