C++模板类之堆排序

Posted by Harid十二月 - 6 - 2010 Leave comments

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

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

堆排序的基本思想是:

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

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

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

代码如下sort.h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#ifndef HEAPSORT_H_
#define HEAPSORT_H_
#include <iostream>
template <class Type>
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 <class Type>
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 <class Type>
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 <class Type>
void HeapSort::setupHeap(Type const* arr, const int size)
{
    for(int i=(getLength()-1)/2; i>=0; i--)
        maxHeap(arr, i, size);
}
template <class Type>
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 <class Type>
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 <class Type>
HeapSort::HeapSort(Type * arr, int length)
{
    m_inputArr = arr;
    m_length = length;
    this->sort(m_inputArr);
    this->m_detect = false;
}
template <class Type>
HeapSort::~HeapSort()
{
    if(m_detect)
        delete [] m_inputArr;
}
#endif

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

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

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


分享按钮