解题思路

  • 大根堆有很好的性质，有助于升序排序
    • 大根堆的根节点一定是最大的，可以用作“选择排序”，一次性选出最大的元素放到末尾
    • 每次调整大根堆的时间复杂度为O(logN)

复杂度分析

时间复杂度：O(NlogN)
空间复杂度：O(1)
是否稳定：不稳定（调整堆的过程中，需要选择交换哪个元素，导致了不稳定性）

代码

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. using namespace std;
  6. // 将数组中的元素nums[i]放到大根堆中的合适位置
  7. void adjustHeap(vector<int>& nums, int i, int length) {
  8.     // 先将nums[i]取出
  9.     int temp = nums[i];
  11.     // k用来层层遍历左右儿子节点
  12.     // i用来找temp的合适的插入位置
  13.     for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
  14.         if (k + 1 < length && nums[k + 1] > nums[k]) {
  15.             ++k;
  16.         }
  18.         // 子节点比父节点大，说明需要向下调整
  19.         if (nums[k] > temp) {
  20.             nums[i] = nums[k];
  22.             // 再往下找合适的插入位置
  23.             i = k;
  24.         } else {
  25.             break;
  26.         }
  27.     }
  28.     nums[i] = temp;
  29. }
  32. void heapSort(vector<int>& nums) {
  33.     int size = nums.size();
  35.     // nums[size/2-1]是第一个非叶节点
  36.     for (int i = size / 2 - 1; i >= 0; --i) {
  37.         adjustHeap(nums, i, size);
  38.     }
  40.     for (int i = size - 1; i >= 0; --i) {
  41.         swap(nums[0], nums[i]);
  42.         adjustHeap(nums, 0, i);
  43.     }
  44. }
  46. int main(void) {
  47.     vector<int> input {9,8,7,6,5,4,3,2,1};
  48.     heapSort(input);
  49.     for (const auto& n : input) {
  50.         cout << n << " ";
  51.     }
  52.     return 0;
  53. }

参考资料