堆排序

堆排序(Heapsort)是利用堆这种数据结构的排序算法。堆是一个近似完全二叉树的结构。

  堆的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆节点的访问

通常堆是通过一维数组来实现的。在起始数组为 0 的情形中:

  • 堆的根节点(即堆积树的最大值)存放在数组位置 1 的地方;

  注意:不使用位置 0,否则左子树永远为 0[2]

  • 父节点i的左子节点在位置 (2*i);
  • 父节点i的右子节点在位置 (2*i+1);
  • 子节点i的父节点在位置 floor(i/2);

堆的操作

在堆的数据结构中,堆中的最大值总是位于根节点。堆中定义以下几种操作:

  • 最大堆调整(Max_Heapify):将堆的末端子结点作调整,使得子结点永远小于父结点
  • 创建最大堆(Build_Max_Heap):将堆所有数据重新排序
  • 堆排序(HeapSort):移除位在第一个数据的根结点,并做最大堆调整的递归运算

数组堆积排序

堆排序
 1 #include<iostream>
 2 using namespace std;
 3 
 4 //筛选法
 5 void sift(int E[],int j,int length)
 6 {
 7     int i=j;
 8     int c = 2*i+1;//数据从0开始
 9 
10     while(c < length)
11     {
12         if((c+1<length)&&(E[c]<E[c+1]))//左孩子<右孩子 时,取大的(右孩子)
13             c++;
14         if(E[i]>E[c]) 
15             break;//此节点数据已经比孩子节点数据大 则停止循环
16         else
17         {
18             int t=E[i];
19             E[i]=E[c];
20             E[c]=t;
21 
22             i=c;//继续重复上述操作,直到孩子节点小于此节点或到数的最后一层
23             c = 2*i+1;
24         }
25     }
26 }
27 //堆排序
28 void HeapSort(int E[],int n)//第二个参数是数组长度
29 {
30     //初始化堆
31     for(int i=n/2;i>=0;i--)//i=n/2是从倒数第二行开始
32         sift(E,i,n);
33 
34     for(int i=0;i<n;i++)//所有的元素
35     {
36         //数组的0号位置与堆内剩余的数据中最后一个交换位置
37         int t=E[n-i-1];
38         E[n-i-1]=E[0];
39         E[0]=t;
40 
41         sift(E,0,n-i-1);//每次都是数组的0号位置
42     }
43 }
44 
45 int main()
46 {
47     int E[]={3, 5, 3, 6, 4, 7, 5, 7, 4};
48     cout<<"原始序列:"<<endl;
49     for(int i=0;i<sizeof(E)/sizeof(int);i++)
50         cout<<E[i]<<" ";
51     cout<<endl;
52 
53     HeapSort(E,sizeof(E)/sizeof(*E));
54 
55     cout<<"堆排序后的序列:"<<endl;
56     for(int i=0;i<sizeof(E)/sizeof(int);i++)
57         cout<<E[i]<<" ";
58     cout<<endl;
59 
60     return 0;
61 }
堆排序

 本文转自cococo点点博客园博客,原文链接:http://www.cnblogs.com/coder2012/archive/2012/10/09/2717314.html,如需转载请自行联系原作者

上一篇:Nginx模块之Nginx-Ts-Module学习笔记(一)抢险体验


下一篇:转:用GDB调试程序(二)