Sắp xếp mảng số nguyên tăng dần. Ví dụ: [5,2,3,1] → [1,2,3,5].
Triển khai QuickSort thủ công:
partition(nums, low, high): pivot=low, duyệt i=low..high-1, nếu nums[i]
sortArr(nums, low, high): nếu low≥high return; partitionIndex = partition(...); sortArr(low, partitionIndex-1); sortArr(partitionIndex+1, high)
Gọi sortArr(0, n-1)
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int partition(vector <int>& nums, int low, int high){ int pivot = low; for(int i = low; i < high; i++){ if(nums[i] < nums[high]){ swap(nums[i], nums[pivot]); pivot++; } } swap(nums[pivot], nums[high]); return pivot; } void sortArr(vector <int>& nums, int low, int high){ if(low >= high) return; int pi = partition(nums, low, high); sortArr(nums, low, pi - 1); sortArr(nums, pi + 1, high); } vector<int> sortArray(vector<int>& nums) { sortArr(nums, 0, nums.size() - 1); return nums; } }; int main(){ vector<int> v1 = {5,2,3,1}; Solution ob; print_vector(ob.sortArray(v1)); }Đầu vào
[5,2,3,1]
Đầu ra
[1,2,3,5]