Problem: 912. Sort an Array 排序数组
堆排序可以通过，快速排序会超时
Code
class Solution { public: vector<int> arr; void maxheapify(int dad, int len) { int son = dad * 2 + 1; while(son < len) { if(son + 1 < len && arr[son + 1] > arr[son]) { son++; } // if(arr[son] <= arr[dad]) continue; if(arr[son] > arr[dad]) { swap(arr[son], arr[dad]); } dad = son; son = dad * 2 + 1; } } void quicksort(int l, int r) { if(l >= r) return; int h = arr[l]; int left = l; int right = r; while(right > left) { while(right > left && arr[right] >= h) right--; if(right > left) { arr[left] = arr[right]; } while(right > left && arr[left] <= h) left++; if(right > left) { arr[right] = arr[left]; } } arr[left] = h; quicksort(l, left-1); quicksort(left + 1, r); } vector<int> sortArray(vector<int>& nums) { int len = nums.size(); arr = nums; // heap for(int i = len/2 - 1; i >= 0; i--) { maxheapify(i, len); } for(int i = len - 1; i >= 0; i--) { swap(arr[0], arr[i]); maxheapify(0, i); } // quick sort // quicksort(0, len - 1); return arr; } };
