当前位置:  编程技术>c/c++/嵌入式

内部排序之堆排序的实现详解

    来源: 互联网  发布时间:2014-10-15

    本文导语:  堆排序(Heap Sort)只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。(1)基本概念a)堆:设有n个元素的序列:{k1, k2, ..., kn}对所有的i=1,2,...,(int)(n/2),当满足下面关系:                    ...

堆排序(Heap Sort)只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。
(1)基本概念
a)堆:设有n个元素的序列:
{k1, k2, ..., kn}
对所有的i=1,2,...,(int)(n/2),当满足下面关系:
                                                                  ki≤k2i,ki≤k2i+1
                                                  或            ki≥k2i,ki≥k2i+1
这样的序列称为堆。
堆的两种类型:
   根结点最小的堆----小根堆。
   根结点最大的堆----大根堆。
根结点称为堆顶,即:在一棵完全二叉树中,所有非叶结点的值均小于(或均大于)左、右孩子的值。
b)堆排序:是一种树型选择排序,特点是,在排序过程中,把R[1..n]看成是一个完全二叉树的存储结构,利用完全二叉树双亲结点和孩子结点的内在关系,在当前无序区中选择关键字最大(最小)的记录。
2)堆排序步骤:
1、从k-1层的最右非叶结点开始,使关键字值大(或小)的记录逐步向二叉树的上层移动,最大(或小)关键字记录成为树的根结点,使其成为堆。
2、逐步输出根结点,令r[1]=r[i](i=n,,n-1,...,2),在将剩余结点调整成堆。直到输出所有结点。我们称这个自堆顶到叶子的调整过程为“筛选”。
(3)要解决的两个问题:
1、如何由一个无序序列建成一个堆;
2、输出一个根结点后,如何将剩余元素调整成一个堆。
将一个无序序列建成一个堆是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树,则最后一个非终端结点是第floor(n/2)个元素,由此“筛选”只需从第floor(n/2)个元素开始。
堆排序中需一个记录大小的辅助空间,每个待排的记录仅占有一个存储空间。堆排序方法当记录较少时,不值得提倡。当n很大时,效率很高。堆排序是不稳定的。
堆排序的算法和筛选的算法如第二节所示。为使排序结果是非递减有序排列,我们在排序算法中先建一个“大顶堆”,即先选得一个关键字为最大的记录并与序列中最后一个记录交换,然后对序列中前n-1个记录进行筛选,重新将它调整为一个“大顶堆”,然后将选得的一个关键字为最大的记录(也就是第一个元素)与当前最后一个记录交换(全局看是第n-1个),如此往复,直到排序结束。由到,筛选应按关键字较大的孩子结点向下进行。
堆排序的算法描述如下: 

 

用C语言代码实现如下:
代码如下:

#include "iostream"
using namespace std;
#define MAXSIZE 20
typedef struct
{
 int key;
 //其他数据信息
}RedType;
typedef struct
{
 RedType r[MAXSIZE+1];
 int length;
}Sqlist;
typedef Sqlist HeapType;  //堆采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m)   //已知H.r[s...m]中记录的关键字出H.r[s].key之外均满足堆的定义,本函数调整H.r[s]的关键字,使H.r[s...m]成为一个大顶堆(对其中记录的关键字而言)
{
 int j;
 RedType rc;
 rc=H.r[s];
 for(j=2*s;j1;--i)
 {
  H.r[0]=H.r[1];   //将堆顶记录和当前未经排序的子序列H.r[1...i]中最后一个记录相互交换
  H.r[1]=H.r[i];
  H.r[i]=H.r[0];
  HeapAdjust(H,1,i-1);    //将H.r[1...i-1]重新调整为大顶堆
 }
}//HeapSort
void InputL(Sqlist &L)
{
 int i;
 printf("Please input the length:");
 scanf("%d",&L.length);
 printf("Please input the data needed to sort:n");
 for(i=1;i

    
 
 

您可能感兴趣的文章:

  • java map(HashMap TreeMap)用法:初始化,遍历和排序详解
  • oracle指定排序的方法详解
  • linux下top命令详解包括top命令参数使用及结果(virt,res,shr)排序举例说明
  • 深入Java冒泡排序与选择排序的区别详解
  • 深入IComparable与IComparer的排序实例详解
  • 快速排序的深入详解以及java实现
  • ASP.NET4 GridView的四种排序样式详解
  • C++实现数组的排序/插入重新排序/以及逆置操作详解
  • java如何对map进行排序详解(map集合的使用)
  • C语言实现排序算法之归并排序详解
  • C++快速排序的分析与优化详解
  • C++实现基数排序的方法详解
  • 深入单链表的快速排序详解
  • 解决JTable排序问题的方法详解
  • jquery 表格排序实例详解
  • PHP快速排序小例子 php快速排序实现方法
  • python 算法 排序实现快速排序
  • VC++实现选择排序算法简单示例
  • C++实现顺序排序算法简单示例代码
  • mysql中文排序注意事项与实现方法
  • php冒泡排序算法实现代码
  • php选择排序算法实现代码
  • oracel如何实现字段的自动排序,问题解决多给分
  • Collections.sort()方法,已经实现Comparable接口,为什么无法将Vector排序?
  • C#实现Datatable排序的方法
  • c# n个数排序实现代码
  • Java实现按中文首字母排序的具体实例
  • python 实现插入排序算法
  • oracle指定排序的方法详解 iis7站长之家
  • 单向链表能否用快速排序??如果能如何实现??
  • C经典冒泡排序法实现代码
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • C++ Lists(链表) 成员 sort():给list排序
  • Java中的数组排序方式(快速排序、冒泡排序、选择排序)
  • STL vector+sort排序和multiset/multimap排序比较
  • 排序算法之PHP版快速排序、冒泡排序
  • <<大话数据结构>>中冒泡排序算法改进
  • php排序算法 PHP版快速排序与冒泡排序
  • java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)
  • 问题:DefaulTableModel是否有排序的功能,如果没有,jTable如何排序,我是从XML取数据到Table里。
  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
  • C#排序算法之快速排序
  • 数据库查询排序使用随机排序结果示例(Oracle/MySQL/MS SQL Server)
  • python算法学习之桶排序算法实例(分块排序)
  • python计数排序和基数排序算法实例
  • C#中使用快速排序按文件创建时间将文件排序的源码
  • 用c语言实现冒泡排序,选择排序,快速排序
  • 常用排序算法整理分享(快速排序算法、希尔排序)
  • php数组随机排序示例
  • jQuery表格排序插件 tablesorter
  • 可视化算法排序过程 Sound of Sorting
  • jQuery排序工具 jQuery.sorted
  • 关于awk数组的排序




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3