一、题目
二、思路
看似一道很常规的排序题目，但是如果使用以前的快速排序模板（如下），会发现超时了！如下的Quicksort函数（递归）和划分枢轴的函数Partition。
class Solution { public: void Quicksort(vector<int>& nums, int low, int high){ if(low < high){ //partition划分操作，将原表划分成2表 int pivot = Partition(nums, low, high); Quicksort(nums, low, pivot - 1); Quicksort(nums, pivot + 1, high); } } int Partition(vector<int>& nums, int low, int high){ //当前表第一个元素被设置为枢轴，对表进行划分 int pivot = nums[low]; while(low < high){ while(low < high && nums[high] >= pivot) --high; //将比枢轴小的元素移动到左边 nums[low] = nums[high]; while(low < high && nums[low] <= pivot) ++low; //将比枢轴大的元素移动到右边 nums[high] = nums[low]; } //枢轴元素放到最终的位置 nums[low] = pivot; //返回存放枢轴的最终位置 return low; } vector<int> sortArray(vector<int>& nums) { int low = 0, high = nums.size() - 1; Quicksort(nums, low, high); return nums; } };
上面版本超时的原因是每次初始选的pivot初值都是数组的第一元素，可以随机初始选择这个pivot或者取中间位置的值。快速排序的思想是每次确定一个pivot枢轴，然后比它小的元素移动到它的左边，比它大的元素移动到它的右边，也即每趟快速排序都能确定一个最终的元素位置pivot后，将该位置的左右两边两个“不符合”的数进行交换。下面代码比上面这种更加简洁。
三、代码
class Solution { public: vector<int> sortArray(vector<int>& nums) { int n = nums.size(); quick_sort(nums,0,n-1); return nums; } void quick_sort(vector<int> &q ,int l,int r){ //递归边界 if(l>=r) return; //这里初值设置为l-1,r+1是因为while中是do,while结构 //先使i+1,j-1指向数组的第一和最后一个位置，再开始判断 int x = q[(l+r) >> 1],i = l-1, j=r+1; while(i<j){ //将比枢轴小的元素 do{i++;} while(q[i] < x); do{j--;} while(q[j] > x); if(i < j) swap(q[i], q[j]); } //递归左右子序列 quick_sort(q,l,j); quick_sort(q,j+1,r); } };
