首页 > 代码库 > 处理海量数据的三大排序之——堆排序（C++）
处理海量数据的三大排序之——堆排序（C++）
在面对大数据量的排序时（100W以上量级数据），通常用以下三种的排序方法：快速排序、归并排序，堆排序。在这个量级上，其他冒泡，选择，插入排序等已经根本没法看了，效率极低，跟前面三种排序差了千百倍，因此不作比较。
这三种排序的平均时间复杂度均为O(nlogn)，快速排序，归并排序在面对基本有序序列排序时，效率反会降低。且归并排序需要用到O(n)的临时存储空间。而堆排序没有明显缺点，特别在面对经常会插入新元素的排序需求，堆排序效果最好。
下面是三种排序对100W个无序数组进行排序的时间对比，可以看出在平均情况下，时间效率：快排>归并>堆排序
基础概念
什么是堆？
堆：一种数据结构，全称为：二叉堆数据结构，是一种数组对象。
当所有节点都大于各自左右子节点时，叫大顶堆；
当所有节点都小于各自左右子节点时，叫小顶堆。
在堆排序中，使用大顶堆结构。
排序原理
若输出堆顶的最大值之后，使得剩余n-1个元素的序列重新又建成一个堆，则得到n个元素中个次大值。如此反复执行，便能得到一个有序序列，这个过程就称之为堆排序。
因此堆排序的实现思路，可以细分为两部分：
1、如何将一个无序数组排列成大顶堆（建堆过程）
2、拿走最大值后如何从剩下的堆中找出次大值，重新建立大顶堆（筛选过程）
时间复杂度
堆排序可分细分为两部分：建堆过程+排序过程。
建堆过程时间复杂度为O(n)，即将一个无序数组建立成堆只需要线性时间。
排序过程需要对n个数据进行筛选时，每次筛选需要O(logn)时间，所以整个排序过程的时间为O(nlogn)
因此堆排序总的运行时间为： O(nlogn) = O(n) + O(nlogn)
算法实现
#include "stdafx.h"#include <iostream>#include <ctime>using namespace std;int a[1000000];#define BEGIN_RECORD \{ clock_t ____temp_begin_time___; ____temp_begin_time___=clock();#define END_RECORD(dtime) \dtime=float(clock()-____temp_begin_time___)/CLOCKS_PER_SEC;}/* 目标：筛选区域为以索引i为树根的子树，找出该子树最大值，将其存放到索引i 过程：从索引为i的结点开始往下，与较大的子节点交换值，向下搜索直到子树底部 a - 待排序数组 i - 筛选起始结点索引 len - 排序元素数量*/void sift(int a[], int i, int len) { int temp = a[i]; int j = 2 * i; while(j <= len) { if(j < len && a[j] < a[j+1]) //如果右结点比左结点大，则拿右结点跟父节点比较 j++; if(a[i] < a[j]) //如果子节点比父节点大，则两者交换值，子节点成为新的父节点，继续向下筛选 { a[i] = a[j]; a[j] = temp; i = j; j = 2 * i; } else //如果父节点比子节点大，则说明找到了该子树的最大值，结束筛选 { break; } } a[i] = temp;}/*堆排序（大顶堆）a - 待排序的数组len - 数组长度*/void heapSort(int a[], int len){ int temp; int i; for (i = len-1; i > 0; i--) //堆排序只能从下标为1开始排序，因此要把数组所有数据后一移位。下标0的数据不处理 { a[i] = a[i - 1]; } for (i = len/2; i >= 1; i--) //建堆过程（使得全树的父节点都比子节点大） { sift(a, i, len); } for (i = len - 1; i >= 2; i--) //排序过程：每次从树根取值（该值必为最大值），放到树的最后一个结点n，并把该结点从树中移除。重复排序过程，直到将所有结点从树移除，排序结束 { temp = a[1]; a[1] = a[i]; a[i] = temp; sift(a, 1, i - 1); //从树根取出最大值，取最尾树结点放到树根，此时树根不再为最大值，需要再对树根进行一次筛选过程，以确保树根仍然为最大值 }}void printArray(int a[], int length){ cout << "数组内容："; for(int i = 0; i < length; i++) { if(i == 0) cout << a[i]; else cout << "," << a[i]; } cout << endl;}int _tmain(int argc, _TCHAR* argv[]){ float tim; BEGIN_RECORD //int a[1000000]; for (int i = 0; i < 1000000; i++) { a[i] = int(rand() % 100000); } //printArray(a, sizeof(a)/sizeof(int)); heapSort(a, sizeof(a)/sizeof(int)); //printArray(a, sizeof(a)/sizeof(int)); END_RECORD(tim) cout << "运行时间：" << tim << "s" << endl; system("pause"); return 0;}