堆排序的具体算法

分类: 电脑/网络 >>程序设计 >>其他编程语言

解析:

1、 堆排序定义

n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：

(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。

2、大根堆和小根堆

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。

注意：

①堆中任一子树亦是堆。

②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

3、堆排序特点

堆排序(HeapSort)是一树形选择排序。

堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。

4、堆排序与直接插入排序的区别

直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比如搜较结果，所以后一趟排序时又重复执行了这些比较 *** 作。

堆排序可通过树形结构保存部分比较结果，可减少比较次数。

5、堆排序

堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

（1）用大根堆排序的基本思想

① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区

② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的扮隐最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

……

直到无序区只有一个元素为止。

（2）大根堆排序算法的基本 *** 作：

① 初始化 *** 作：将R[1..n]构造为初始堆；

② 每一趟排序的基本 *** 作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。

注意：

①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。

②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整厅橡厅个向量为止。

（3）堆排序的算法：

void HeapSort(SeqIAst R)

{ 对R[1..n]进行堆排序，不妨用R[0]做暂存单元

int i；

BuildHeap(R)； 将R[1-n]建成初始堆

for(i=ni>1；i--){ 对当前无序区R[1..i]进行堆排序，共做n-1趟。

R[0]=R[1]；R[1]=R[i]R[i]=R[0]； 将堆顶和堆中最后一个记录交换

Heapify(R，1，i-1)； 将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质

} endfor

} HeapSort

（4） BuildHeap和Heapify函数的实现

因为构造初始堆必须使用到调整堆的 *** 作，先讨论Heapify的实现。

① Heapify函数思想方法

每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。

"筛选法"调整堆

R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。

具体的算法【参见教材】

②BuildHeap的实现

要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。

显然只有一个结点的树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为 ， -1，…，1的结点作为根的子树都调整为堆即可。

具体算法【参见教材】。

5、大根堆排序实例

对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况参见【动画演示】。

6、 算法分析

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1)，

它是不稳定的排序方法。

1，实用的排序算法：选择排序

（1）选择排序的基本思想是：每一趟（例如第i趟，i=0，1，2，3，……n-2）在后面n-i个待排序元素中选择排序码最小的元素，作为有序元素序列的第i个元素。待到第n-2趟做完，待排序元素只剩下一个，就不用再选了。

（2）三种常用的选择排序方法

1>直接选择排序

2>锦标赛排序

3>堆排序

其中，直接排序的思路和实现都比较简单，并且相比其他排序算法，直接选择排序有一个突出的优势——数据的移动次数少。

（3）直接选择排序简介

1>直接选择排序（select sort）是一种简单的排序方法，它的基本步骤是：

1）在一组元素V[i]~V[n-1]中选择具有最小排序码的元素；

2）若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素对调；

3）在这组元素中剔除这个具有最小排序码的元素，在剩下的元素V[i+1]~V[n-1]中重复执行1、2步骤，直到剩余元素只有一个为止。

2>直接选择排序使用注意

它对一类重要的元素序列具有较好的效率，这就是元素规模很大，而排序码却比较小的序列。因为对这种序列进行排序，移动 *** 作所花费的时间要比比较 *** 作的时间大的多，而其他算法移动 *** 作的次数都要比直接选择排序来的多，直接选择排序是一种不稳定的 排序方法。

3>直接选择排序C++函数代码

//函数功能，直接选择排序算法对数列排序

//函数参数，数列起点，数列终点

void dselect_sort(const int start, const int end) {

for (int i = starti <end++i) {

int min_position = i

for (int j = i + 1j <= end++j) {//此循环用来寻找最小关键码

if (numbers[j] <numbers[min_position]) {

min_position = j

}

}

if (min_position != i) {//避免自己与自己交换

swap(numbers[min_position], numbers[i])

（4）关于锦标赛排序

直接选择排序中，当n比较大时，排序码的比较次数相当多，这是因为在后一趟比较选择时，往往把前一趟已经做过的比较又重复了一遍，纯竖伏没有把前一趟的比较结果保留下来。

锦标赛排序（tournament sort）克服了这一缺点。它的思想与体育比赛类似，就是把待排序元素两两进行竞赛，选出其中的胜利者，之后胜利者之间继续竞赛纤仿，再选出其中的胜利者，然后重复这一过程，最终构造出胜者树，从而实现排序的目的。

2，堆排序的排序过程

（1）个人理解：堆排序是选择排序的一种，所以它也符合选择排序的整体思想。直接选择排序是在还未成序的元素中逐个比较选择，而堆排序是首先建立一个堆（最大堆或最小堆），这使得数列已经“大致”成序，之后只需要局部调整来重建堆即可。建立堆及重建堆这一过程映射到数组中，其实就是一个选择的过程，只不过不是逐个比较选择，而是借助完全二叉树来做到有目的的比较选择。这也是堆排序性能优于直接选择排序的一个体现。

（2）堆排序分为两个步骤：

1>根据初始输入数据，利用堆的调整算法形成初始堆；

2>通过一系列的元素交换和重新调整堆进行排序。

（3）堆排序的排序思路

1>前提，我们是要对n个数据进行递增排序，也就是说拥有最大排序码的元素应该在数组的末端。

2>首先建立一个最大堆，则堆的第一个元素heap[0]具有最大的排序码，将heap[0]与heap[n-1]对调，把具有最大排序码的元素交换到最后，再对前面n-1个元素，使用堆的调整算法siftDown(0,n-2)，重新建立最大堆。结果具有次最大排序码的元素又浮到堆顶，即heap[0]的位置，再对调heap[0]与heap[n-2]，并调用siftDown(0，n-3)，对前n-2个元素重新调整，……如此反复，最后得到一个数列的排序码递增序列。

（4）堆排序的排序过程：

下面给出局做携部调整成最大堆的函数实现siftDown()，这个函数在前面最小堆实现博文中的实现思路已经给出，只需做微小的调整即可用在这里建立最大堆。

初始堆： 49 a[1] 38 65 a[2]a[3] 97 76 13 27 a[4] a[5] a[6] a[7] 50 a[8]procedure heap(nn,ii:integer) var x,i,j:integer begin i:=iix:=a[ii]j:=2*iiwhile j<=nn dobeginif (j<nn) and(a[j]<a[j+1] then j:=j+1 if x<a[j] then begin a[i]:=a[j]i:=jj:=2*iendelse j:=nn+1 end end主程序：for i:=n div 2 downto 1 do heap(n,i) /heap相当于搜索顶点i的所有子念模搜节点，找出最大的和它替换for i:=n downto 2 do begintemp:=a[1]a[1]:=a[i]a[i]:=temp/将当前最大的数（放在a[1]）和第i个数交换，仔历保证从后面往前数是heap(i-1,1) 从大到小，则程序完成时，数组a从前往后是从小到码携大 end至于过程自己用笔算，很快就会明白，不明白算了就明白。

---