堆排序:一种基于堆的排序算法;
一些基础概念
堆定义:
当且仅当该序列满足如下性质(简称为堆性质):
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) //ki相当于二叉树的非叶结点,K2i则是左孩子,k2i+1是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:
树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
下图为数组对应的大根堆和小根堆。
堆的高度:
堆可以被看成是一棵树,结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目;定义堆的高度为树根的高度。我们将看到,堆结构上的一些基本操作的运行时间至多是与树的高度成正比,为O(lgn)
大根堆的堆排序思想:
1) 初始化R[1…n]为大根堆,该堆为无序的;
2) 交换R[1]和R[n],R[1…n-1]为无序的,R[n]为有序的;
3) 初始化R[1…n-1]为大根堆;
4) 交换R[1]和R[n-1],R[1…n-2]为无序的,R[n-1…n]为有序的;
依次重复,知道排好序为止。
算法如下:
/**
* 建立堆
* heap为需要建堆的数组,
* root建堆的起始根
* index为未排序的最后叶子节点
*/
private static void createHeap(int[] heap, int root, int index) {
int left;
int right;
int tmp;
if(root>=index){
return ;
}
while (root >= 0) {
left = root << 1;
right = (root << 1) + 1;
if (right <= index) {
if (heap[root] < heap[right]) {
tmp=heap[root];
heap[root]= heap[right];
heap[right]=tmp;
createHeap(heap, right, index);
}
}
if (left <= index) {
if (heap[root] < heap[left]) {
tmp=heap[root];
heap[root]= heap[left];
heap[left]=tmp;
createHeap(heap, left, index);
}
}
root--;
}
}
public static void heapSort(int[]heap, int index) {
int i, j, Temp;
// 将二叉树转成Heap
for (i = (index / 2); i >= 1; i--)
createHeap(heap,i, index);
// 开始进行堆排序
for (i = index ; i >= 1; i--) {
Temp = heap[i]; // Heap的Root值和最后一个值交换
heap[i] = heap[0];
heap[0] = Temp;
createHeap(heap,0, i-1); // 对其余数值重建堆
System.out.print("排序中: ");
for (j = 0; j <= index; j++)
System.out.printf("%3s", heap[j]);
System.out.println("");
}
}
分享到:
相关推荐
《计算机程序设计艺术》-第1卷-基本算法(第3版)-中文版 《计算机程序设计艺术》-第2卷-半数值算法(第3版)-中文版 《计算机程序设计艺术》-第3卷-排序与查找(第2版)-中文版
计算机程序设计艺术-第3卷-排序与查找(第2版)-中文版.pdf
计算机程序设计艺术-第3卷-排序与查找(第2版)-part-2-中文版.pdf
计算机程序设计艺术-第3卷-排序与查找(第2版)-part-1-中文版.pdf
三卷中文名为《基本算法》 《半数值算法》及《排序与查找》 本书内容博大精深 作者因为三卷书获得美国计算机协会1974年图灵奖(该奖被国际公认为计算机科学领域的最高奖项) ">《计算机程序设计艺术》重译自Donald E...
三卷中文名为《基本算法》 《半数值算法》及《排序与查找》 本书内容博大精深 作者因为三卷书获得美国计算机协会1974年图灵奖(该奖被国际公认为计算机科学领域的最高奖项) ">《计算机程序设计艺术》重译自Donald E...
计算机程序设计艺术+第3卷:排序与查找(第二版)高清中文版
《计算机程序设计艺术》-第1卷-基本算法(第3版)-中文版 《计算机程序设计艺术》-第2卷-半数值算法(第3版)-中文版 《计算机程序设计艺术》-第3卷-排序与查找(第2版)-中文版
共四部分: 计算机程序设计艺术(第一卷)基本算法.rar 计算机程序设计艺术(第二卷)半数值算法.rar ...计算机程序设计艺术(第三卷)排序与查找.rar 计算机程序设计艺术(补充卷)英文版.rar
分“排序”和“查找”两章。详细评价了在这两方面的重要技术或算法,指出了使用各种技术的条件,理论与实践并重。
《计算机程序设计艺术》重译自Donald E. Knuth(汉名高德纳)的三卷著作:"The Art of Computer Programming: 1. Fundamental Algorithms; 2. Seminumerical Algorithms; 3. Sorting and Searching";三卷中文名为...
共四部分: 计算机程序设计艺术(第一卷)基本算法.rar 计算机程序设计艺术(第二卷)半数值算法.rar 计算机程序设计艺术(第三卷)排序与查找.rar 计算机程序设计艺术(补充卷)英文版.rar
计算机程序设计艺术 全三卷 高清 计算机程序设计艺术(第一卷) 基本算法 第3版.pdf 计算机程序设计艺术(第二卷) 半数值算法 第3版.pdf 计算机程序设计艺术(第三卷)排序与查找 第2版.pdf
《计算机程序设计艺术》1,2,3卷--中文PDF电子书 英文书名《The Art Of Computer Programming》 第3版 Addison Wesley 国防工业出版社 Donald E.Knuth著 苏运霖译 第一卷 基本算法 。。。第1章 基本...
《计算机程序设计艺术》1,2,3卷--中文PDF电子书 英文书名《The Art Of Computer Programming》 第3版 Addison Wesley 国防工业出版社 Donald E.Knuth著 苏运霖译 第一卷 基本算法 。。。第1章 基本...
计算机程序设计艺术(第三版) 1-3卷. 第1卷-基本算法;第2卷-半数值算法;第3卷-排序与查找
大师Donald E. Knuth(汉名高德纳)的著作,计算机程序设计与艺术第三卷:排序与查找Sorting and Searching(中英)
算法-理论基础- 排序- 堆排序(包含源程序).rar
计算机程序设计艺术 第3卷:排序与查找(第二版)高清中文版
堆排序--大顶堆排序