详解堆排序算法原理及Java版的代码实现

网友投稿 171 2023-07-14


详解堆排序算法原理及Java版的代码实现

概述

堆排序是一种树形选择排序,是对直接选择排序的有效改进。

堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足:

时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆)。

若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。

(a)大顶堆序列:(96, 83, 27, 38, 11, 09)

(b)小顶堆序列:(12, 36, 24, 85, 47, 30, 53, 91)

初始时把要排序的n 个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素。然后对剩下的n-1个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到最后得到有n个节点的有序序列。称这个过程为堆排序。

步骤&实例

实现堆排序需解决两个问题:

(1)如何将n 个待排序的数建成堆;

(2)输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。

建堆方法(小顶堆):

对初始序列建堆的过程,就是一个反复进行筛选的过程。

n 个结点的完全二叉树,则最后一个结点是第n/2个结点的子树。

筛选从第n/2个结点为根的子树开始(n/2是最后一个有子树的结点),使该子树成为堆。

之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

如图建堆初始过程

无序序列:(49, 38, 65, 97, 76, 13, 27, 49)

(a) 无序序列,初始二叉树,97(第8/2=4个结点)为最后一个结点(49)的父结点。

(b) 97>=49,替换位置,接下来对n/2的上一个结点65进行筛选。

(c) 13<=27且65>=13,替换65和13的位置,接下来对38进行替换(都大于它,不需操作),对49进行筛选。

(d) 13<=38且49>=13,替换49和13的位置,49>=27,替换49和27的位置。

(e) 最终得到一个堆,13是我们得到的最小数。

调整堆的方法(小顶堆):

设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶,堆被破坏,其原因仅是根结点不满足堆的性质。

将根结点与左、右子树中较小元素的进行交换。

若与左子树交换:如果左子树堆被破坏,则重复方法(2).

若与右子树交换,如果右子树堆被破坏,则重复方法(2).

继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

调整堆只需考虑被破坏的结点,其他的结点不需调整。

代码实现(java)

运行代码结合注释与上面的实例步骤进行对比思考。

package com.coder4j.main;

public class HeapSort {

/**

* 调整为小顶堆(排序后结果为从大到小)

*

* @param array是待调整的堆数组

* @param s是待调整的数组元素的位置

* @param length是数组的长度

*

*/

public static void heapAdjustS(int[] array, int s, int length) {

int tmp = array[s];

int child = 2 * s + 1;// 左孩子结点的位置

System.out.println("待调整结点为:array[" + s + "] = " + tmp);

while (child < length) {

// child + 1 是当前调整结点的右孩子

// 如果有右孩子且小于左孩子,使用右孩子与结点进行比较,否则使用左孩子

if (child + 1 < length && array[child] > array[child + 1]) {

child++;

}

System.out.println("将与子孩子 array[" + child + "] = " + array[child] + " 进行比较");

// 如果较小的子孩子比此结点小

if (array[s] > array[child]) {

System.out.println("子孩子比其小,交换位置");

array[s] = array[child];// 把较小的子孩子向上移动,替换当前待调整结点

s = child;// 待调整结点移动到较小子孩子原来的位置

array[child] = tmp;

child = 2 * s + 1;// 继续判断待调整结点是否需要继续调整

if (child >= length) {

System.out.println("没有子孩子了,调整结束");

} else {

System.out.println("继续与新的子孩子进行比较");

}

// continue;

} else {

System.out.println("子孩子均比其大,调整结束");

break;// 当前待调整结点小于它的左右孩子,不需调整,直接退出

}

}

}

/**

* 调整为大顶堆(排序后结果为从小到大)

*

* @param array是待调整的堆数组

* @param s是待调整的数组元素的位置

* @param length是数组的长度

*

*/

public static void heapAdjustB(int[] array, int s, int length) {

int tmp = array[s];

int child = 2 * s + 1;// 左孩子结点的位置

System.out.println("待调整结点为:array[" + s + "] = " + tmp);

while (child < length) {

// child + 1 是当前调整结点的右孩子

// 如果有右孩子且大于左孩子,使用右孩子与结点进行比较,否则使用左孩子

if (child + 1 < length && array[child] < array[child + 1]) {

child++;

}

System.out.println("将与子孩子 array[" + child + "] = " + array[child] + " 进行比较");

// 如果较大的子孩子比此结点大

if (array[s] < array[child]) {

System.out.println("子孩子比其大,交换位置");

array[s] = array[child];// 把较大的子孩子向上移动,替换当前待调整结点

s = child;// 待调整结点移动到较大子孩子原来的位置

array[child] = tmp;

child = 2 * s + 1;// 继续判断待调整结点是否需要继续调整

if (child >= length) {

System.out.println("没有子孩子了,调整结束");

} else {

System.out.println("继续与新的子孩子进行比较");

}

// continue;

} else {

System.out.println("子孩子均比其小,调整结束");

break;// 当前待调整结点大于它的左右孩子,不需调整,直接退出

}

}

}

/**

* 堆排序算法

*

* @param array

* @param inverse true 为倒序排列,false 为正序排列

*/

public static void heapSort(int[] array, boolean inverse) {

// 初始堆

// 最后一个有孩子的结点位置 i = (length - 1) / 2, 以此向上调整各结点使其符合堆

System.out.println("初始堆开始");

for (int i = (array.length - 1) / 2; i >= 0; i--) {

if (inverse) {

heapAdjustS(array, i, array.length);

} else {

heapAdjustB(array, i, array.length);

}

}

System.out.println("初始堆结束");

for (int i = array.length - 1; i > 0; i--) {

// 交换堆顶元素H[0]和堆中最后一个元素

int tmp = array[i];

array[i] = array[0];

array[0] = tmp;

// 每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整

if (inverse) {

heapAdjustS(array, 0, i);

} else {

heapAdjustB(array, 0, i);

}

}

}

public static void main(String[] args) {

int[] array = { 49, 38, 65, 97, 76, 13, 27, 49 };

heapSort(array, false);

for (int i : array) {

System.out.print(i + " ");

}

}

}

运行结果:

初始堆开始

待调整结点为:array[3] = 97

将与子孩子 array[7] = 49 进行比较

子孩子比其小,交换位置

没有子孩子了,调整结束

待调整结点为:array[2] = 65

将与子孩子 array[5] = 13 进行比较

子孩子比其小,交换位置

没有子孩子了,调整结束

待调整结点为:array[1] = 38

将与子孩子 array[3] = 49 进行比较

子孩子均比其大,调整结束

待调整结点为:array[0] = 49

将与子孩子 array[2] = 13 进行比较

子孩子比其小,交换位置

继续与新的子孩子进行比较

将与子孩子 array[6] = 27 进行比较

子孩子比其小,交换位置

没有子孩子了,调整结束

初始堆结束

待调整结点为:array[0] = 97

将与子孩子 array[2] = 27 进行比较

子孩子比其小,交换位置

继续与新的子孩子进行比较

将与子孩子 array[6] = 49 进行比较

子孩子比其小,交换位置

没有子孩子了,调整结束

待调整结点为:array[0] = 97

将与子孩子 array[1] = 38 进行比较

子孩子比其小,交换位置

继续与新的子孩子进行比较

将与子孩子 array[3] = 49 进行比较

子孩子比其小,交换位置

没有子孩子了,调整结束

待调整结点为:array[0] = 65

将与子孩子 array[1] = 49 进行比较

子孩子比其小,交换位置

继续与新的子孩子进行比较

将与子孩子 array[4] = 76 进行比较

子孩子均比其大,调整结束

待调整结点为:array[0] = 76

将与子孩子 array[2] = 49 进行比较

子孩子比其小,交换位置

没有子孩子了,调整结束

待调整结点为:array[0] = 97

将与子孩子 array[1] = 65 进行比较

子孩子比其小,交换位置

没有子孩子了,调整结束

待调整结点为:array[0] = 76

将与子孩子 array[1] = 97 进行比较

子孩子均比其大,调整结束

待调整结点为:array[0] = 97

97 76 65 49 49 38 27 13

PS:堆排序与直接插入排序的区别

直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果,可减少比较次数。


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:使用Web Uploader实现多文件上传
下一篇:Eclipse常用快捷键总结(必看篇)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~