C++模板类之堆排序

Posted by Harid2010 - Dec - 06 留个言

嘿嘿,貌似我这几天一直在搞排序,什么《C++模板类插入排序》、《C++模板类冒泡排序》,嗯,再搞几个我就不搞了,换换口味。另外,我得认真上自习、看书了……

今天这个叫“堆排序”。堆排序的时间代价是O(nlgN),它与前面两种排序方法一样都是原地排序,而且它和合并排序同为渐近最优的比较排序算法。

堆排序的基本思想是:

首先,将输入的一串数用数组保存,并维护成最大堆。最大堆是二叉堆的一种,可以看成是一棵树。树的根保存的是这一串数里面最大的数,而且每一棵子树的根的值也绝对是子树里的最大数,也就是树的父结点一定大于其左儿子与右儿子。我们需要创建一个方法来时时维护最大堆的特性,该方法能够递归实现父结点以下的所有的结点完成最大堆排列;

然后,堆建立好之后,进行排序。因为整棵树的根结点正是这一串数里面的最大数,所以在一次循环里将整个树(最大堆)的根值与数组里最后一个替换,则完成了将这一串数里的最大值排序至原数组的最后一个的工作,然后逻辑减小堆的大小,也就是让刚刚我们替换好了的那个最大值不再参于第二次最大堆的构建,这样,第二大的数就排到了当前最大堆(树)的根部,然后再替换其至原数组的倒数第二个位置,如此循环,直到将最大堆大小减小至只剩两个结点时,则可以结束了;

最后,输出原数组就行了(原数组已排好序了);

代码如下sort.h:

#ifndef HEAPSORT_H_
#define HEAPSORT_H_
#include 
template 
class HeapSort
{
private:
    Type* m_inputArr;    //原始输入队列,同时存储排好序的数组
    int m_length;        //堆长度
    bool m_detect;         //侦测是用到哪一个构造函数
    void getInput();     //获得输入
    void maxHeap(Type const*, const int, const int);      //保持最大堆性质
    void setupHeap(Type const*, const int);   //产生最大堆
    void sort(Type const*);      //总排序方法
public:
    HeapSort();
    HeapSort(Type*, int);
    ~HeapSort();
    int getLength(){
        return m_length; }
    void show();
};
template 
void HeapSort::getInput()
{
    using namespace std;
    cout <<"Please enter the length you wanna sort: ";
    while(!(cin >>m_length) || m_length<0 || cin.get()!='\n')
    {
        cerr <<"Error, enter a positive number:  ";
        cin.clear();
        while(cin.get()!='\n')
            continue;
    }
    m_inputArr = new Type[m_length+1];
    for(int i=0; i<<"\tenter="" #"<<<"="" number:="" ";="" while(!(cin="">>m_inputArr[i]) || m_length<0 || cin.get()!='\n')
        {
            cerr <<"Error, enter a positive number:  ";
            cin.clear();
            while(cin.get()!='\n')
                continue;
        }
    }
    m_inputArr[m_length] = '\0';
}
template 
void HeapSort::maxHeap(Type const* arr, const int node, const int size)
{
    int left = 2 * node + 1;
    int right = left + 1;
    int largest = node;
    if((leftm_inputArr[largest]))
        largest = right;
    if(largest != node)
    {
        m_inputArr[node] += m_inputArr[largest];
        m_inputArr[largest] = m_inputArr[node] - m_inputArr[largest];
        m_inputArr[node] -= m_inputArr[largest];
        maxHeap(arr, largest, size);
    }
}
template 
void HeapSort::setupHeap(Type const* arr, const int size)
{
    for(int i=(getLength()-1)/2; i>=0; i--)
        maxHeap(arr, i, size);
}
template 
void HeapSort::sort(Type const* arr)
{
    this->setupHeap(m_inputArr, getLength());
    int size = getLength();
    while(size>=2)
    {
        m_inputArr[size-1] += m_inputArr[0];
        m_inputArr[0] = m_inputArr[size-1] - m_inputArr[0];
        m_inputArr[size-1] -= m_inputArr[0];
        size--;
        this->maxHeap(arr, 0, size);
    }
}
template 
void HeapSort::show()
{
    using namespace std;
    cout <<"The ordered arrar is :\n\t";
    for(int i=0;i<<<"="" ";="" }="" <
HeapSort::HeapSort()
{
    this->getInput();
    this->sort(m_inputArr);
    this->m_detect = true;
}
template 
HeapSort::HeapSort(Type * arr, int length)
{
    m_inputArr = arr;
    m_length = length;
    this->sort(m_inputArr);
    this->m_detect = false;
}
template 
HeapSort::~HeapSort()
{
    if(m_detect)
        delete [] m_inputArr;
}
#endif

   声明:本文采用 BY-NC-SA 协议进行授权 | 星期九
   原创文章转载请注明:转自《C++模板类之堆排序

Comments(53) Leave comments
  1. Gravatar
    Tanky Woo SouGou Browser SouGou Browser 2.X Windows Windows XP
    十二月 20th, 2010 at 20:09  | #1

    我今晚也写了一个。《算法导论》第六章讲的很给力,你可以看看。

    • Gravatar Harid  @  十二月 20th, 2010 at 20:40 replied.

      @Tanky Woo, 嘿嘿,我喜欢写这些小程序,以写库的方式写,以后可以直接拿来用。

  2. Gravatar
    WordPress啦 Mozilla Firefox Mozilla Firefox 3.6.12 Windows Windows XP
    十二月 10th, 2010 at 12:10  | #3

    貌似有点灰常的复杂啊,额,哈哈

    • Gravatar Harid  @  十二月 11th, 2010 at 12:34 replied.

      @WordPress啦, 🙂 ,如果尝过C++,这个其实很简单的。你就你的PHP,我没有学过,我觉得灰常的复杂。

  3. Gravatar
    C瓜哥 Mozilla Firefox Mozilla Firefox 3.6.10 Windows Windows XP
    十二月 8th, 2010 at 18:01  | #4

    1、你不是学硬件的吗?
    2、你知道时间复杂度是多少,你会自己算吗?

    • Gravatar Harid  @  十二月 8th, 2010 at 18:23 replied.

      @C瓜哥, 算时间复杂度我没有看过,只是记住一些常用算法的时间复杂度我觉得对于我来说就够了。我是学硬件的呀。

      • Gravatar C瓜哥  @  十二月 8th, 2010 at 20:31 replied.  | #5

        @Harid,
        学硬件的为什么要学C++呢? 😀

        • Gravatar Harid  @  十二月 11th, 2010 at 12:38 replied.

          @C瓜哥, 我个人比较喜欢C++,而且学硬件要求软硬兼通,当然这里的“通”不是说要像你们那样精通,我们可以不用去在乎GUI,但是必须得能写出程序来,因为很多时候需要跑测试,没有软件的硬件是没有灵魂的。

          • Gravatar C瓜哥  @  十二月 11th, 2010 at 13:13 replied.  | #6

            @Harid,
            学硬件太枯燥了 😥

Pages:
55 + 81 =  (required)
comment_ad

 NOTICE1: You should type some Chinese word (like “你好”) in your comment to pass the spam-check, thanks for your patience!

 NOTICE2: 请申请gravatar头像(http://en.gravatar.com),木有头像的会显示为“小怪物”头像,将难以通过审核!

分享按钮