恐惧是生物的本能，勇气是人类的赞歌
经典快速排序
一次划分：
什么是快速排序的一次划分？
一次划分就是，找到一个基准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);}
};