堆排序

堆排序 = 建堆 +排序（交换）

//heapSort.h
#ifndef _HEAP_SORT_H_
#define _HEAP_SORT_H_
#include <vector>
#include <iostream>
using std::cout;
using std::endl;
using std::vector;
using std::swap;


void heapify(vector<int>&nums, size_t N, size_t parent); //大顶堆,下沉
void heapSort(vector<int>& nums);

#endif //_HEAP_SORT_H_

//heapSort.cc
#include "heapSort.h"
void heapify(vector<int>&nums, size_t N, size_t parent) {   //大顶堆,下沉
    size_t son = 2 * parent + 1;    //默认先选择左孩子
    while(son < N) {
        if(son + 1 < N && nums[son + 1] > nums[son]) {  //右孩子存在且比左孩子大
            ++son;  //son为右孩子
        }
        if(nums[son] > nums[parent]) {
            swap(nums[son], nums[parent]);
            parent = son;
            son = 2 * parent + 1;
        }
        else {
            break;  //如果父结点最大，终止循环
        }
    }
}


void heapSort(vector<int>& nums) {
    //建堆
    size_t len = nums.size();
    for(int i = len / 2 - 1; i >= 0; --i) { //最后一个父结点的位置为N/2 - 1
        heapify(nums, len, i);
    }
    swap(nums[0], nums[len - 1]);
    
    //排序
    for(int l = len - 1; l > 0; --l) {
        heapify(nums, l, 0);
        swap(nums[0], nums[l - 1]);
    }
}

性能

1. 建堆的时间复杂度为O(N)
2. heapify复杂度O(logN)
3. 堆排序对N个数进行heapify

堆排序的时间复杂度：O(NlogN)

为何堆排序是不稳定排序?

当数组中有相等元素时，堆排序算法对这些元素的处理方法不止一种，故是不稳定的