C++实现的一个堆排序算法

堆排序是一个比较重要的排序算法，这个排序算法并不是一个最好的排序算法，但是这个算法使用了一种思想，通过数据结构来实现特定的目的的方法。
堆排序的算法依赖堆这种数据结构。
我们使用C++实现这个算法，有两个目的，第一熟悉C++面向对象的设计原则，第二熟悉资源管理的方法。

此例子实现一个CInt类，这个主要是模仿现实的情况，我们可能会对一组对象进行排序，针对这个场景，我们也是使用了智能指针配合序列容器进行排序操作，另外，STL库里面有排序算法，我们可以直接使用之。

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
using namespace std;

class CInt
{
public:
    CInt(int nNum) : m_nNum(nNum) {}
    ~CInt() { }
    CInt(const CInt & other) { m_nNum = other.m_nNum; }
    CInt & operator= (const CInt & other) 
    {
        m_nNum = other.m_nNum;
        return *this;
    }

    bool operator< (const CInt & other)
    {
        return m_nNum < other.m_nNum;
    }

    void SetNum(int nNum) { m_nNum = nNum; }
    int  GetNum() const { return m_nNum; }
private:
    int m_nNum;
};

typedef shared_ptr<CInt> CIntSPtr;

class CHeapSort
{
public:
    CHeapSort() {}
    ~CHeapSort() {}
private:
    CHeapSort(const CHeapSort & other);
    CHeapSort & operator= (const CHeapSort & other);

public:
    vector<CIntSPtr> Sort(const vector<CIntSPtr> & vecNum)
    {
        m_vecNum = vecNum;

        BuildHeap();
        Sort();

        return m_vecNum;
    }
private:
    void BuildHeap()
    {
        for (int i=m_vecNum.size()/2-1; i>=0; --i) {
            AdjustHeap(i, m_vecNum.size());
        }
    }

    void Sort()
    {
        for (int i=m_vecNum.size()-1; i>0; --i) {
            swap(m_vecNum[i], m_vecNum[0]);
            AdjustHeap(0, i);
        }
    }

    void AdjustHeap(size_t i, size_t HeapSize)
    {
        auto j = i;     
        auto left     = LEFT(i);
        auto right    = RIGHT(i);

        if (left  < HeapSize && *m_vecNum[j]<*m_vecNum[left])  j = left;
        if (right < HeapSize && *m_vecNum[j]<*m_vecNum[right]) j = right;

        if (j != i)
        {
            swap(m_vecNum[i], m_vecNum[j]);
            AdjustHeap(j, HeapSize);
        }
    }

    size_t LEFT(size_t i)
    {
        return 2 * i + 1;
    }

    size_t RIGHT(size_t i)
    {
        return 2 * i + 2;
    }

    size_t PARENT(size_t i)
    {
        return (i-1) / 2;
    }

private:
    vector<CIntSPtr> m_vecNum;
};

void OutPut(const CIntSPtr & a)
{
    cout << a->GetNum() << " ";
}

int main(int argc, char ** argv)
{
    const int LEN = 10;
    int a[LEN] = {0, 2, 7, 9, 8, 3, 4, 1, 5, 6};
    vector<CIntSPtr> vecNumber;

    for (int i=0; i<LEN; ++i) {
        vecNumber.push_back(CIntSPtr(new CInt(a[i])));
    }

    for_each(vecNumber.begin(), vecNumber.end(), OutPut);
    cout << endl;

    CHeapSort heap_sort;
    vecNumber = heap_sort.Sort(vecNumber);

    for_each(vecNumber.begin(), vecNumber.end(), OutPut);
    cout << endl;
    
    return 0;
}