QuickSort 拿下！
剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
由于这一题的解题思路是：首先将数组转换为字符数组，然后根据规则对其进行排序；排序的时候可以用到QuickSort（快速排序），又是一个没有系统研究过的tag，因此，特地对其进行一个仔细研究。
首先是代码
void QuickSort2(vector<int>& arr,int left,int right){
//快速排序，每次选取第一个元素作为基准数据，将数组分为两个部分，
//左边的元素都小于基准数据，右边的元素都大于基准数据。
if(left>=right)
return;
int low=left;
int high=right;
while(low<high){
while(low<high&&arr[high]>=arr[left])
high--;
while(low<high&&arr[low]<=arr[left])
low++;
swap(arr[low],arr[high]);
}
swap(arr[left],arr[low]);
QuickSort2(arr,left,low-1);
QuickSort2(arr,low+1,right);
}
然后是快速排序的思路
例如 [49, 38, 65, 97, 23]
首先选取第一个元素49，将余下的元素按照大小关系分布在49的两边，我们可以规定：比49小，放在左边，比49大，放在右边；
此时就是：[左边数组，49，右边数组]。这就是一次快速排列后的结果；
紧接着，我们同样对左边数组、右边数组使用快速排列，直到最后数组里面只有一个元素，此时数组里面的顺序就完成了！
思路就是这样，先不要想实现，思路你有了吗，是不是很easy！
最后是实现
我们可以采用递归的思路，例如我们的函数是QuickSort();当我们调用的时候，先执行一次快排，这样我们就将数组按照大小关系分布在了第一个元素的左右两边，然后调用QuickSort(左边数组)，QuickSort(右边数组)；
我最开始的思路是这样的：
void QuickSort(vector<int>& arr,int left,int right){
//快速排序，每次选取第一个元素作为基准数据，将数组分为两个部分，
//左边的元素都小于基准数据，右边的元素都大于基准数据。
if(left>=right)
return;
int low=left;
int high=right;
int tmp=arr[low];
while(low<high){
while(low<high&&arr[high]>=tmp)
high--;
arr[low]=arr[high];
while(low<high&&arr[low]<=tmp)
low++;
arr[high]=arr[low];
}
arr[low]=tmp;
QuickSort(arr,left,low-1);
QuickSort(arr,low+1,right);
}
而后，才修改成了上述QuickSort2的形式，两种都大同小异；
边界问题
执行完一次快排后的情况
此时 low=high ；但是，QuickSort2里面 swap(arr[left],arr[low]);，此时如果arr[low]>arr[left]的话，岂不是排了个寂寞？
swap(arr[left],arr[low]);
QuickSort2(arr,left,low-1);
QuickSort2(arr,low+1,right);
不存在这种情况： low指向的一定是比arr[left]小的数据，所以，如果在low的后面有比arr[left]大的数据，一定会被high遍历淘汰。
递归最后满足什么条件退出？
我们每次都是使用一个数据将数组分为两部分，然后对这两部分进行快速排列。
QuickSort2(arr,left,low-1);
QuickSort2(arr,low+1,right);
当由左右边界限定的数组长度小于2的时候，就可以退出了；当只有一个数的时候，显然不用排序，当left>right的时候，显然也不用，因为已经越界了
（越界的情况何时产生：例如[49,38,37,44，23],第一次快排后，low=high=4,此时调用： QuickSort2(arr,low+1,right);就会产生越界的情况）
c++完整代码
#include<iostream>
#include<vector>
using namespace std;
void QuickSort(vector<int>& arr,int left,int right){
//快速排序，每次选取第一个元素作为基准数据，将数组分为两个部分，
//左边的元素都小于基准数据，右边的元素都大于基准数据。
if(left>=right)
return;
int low=left;
int high=right;
int tmp=arr[low];
while(low<high){
while(low<high&&arr[high]>=tmp)
high--;
arr[low]=arr[high];
while(low<high&&arr[low]<=tmp)
low++;
arr[high]=arr[low];
}
arr[low]=tmp;
QuickSort(arr,left,low-1);
QuickSort(arr,low+1,right);
}
void QuickSort2(vector<int>& arr,int left,int right){
//快速排序，每次选取第一个元素作为基准数据，将数组分为两个部分，
//左边的元素都小于基准数据，右边的元素都大于基准数据。
if(left>=right)
return;
int low=left;
int high=right;
while(low<high){
while(low<high&&arr[high]>=arr[left])
high--;
while(low<high&&arr[low]<=arr[left])
low++;
swap(arr[low],arr[high]);
}
swap(arr[left],arr[low]);
QuickSort2(arr,left,low-1);
QuickSort2(arr,low+1,right);
}
int main(){
vector<int> Arr={
49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
QuickSort2(Arr,0,Arr.size()-1);
return 0;
}
快排的优化
这几天又刷了LC912. 排序数组，没有想到官方不讲武德，测试集里面新增加了一个很长的有序数组，那么我之前写的快排就会退化为时间复杂度为O(N2) ，这个时候就需要对快排进行一个优化，就是每次不是选取第一个元素作为基准，而是随机选取；
只需要增加一句即可：
void QuickSort3(vector<int>& arr,int left,int right){
//快速排序，每次选取第一个元素作为基准数据，将数组分为两个部分，
//左边的元素都小于基准数据，右边的元素都大于基准数据。
if(left>=right)
return;
//随机选取一个元素作为本次的基准
//(right - left + 1) 总共有几个数
//rand() % (right - left + 1) 随机选取一个数
//rand() % (right - left + 1) + left 这个数的实际下标
int i = rand() % (right - left + 1) + left;
swap(arr[left], arr[i]);
int low=left;
int high=right;
while(low<high){
while(low<high&&arr[high]>=arr[left])
high--;
while(low<high&&arr[low]<=arr[left])
low++;
swap(arr[low],arr[high]);
}
swap(arr[left],arr[low]);
QuickSort2(arr,left,low-1);
QuickSort2(arr,low+1,right);
}
这里记录一些刷题时候的总结思考
查看5道真题和解析