堆排序——C#实现一算法描述堆排序（Heap Sort）是利用一种被称作二叉堆的数据结构进行排序的排序算法。
二叉堆在内部维护一个数组，可被看成一棵近似的完全二叉树，树上每个节点对应数组中的一个元素。
除最底层外，该树是满的。
二叉堆中，有两个与所维护数组相关的属性。
Length表示数组的元素个数，而HeapSize则表示二叉堆中所维护的数组中的元素的个数（并不是数组中的所有元素都一定是二叉堆的有效元素）。
因此，根据上述定义有： 0 = HeapSize = Length。
二叉堆可分为最大堆和最小堆两种类型。
在最大堆中，二叉树上所有的节点都不大于其父节点，即 A[Parent(i)] = A[i]。
最小堆正好相反：A[Parent(i)] = A[i]。
为维护一个二叉堆是最大（小）堆，我们调用一个叫做MaxHeapify （MinHeapify）的过程。
以MaxHeapify，在调用MaxHeapify时，先假定根节点为Left(i)和Right(i)的二叉树都是最大堆，如果A[i]小于其子节点中元素，则交换A[i]和其子节点中的较大的元素。
但这样一来，以被交换的子节点为根元素的二叉堆有可能又不满足最大堆性质，此时则递归调用MaxHeapify方法，直到所有的子级二叉堆都满足最大堆性质。
如下图所示：因为在调用MaxHeapify（MinHeapify）方法使根节点为A[i]的二叉堆满足最大（小）堆性质时我们有其左右子堆均已满足最大（小）堆性质这个假设，所以如果我们在将一个待排序的数组构造成最大（小）堆时，需要自底向上地调用 MaxHeapify（MinHeapify）方法。
在利用最大堆进行排序时，我们先将待排序数组构造成一个最大堆，此时A[0]（根节点）则为数组中的最大元素，将A[0]与A[n - 1]交换，则把A[0]放到了最终正确的排序位置。
然后通过将HeapSize 减去1，将（交换后的）最后一个元素从堆中去掉。
Java实现堆排序（Heapsort）实例代码复制代码代码如下:import java.util.Arrays;public class HeapSort {public static void heapSort(DataWraper[] data){System.out.println("开始排序");int arrayLength=data.length;//循环建堆for(int i=0;i<arrayLength-1;i++){//建堆buildMaxHeap(data,arrayLength-1-i);//交换堆顶和最后⼀个元素swap(data,0,arrayLength-1-i);System.out.println(Arrays.toString(data));}}private static void swap(DataWraper[] data, int i, int j) {// TODO Auto-generated method stubDataWraper tmp=data[i];data[i]=data[j];data[j]=tmp;}//对data数组从0到lastIndex建⼤顶堆private static void buildMaxHeap(DataWraper[] data, int lastIndex) {// TODO Auto-generated method stub//从lastIndex处节点（最后⼀个节点）的⽗节点开始for(int i=(lastIndex-1)/2;i>=0;i--){//k保存正在判断的节点int k=i;//如果当前k节点的⼦节点存在while(k*2+1<=lastIndex){//k节点的左⼦节点的索引int biggerIndex=2*k+1;//如果biggerIndex⼩于lastIndex，即biggerIndex+1代表的k节点的右⼦节点存在if(biggerIndex<lastIndex){//若果右⼦节点的值较⼤if(data[biggerIndex].compareTo(data[biggerIndex+1])<0){//biggerIndex总是记录较⼤⼦节点的索引biggerIndex++;}}//如果k节点的值⼩于其较⼤的⼦节点的值if(data[k].compareTo(data[biggerIndex])<0){//交换他们swap(data,k,biggerIndex);//将biggerIndex赋予k，开始while循环的下⼀次循环，重新保证k节点的值⼤于其左右⼦节点的值 k=biggerIndex;}else{break;}}}}public static void main(String[] args) {// TODO Auto-generated method stubDataWraper [] data={new DataWraper(21, ""),new DataWraper(30, ""),new DataWraper(49, ""),new DataWraper(30, "*"),new DataWraper(16, ""),new DataWraper(9, ""),};System.out.println("排序之前：\n"+Arrays.toString(data)); heapSort(data);System.out.println("排序之后：\n"+Arrays.toString(data)); }}排序之前：[21, 30, 49, 30*, 16, 9]开始排序[9, 30, 21, 30*, 16, 49][16, 30*, 21, 9, 30, 49][9, 16, 21, 30*, 30, 49][9, 16, 21, 30*, 30, 49][9, 16, 21, 30*, 30, 49]排序之后：[9, 16, 21, 30*, 30, 49]。
自己写的堆排序算法。
1、程序结构如下：将main();函数中的init（）；diaplay（）；等函数编写到统一的tools.h文件中声明，tools.cpp，文件中实现。
更改了test文件，有错误的时候，输出错误位置，等待用户输入任意键。
在没有错误的情况下，输出无错信息。
2、heapsort函数中，有showtime（）功能，showtime（）函数也是在tools.h文件中声明，在tools.cpp文件中实现的。
可以在heapsort（）开始和结束时显示时间。
这样可准确测试排序所需的时间。
3此程序较之前写的快速排序有优势，由于没有递归调用，所以，可允许的数组程度大大增加。
目前测试长度为一千万的数组，排序时间为10秒，与快速排序相同，长度为一亿的数据，排序时间为2分钟45秒。
4、修改了数组长度的#define LEN 100000000为int len=100000000;这有很大的意义，也就是说数组的长度可以动态的获得，可以用户输入，从文件中读取等等，从网络中获得，从数据库中获得等等，同时也就说明了，数据可以有很多方式获得，不仅仅是我们随机产生，就是说这个软件只要稍加修改就能处理我们的实用数据了。
程序源代码如下：//***********************************************************************//main.cpp//作者：孙某，QQ1214414962//***********************************************************************#include <cstdio>#include <cstdlib>#include<iostream>#include "tools.h"#include "heapsort.h"using namespace std;void main(){ const int len=100000000;int *a=new int[len];init(a,len);printf("the original series...\n");display(a,len);heapsort(a,len);test(a,len);printf("the series after sorts...\n");display(a,len);getchar();delete a;}//**********************************************************************//tools.h//**********************************************************************#ifndef TOOLS_H#define TOOLS_Hvoid init(int *a,int len);void display(int a[],int len);void test(int a[],int len);void showtime();#endif//********************************************************************* //tools.cpp//******************************************************************** #include <cstdio>#include <cstdlib>#include<iostream>#include<ctime>#include"tools.h"using namespace std;void init(int *a,int len){ int i;for(i=0;i<len;i++){a[i]=rand();}}void display(int a[],int len){int i;for(i=0;i<len&&i<100;i++){if(i!=0&&i%10==0){printf("\n");}printf("%6d",a[i]);printf(" ");}printf("\n");if(len>100){printf("this series is too long,totally %d numbers\n",len);printf("Now display the last 100 numbers..........");for(i=len-100;i<len;i++){ if(i%10==0){printf("\n");}printf("%6d",a[i]);printf(" ");}}printf("\n");}void test(int a[],int len){int i;int flag=0;printf("this is the test to show if there is any wrong sorts...\n");for(i=0;i<len-1;i++){if(a[i]>a[i+1]){ flag=1;printf("qiuck sort is wrong at location :%d\n",i);printf("a[%d]:%d\na[%d]:%d",i,a[i],i+1,a[i+1]);getchar();}}if(flag=0){printf("there is nothing wrong ,it is a prefect series\n");}}void showtime(){time_t now_time;now_time = time(NULL);struct tm now = *localtime(&now_time);cout<<now.tm_hour<<":"<<now.tm_min<<":"<<now.tm_sec;}//********************************************************** //heapsort.h//********************************************************** #ifndef HEAPSORT_H#define HEAPSORT_Hvoid heapsort(int *a,int len);#endif//******************************************************** //haapsort.cpp//******************************************************** #include<iostream>#include "heapsort.h"#include"tools.h"using namespace std;void swap(int &num1,int &num2);void maxheapadjust(int *a,int ls);void minheapadjust(int *a,int ls);void heapadd(int *a, int i);void heapfixdown(int *a,int i,int len);void heapsort(int *a,int len){ cout<<"heapsort begins at:";showtime();cout<<endl;maxheapadjust(a,0);for(int i=3;i<len;i++){heapadd(a,i);}for(int i=len;i>0;i--){swap(a[i-1],a[0]);heapfixdown(a,0,i-2);}minheapadjust(a,0);cout<<"heapsort finishs at:";showtime();cout<<endl;}void maxheapadjust(int *a,int ls){if(a[ls]<a[2*ls+1])swap(a[ls],a[2*ls+1]);}if(a[ls]<a[2*ls+2]){swap(a[ls],a[2*ls+2]);}}void minheapadjust(int *a,int ls){if(a[ls]>a[2*ls+1]){swap(a[ls],a[2*ls+1]);}if(a[ls]>a[2*ls+2]){swap(a[ls],a[2*ls+2]);}if(a[2*ls+1]>a[2*ls+2]){swap(a[2*ls+1],a[2*ls+2]);}}void swap(int &num1,int &num2){int temp=num1;num1=num2;num2=temp;}void heapadd(int *a, int i){for(int j=(i-1)/2;j>=0&&a[i]>a[j]; j=(i-1)/2) {swap(a[i], a[j]);i=j;}}void heapfixdown(int *a, int i,int len)int j, temp;temp = a[i];j = 2 * i + 1;while (j < len){if (j + 1 < len && a[j + 1] > a[j]) //在左右孩子中找最小的j++;if (a[j] <= temp)break;a[i] = a[j]; //把较小的子结点往上移动,替换它的父结点i = j;j = 2 * i + 1;}a[i] = temp;}。
数据结构实验报告本文是范文，仅供参考写作，禁止抄袭本文内容上传提交，违者取消写作资格，成绩不合格！实验名称：排序算法比较提交文档学生姓名：提交文档学生学号：同组成员名单：指导教师姓名：排序算法比较一、实验目的和要求1、设计目的1．掌握各种排序的基本思想。
2．掌握各种排序方法的算法实现。
3．掌握各种排序方法的优劣分析及花费的时间的计算。
4．掌握各种排序方法所适应的不同场合。
2、设计内容和要求利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间二、运行环境（软、硬件环境）软件环境：Vc6.0编程软件运行平台： Win32硬件：普通个人pc机三、算法设计的思想1、冒泡排序：bubbleSort()基本思想: 设待排序的文件为r[1..n]第1趟(遍)：从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录r[i]和r[i+1]的位置；否则,不交换。
(i=1,2,...n-1)第1趟之后,n个关键字中最大的记录移到了r[n]的位置上。
第2趟：从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录r[i]和r[i+1]的位置；否则,不交换。
(i=1,2,...n-2)第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位置上，作完n-1趟,或者不需再交换记录时为止。
2、选择排序：selSort()每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从array[k]开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比array[k-1]更小的元素，则把array[minlIndex]和a[k-1]对调，这时array[k]到最后一个元素中最小的元素就换到了array[k-1]的位置。
