912 排序数组
堆排序
class Solution {
private:
void heapify(vector<int>& nums, int u, int heapSize) {
int smallest = u;
int l = 2 * u + 1, r = 2 * u + 2;
if (l < heapSize && nums[l] < nums[smallest])
smallest = l;
if (r < heapSize && nums[r] < nums[smallest])
smallest = r;
if (smallest != u) {
swap(nums[smallest], nums[u]);
heapify(nums, smallest, heapSize);
}
}
void buildMinHeap(vector<int>& nums, int heapSize) {
for (int i = nums.size() / 2; i >= 0; i--)
heapify(nums, i, heapSize);
}
public:
vector<int> sortArray(vector<int>& nums) {
vector<int> ans;
int heapSize = nums.size();
buildMinHeap(nums, heapSize);
for (int i = heapSize - 1; i >= 0; i--) {
ans.push_back(nums[0]);
swap(nums[0], nums[i]);
heapify(nums, 0, i);
}
return ans;
}
};
归并排序
class Solution {
private:
vector<int> tmp;
void mergeSort(vector<int>& nums,int l,int r){
if(l < r){
int mid = (l + r)>> 1;
mergeSort(nums,l,mid);
mergeSort(nums,mid+ 1,r);
int cnt = 0;
int i = l, j = mid + 1;
while(i <= mid && j <= r){
if(nums[i] <= nums[j])
tmp[cnt++] = nums[i++];
else
tmp[cnt++] = nums[j++];
}
while(i <= mid)
tmp[cnt++] = nums[i++];
while(j <= r)
tmp[cnt++] = nums[j++];
for(int i = 0; i < r - l + 1;i++)
nums[l+i] = tmp[i];
}
}
public:
vector<int> sortArray(vector<int>& nums) {
tmp.resize(nums.size(),0);
mergeSort(nums,0,nums.size() - 1);
return nums;
}
};
快速排序
class Solution {
private:
void quickSort(vector<int>& nums, int l, int r) {
// 注意是l < r
if (l < r) {
int idx = l + rand() % (r - l + 1);
int pivot = nums[idx];
int i = l - 1, j = r + 1;
while (i < j) {
do
i++;
while (nums[i] < pivot);
do
j--;
while (nums[j] > pivot);
if(i < j)
swap(nums[i],nums[j]);
}
// 因为是 l < r 所以这里是quickSort(nums, l, j)而不是quickSort(nums, l, j - 1)
quickSort(nums, l, j);
quickSort(nums, j + 1, r);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
quickSort(nums, 0, nums.size() - 1);
return nums;
}
};