题目描述
给你一个整数数组 nums，请你将该数组升序排列。
Example1:
输入：nums = [5,2,3,1] 输出：[1,2,3,5]
Example2:
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
提示
- 1 <= nums.length <= 50000
- -50000 <= nums[i] <= 50000
解题思路
- 简单dfs
class Solution {
public:
// ----------------------------
// quickSort
// ----------------------------
void QuickSort(vector<int>& nums, int begin, int end){
if(begin < end){
int pivot = partition(nums, begin, end);
QuickSort(nums, begin, pivot - 1);
QuickSort(nums, pivot + 1, end);
}
}
int partition(vector<int>& nums, int begin, int end){
int pivot = nums[begin];
while(begin < end){
while(begin < end && nums[end] >= pivot){
end--;
}
nums[begin] = nums[end];
while(begin < end && nums[begin] <= pivot){
begin++;
}
nums[end] = nums[begin];
}
nums[begin] = pivot;
return begin;
}
// ----------------------------
// mergeSort
// ----------------------------
void mergeSort(vector<int>& nums, vector<int>& temp, int begin, int end){
if(begin < end){
int mid = (begin + end) / 2;
mergeSort(nums, temp, begin, mid);
mergeSort(nums, temp, mid + 1, end);
merge(nums, temp, begin, mid, end);
}
}
void merge(vector<int>& nums, vector<int>& temp, int begin, int mid, int end){
int i = begin;
int j = mid + 1;
int k = 0;
while(i <= mid && j <= end){
if(nums[i] < nums[j]){
temp[k++] = nums[i++];
}else{
temp[k++] = nums[j++];
}
}
while(i <= mid){
temp[k++] = nums[i++];
}
while(j <= end){
temp[k++] = nums[j++];
}
k = 0;
while(begin <= end){ // 这里有等于号
nums[begin++] = temp[k++];
}
}
// ----------------------------
// heapSort
// ----------------------------
void heapAdjust(vector<int>& nums, int pos, int length){
int temp = nums[pos];
for(int k = 2 * pos + 1; k < length; k = 2 * k + 1){
if(k + 1 < length && nums[k] < nums[k + 1]){
k++;
}
if(nums[k] > temp){
nums[pos] = nums[k]; // 这里需要注意，应该先赋值，在改变pos的值
pos = k;
}else{
break;
}
}
nums[pos] = temp;
}
void heapSort(vector<int>& nums, int length){
for(int i = length / 2 - 1; i >= 0; i--){ // 从最后一个非叶子节点的父结点开始建堆
heapAdjust(nums, i, length);
}
for(int j = length - 1; j > 0; j--){
swap(nums[0], nums[j]);
heapAdjust(nums, 0, j);
}
}
vector<int> sortArray(vector<int>& nums) {
// QuickSort(nums, 0, nums.size() - 1);
// vector<int> temp(nums.size());
// mergeSort(nums, temp, 0, nums.size() - 1);
heapSort(nums, nums.size());
return nums;
}
};
