堆排序

堆排序(HeapSort)是利用堆积树（堆）这种数据结构设计的一种排序方法。

特性：

1、时间复杂度：N log N

2、由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件

3、不稳定的排序方法（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后他们的相对位置不发生变化）

4、最大堆性质： A[ parent(i) ] >= A[ i ] , 即叶子结点不大于根节点；最小堆满足 A[ parent(i) ] <= A[ i ]

堆排序分三个步骤：

1、堆的维护：其时间复杂度是O(nlog n),

2、堆的建立：功能是从一个无序的数组中构建一个最大堆

3、堆排序：时间复杂度是 O(nlog n) 功能是对一个数组进行原址排序

伪代码：

//堆的维护

MAX - HEAPIFY(A, currentNode)
leftNode = 2 * currentNode + 1 //根节点的左孩子下标计算
rightNode = 2 * currentNode + 2 //根节点的右孩子下标计算
if leftNode < A.heapSize and A[leftNode] > A[currentNode]) //找出当前树种根、左叶子和右叶子的最大值及下表
largest = leftNode;
else largest = currentNode;
if rightNode < A.heapSize and A[rightNode] > Ar[largest])
largest = rightNode;
if largest != currentNode // 将最大值赋值给根节点。并记录最大值的下标（若有交换），对交换后的根结点递归调用MaxHeap（）
exchange A[currentNode] with A[largest]
MaxHeap(A,largest); //当根节点与叶子节点交换后，对堆进行维护，对交换后再对子树进行维护

//堆的建立

BUILD - MAX - HEAP(A)
A.HeapSize = A.length //length指数组中元素个数
for i = [A.length/2] downto 0 //在实际编码时，元素下标最小为0，所以，这里与算法导论书上有区别
MAX - HEAPIFY( A, i )

//堆排序
HEAPSORT(A)
BUILD - MAX - HEAP(A) // 将无序数组用堆排序，此时，数组中的最大元素总是在 A[0]中
for i = A.length downto 0
exchange A[0] with A[i] // 通过将A[0] 与 A[n]交换，可以使该元素放在正确的位置，并使HeapSize-1
A.HeapSize = A.HeapSize -1
MAX - HEAPIFY(A,0)

以下，将堆建立成为一个类，用三个成员函数完成三个功能。用最大堆排序代码：

#include<iostream>
#include"math.h"
using namespace std;
template<class T>
class Heap
{
public: 
    int HeapSize;
    T* Arry;
    void MaxHeap(int i);                           //维护堆
    void buildHeap(T* arry, int heapSize);         //建立堆
    void HeapSort(T* arry, int heapSize);          //堆排序
};

template<class T>
void Heap<T>::MaxHeap(int currentNode)
{
    int largest;
    int leftNode = 2 * currentNode + 1;
    int rightNode = 2 * currentNode + 2;
    //找出当前树种 根、左叶子和右叶子的最大值及下表，将最大值赋值给根节点。并记录最大值的下标（若有交换），对交换后的根结点递归调用MaxHeap（）
    if (leftNode < HeapSize&&Arry[leftNode] > Arry[currentNode]) 
        largest = leftNode;
    else
        largest = currentNode;
    if (rightNode < HeapSize&&Arry[rightNode] > Arry[largest])
        largest = rightNode;
    if (largest != currentNode)
    {
        T temp = Arry[currentNode];
        Arry[currentNode] = Arry[largest];
        Arry[largest] = temp;
        this->MaxHeap(largest);            //当根节点与叶子节点交换后，对堆进行维护，对交换后再对子树进行维护
    }
}
template<class T>
void Heap<T>::buildHeap(T* arry, int heapSize)              //建立堆
{
    this->HeapSize = heapSize;
    Arry = new T[heapSize];                       //将数据读入到堆中
    for (int i = 0; i < heapSize; i++)
        Arry[i] = arry[i];
    int degree = log(heapSize) / log(2);        //求二叉树的深度-1,由于倒数第一层叶子节点没有叶子，在维护时要从倒数第二层开始遍历
    for (int i = pow(2, degree)-1; i>=0; i--)
        this->MaxHeap(i);
}

template<class T>
void Heap<T>::HeapSort(T* arry, int heapSize)          //堆排序，将用堆排序好的数据输出到数组
{
    buildHeap(arry, heapSize);                  //建立堆，此时，数组中的最大元素总是在 Arry[0]中
    for (int i = heapSize - 1; i > 0; i--)      // 通过将Arry[0] 与 Arry[n]交换，可以使该元素放在正确的位置，并使HeapSize-1
    {
        T temp = this->Arry[0];           
        this->Arry[0] = this->Arry[i];      
        this->Arry[i] = temp;
        this->HeapSize--;
        MaxHeap(0);
    }
}

测试代码：

int main()
{
    int arry[] = { 21, 1200, 9, 1, 5, 8, 19, 4, 7, 10, 15, 17, 21, 41, 51, 61, 81, 71, 91, 100 };
    Heap<int>hs;
    hs.HeapSort(arry, 20);
    for (int i = 0; i < 20; i++)
        cout << hs.Arry[i] << " ";
    cout << endl;
    cout << "BigThink" << endl;
    system("pause");
    return 0;
}

View Code