快排的两个重要思想
1. 找到分界点，两边进行排序 2. 原地排序我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。 原地排序 完整代码
class Solution { public: void sortColors(vector<int>& nums) { quik_sort(0,nums.size()-1,nums); } // 快排 void quik_sort(int p,int r, vector<int>& nums) { if(p>=r) return; int q=partition(p,r,nums); quik_sort(p,q-1,nums); quik_sort(q+1,r,nums); } int partition(int p,int r,vector<int>& nums) { // 函数作用是排序分成大于一部分和小于一部分 int pivot=nums[r]; int i=p; for(int j=p;j<r;j++) { if(nums[j]<pivot){ swap(nums[i],nums[j]); i++; } } swap(nums[i],nums[r]); for(auto value: nums) cout<<value<<" "; cout<<endl; cout<<i<<endl; return i; } };