基于C++的堆排序实现

发表于 | 分类于 ， ， | 阅读次数：
本文字数： 2.2k | 阅读时长 ≈ 2 分钟

前言

大二上我选修了C++课，因为这门语言我从未学到其精妙之处，所以想要好好学一学。由于平时学业比较繁重，我没有时间将做过的四门实验与大作业发布到博客上。因此，趁着寒假空闲时间，我将落下的几篇博文一一补上。

第一个实验是用C++实现堆排序。虽然C++的STL库可以直接调用优先队列，实现与堆排序相同的功能，但是堆的思想还是有必要好好学一学。不过对我而言，都是学过的东西，稍微回忆一下也都记得个大概，敲起来也并不费事。

原理

首先将需要排序的所有元素建立成一个大顶堆。根据大顶堆的定义，父节点上的元素必然大于其子节点上的元素，因此在堆顶上的元素是堆中最大的。然后依次弹出堆顶的元素，即可得到一个有序的数组。

实现

方法

建立大顶堆的时候，每次从堆底插入新元素，然后与其父节点比较，如果小于其父节点则不变。如果该节点大于其父节点，则与其父节点进行交换，然后再与新的父节点进行比较，重复上述操作直至小于父节点或者达到堆顶。
建立堆

删除堆顶元素时，将堆顶元素与堆底元素进行交换。然后维护剩下元素的大顶堆。将新的堆顶元素与其子节点中较大的那个进行比较，如果该元素比子节点小，则进行交换，然后重复上述操作，直到该元素比它的两个子节点都要大或者达到堆底。
删除堆

代码

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
#include <iostream>
#define n 6
using namespace std;

//函数模板，能够使得函数调用参数为任意类型
template <typename T>
inline Swap(T &a,T &b){
    T t=a;
    a=b;
    b=t;
}

//从堆底插入新的元素
template <typename T>
void Insert(T h[],int k){
	//由于下标是从0开始，所以要在这里加一。
	k++;
	//插入数从底部上升
    while(k>1){
        int t=k/2;
        if(h[t-1]<h[k-1])Swap(h[t-1],h[k-1]);
        else break;
        k=t;
    }
}

//删除堆顶的元素
template <typename T>
void Delete(T h[],int m){
	//将堆顶的元素与堆末尾的元素进行交换，即删除操作。
	Swap(h[0],h[m]);

	//调整堆，将堆顶的数下降。
    int k=1;
    while(k*2<m){
        int t=k*2;
        t--,k--;
        if(t+1<m&&h[t]<h[t+1])t++;
        if(h[t]>h[k])Swap(h[t],h[k]);
        else break;
        k=t+1;
    }
}

template <typename T>
void heapSort(T h[]){
	//通过插入过程实现建立堆
	for(int i=1;i<n;i++)Insert(h,i);
	//通过删除过程实现排序
    for(int i=n-1;i>0;i--)Delete(h,i);
}

//输出数组
template <typename T>
void Print(T h[]){
    for(int i=0;i<n;i++)cout<<h[i]<<" ";
    cout<<endl<<"====================="<<endl;
}
int main()
{
    int a[6]={1,4,5,3,2,8};
    double d[6]={1.4,4.3,2.5,3.7,9.2,0.8};
    char c[6]={'c','d','r','a','y','b'};
    string s[6]={"hello","yes","byebye","welcome","good","morning"};
	
	//排序
    heapSort(a);
    heapSort(d);
    heapSort(c);
    heapSort(s);

    cout << endl<<"排序结果：" << endl;
    cout << "======================"<<endl;

    Print(a);
    Print(d);
    Print(c);
    Print(s);

    return 0;
}

运行结果

运行结果

总结

听说了函数模板这种东西之后，才惊觉stl库中的那些函数是通过这样的泛型编程实现的。
不过函数模板需要每个函数前都来那么一句，稍微有那么一点不是很舒服。
C++函数对于参数的灵活性调用也让我大吃一惊，虽然在此次实验中并没有体现到。