堆排序简述

不多说了，又把排序搞忘掉了，捡起捡起~
今天我说的堆排序中的堆，跟我们程序运行时，内存分布中的堆（如下图），不一样（此处应该有背景音乐）

今天要讲的堆排序，是以数组方式存储，以二叉树形式视之的一种排序算法~假设，我们有一个数组，要求对其非递减排序，我们可以将整个数组视为一个二叉树（为了方便起见，我们从下标1开始），保证以下性质成立：
（1）在保证下标不越界的情况下，一个元素（下标为idx）的左孩子为2*idx， 右孩子为2*idx+1
（2）保证非叶子节点必须大于其孩子；
我们用如下的代码来保证这条性质（也就是堆排序中的重中之重），heapsz为一个全局变量（为了简便）：

void heapify(int idx, int *arr){
    int maxIdx = idx, lchld = 2*idx, rchld = 2*idx+1, tmp;
    if(lchld<=heapsz&&arr[maxIdx]<arr[lchld]){
        maxIdx = lchld;
    }
    if(rchld<=heapsz&&arr[maxIdx]<arr[rchld]){
        maxIdx = rchld;
    }
    if(maxIdx!=idx){
        tmp = arr[idx];arr[idx]=arr[maxIdx];arr[maxIdx] =tmp;
        heapify(maxIdx, arr);
    }
}

性质保证完了，接下来我们就要建堆了，只需从下标为heapsz/2的下标递减遍历到下标1 即可：

void create_heap(int *arr){
    for(int i = heapsz/2; i >=1; i--){
        heapify(i, arr);
    }
}

现在我们建成了一个大顶堆，保证每个元素均比其孩子大，将其排序的话，只需将下标为1和下标为heapsz的元素交换，heapsz减1，heapiy(1, arr)即可~~

void heap_sort(int *arr){
    int tmp;
    for(;heapsz>1;){
        tmp = arr[heapsz];arr[heapsz]=arr[1];arr[1] =tmp;
        heapsz --;
        heapify(1, arr);
    }
}

自己写的一个小程序如下：

#include <iostream>

using namespace std;
void heapify(int idx, int *arr);
void create_heap(int *arr);
void heap_sort(int *arr);
int heapsz = 10;
int main()
{
    int arr[] = {-1, 87, 76, 34, 3, 22, 57, 90, 19, 65, 12};
    create_heap(arr);
    for(int i = 1; i <= 10; i++)
        cout << arr[i]<<" ";
    cout<<endl;
    heap_sort(arr);
    for(int i = 1; i <= 10; i++)
        cout << arr[i]<<" ";
    cout<<endl;
    return 0;
}
void heapify(int idx, int *arr){
    int maxIdx = idx, lchld = 2*idx, rchld = 2*idx+1, tmp;
    if(lchld<=heapsz&&arr[maxIdx]<arr[lchld]){
        maxIdx = lchld;
    }
    if(rchld<=heapsz&&arr[maxIdx]<arr[rchld]){
        maxIdx = rchld;
    }
    if(maxIdx!=idx){
        tmp = arr[idx];arr[idx]=arr[maxIdx];arr[maxIdx] =tmp;
        heapify(maxIdx, arr);
    }
}
void create_heap(int *arr){
    for(int i = heapsz/2; i >=1; i--){
        heapify(i, arr);
    }
}
void heap_sort(int *arr){
    int tmp;
    for(;heapsz>1;){
        tmp = arr[heapsz];arr[heapsz]=arr[1];arr[1] =tmp;
        heapsz --;
        heapify(1, arr);
    }
}

输出结果如图：

大家轻拍了哈~~~