堆排序算法
首先介绍一下什么是堆,这里所说的堆其实是二叉堆。二叉堆是完全二叉树的应用,此外二叉堆又分为最小和最大二叉堆之分。最小二叉堆满足父节点的值小于儿子节点的值(除根节点外,因为根节点没有父节点)。很明显,说道这里最大二叉堆大家也就知道了,就不再叙述。
堆排序分为两个阶段:第一个阶段就是构建一个最小或者最大二叉堆。第二阶段就是采用选择排序的思想,将根节点交换到后面,再将其余的节点进行调整,成为新的二叉堆,重复进行,直到排序完成。下面将为大家展示如何用堆排序输出降序排列的序列。
按降序排列
package com.heapsort.yy;
/**
* 堆排序算法
*@author yuyang_csu
*@data 2013-4-6
*/
public class HeapSort {
//声明待排序的数组
private int arr[];
//重载构造函数
public HeapSort(int arr[]){
this.arr = arr;
}
//创建交换数组中两个元素的方法
public void swap(int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
* 建立最小堆得方法
* @param arr:待排序数组
* @param lastindex:待排序数组的长度
*/
public void buildMinHeap(int [] arr,int lastindex){
//从最后一个元素的父节点开始构建堆
for(int root = lastindex-1/2;root>=0;root--){
int left = root*2+1;
//若当前节点存在子节点
while(left<arr.length){
//若当前节点存在右结点时,返回儿子节点中元素较小的节点
if(left!=lastindex-1 && arr[left]>arr[left+1]){
left++;
}
if(arr[root]>arr[left]){
swap(root,left);
}else{
break;
}
left = left*2+1;
}
}
}
//构建堆排序的方法
public void heapSort(){
for(int i = arr.length;i>0;i--){
buildMinHeap(arr,i);
if(0==i-1){
swap(0,i-1);
}
}
}
//显示数组的方法
public void display(){
for(int i = 0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
public static void main(String[] args) {
int [] arr = {31,41,59,26,53,58,97};
HeapSort hs = new HeapSort(arr);
hs.heapSort();
hs.display();
}
}
按升序排列
public class HeapSort {
//待排序的数组
private int arr[];
//重载构造器
public HeapSort(int[] arr) {
this.arr = arr;
}
//交换数组两个元素的方法
public void swap(int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
//堆排序方法
public void heapSort(int lastindex){
//循环实现
// while(lastindex>=0){
// sort(lastindex);
// swap(0,lastindex);
// lastindex--;
// }
//递归实现
if(lastindex>=0){
sort(lastindex);
swap(0,lastindex);
//注意可以写成--lastindex或者lastindex-1,不能写成lastindex--
heapSort(--lastindex);
}
}
//创建最大堆得方法
public void sort(int lastindex) {
// 重最后一个节点的父节点开始遍历
for (int i = (lastindex-1)/2; i >= 0; i--) {
//声明左节点下标
int left = 2 * i + 1;
// 当节点有子节点的时候
while (left <= lastindex) {
// 当有右子节点的时候,返回儿子节点中元素较大的节点的下标
if (left != lastindex && arr[left] < arr[left+1]){
left++;
}
// 当父节点小于子节点中较大时,下滤
if (arr[i] < arr[left]) {
swap(i, left);
left = left * 2 + 1;
}else{
break;
}
}
}
}
//显示数组的方法
public void display() {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
//主函数
public static void main(String[] args) {
int arr[] = { 1, 4, 7, 9, 2, 7, 3, 5 };
HeapSort t = new HeapSort(arr);
t.heapSort(arr.length-1);
t.display();
}
}
堆排序的时间复杂度:将一个序列调整为堆的时间复杂度为O(logN),因此堆排序的时间复杂度为O(NlogN)。
堆排序稳定性分析: 我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法
分享到:
相关推荐
1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
堆排序的c++实现代码
堆排序的源代码; 平台:openSUSE 11.4 编译器:GCC version 4.5.1
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...
用函数实现堆排序,并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 第一行:初始建堆后的结果 其后各行输出交换堆顶元素并调整堆的结果,数据...
上课的算法设计实验,内容有堆排序等一些内容!的代码 上课的算法设计实验,内容有堆排序等一些内容!的代码 上课的算法设计实验,内容有堆排序等一些内容!的代码
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构试验堆排序MFC // HeapSortDlg.h : header file // #if !defined(AFX_HEAPSORTDLG_H__DA227A0F_D8D2_459E_A6AE_1F11F292DDDD__INCLUDED_) #define AFX_HEAPSORTDLG_H__DA227A0F_D8D2_459E_A6AE_1F11F292...
关于堆排序,里面有关于堆排序的练习台里面有关于堆排序的练习台里面有关于堆排序的练习台里面有关于堆排序的练习台里面有关于堆排序的练习台里面有关于堆排序的练习台
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
对堆排序的改进 1.将数据初始化为大顶堆,交换第一个和最后一个元素,这里是不变的 2.重新构造大顶堆是,首先让第一个元素下降h/2的高度(h 为堆的高度) 3.下降了h/2层后判断这个元素与它的父节点谁大,如果父...
这是一个用C++编写的简单学生成绩管理系统,其中实现学生成绩的最大最小堆排序,程序已经过测试!
// 堆排序 #include typedef int InfoType; // 定义其它数据项的类型 #include "compare.h" #include "sort.h" typedef SqList HeapType; // 堆采用顺序表存储表示 void HeapAdjust(HeapType &H,int s,int m) // ...
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
算法 堆的创建与堆排序 堆的创建与堆排序
ACM准备模板 堆排序模板 acm 堆 排序