1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| class Solution { public: int partition(vector<int>& nums, int l, int r) { int pivot = nums[l]; int i = l, j = r + 1; while (i < j) { while (++i < r && nums[i] < pivot) ; while (--j > l && nums[j] > pivot) ; if (i < j) { swap(nums[i], nums[j]); } } swap(nums[l], nums[j]); return j; }
int randomized_partition(vector<int>& nums, int l, int r) { int i = l + rand() % (r - l + 1); swap(nums[i], nums[l]); return partition(nums, l, r); }
void quicksort(vector<int>& nums, int l, int r) { if (l < r) { int pivot = randomized_partition(nums, l, r); quicksort(nums, l, pivot - 1); quicksort(nums, pivot + 1, r); } }
vector<int> sortArray(vector<int>& nums) { quicksort(nums, 0, nums.size() - 1); return nums; } };
|