Java版堆排序 java

PS：本文系转载文章，阅读原文可读性会更好，文章末尾有原文链接
目录
1、堆排序

1、1 大顶堆 1、2 小顶堆 1、3 堆排序的速度测试

1、堆排序
1、1 大顶堆
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序；大顶堆是具有以下性质的完全二叉树，即每个结点的值都大于或等于其左右孩子结点的值，但是我们没有要求该结点的左孩子的值和右孩子的值的大小有任何关系。
好，我们举个例子说明一下大顶堆，先画一张图，如下图1所示：
图片
注意：图1中的白色数字表示节点的值，蓝色的数字表示节点的编号。
我们对图1中的堆按层进行编号，映射到数组中的排序是这样的：
arr = {9 , 7 , 8 , 3 , 4 , 5 , 6 , 1 , 2}，这时候发现图1中的节点编号和数组 arr 的下标是一一对应的，并且有 arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 条件是成立的；一般使用大顶堆是升序排序。
好，我们说一下将一个无序的二叉树构成大顶堆的基本思想：
【Java版堆排序】（1）将待排序序列构造成一个大顶堆。
（2）此时，整个序列的最大值就是堆顶的根节点。
（3）将其与末尾元素进行交换，此时末尾就为最大值。
（4）然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值；如此反复执行，便能得到一个有序序列了。
看了二叉树构成大顶堆的基本思想，有的人可能就会说，还是不理解，好，我们现在举个例子：
（1）假设我们有一个无序的二叉树，如图2所示，图2中的二叉树映射成数组是这样的：arr = {1 , 3 , 4 , 2 , 5} ；注意：白色的数字表示的是节点的值，蓝色的数字表示节点的编号，以下图相同。
图片
（2）我们从第一个非叶子节点开始，从下到上，从左到右，计算公式：arr.length / 2 - 1 = 5 / 2 - 1 = 1，从1编号开始，也就是3节点，以3节点为父节点的二叉子树（3节点、2节点、5节点）中右子节点5是最大的，所以3节点和5节点互换位置，得到图3的二叉树，图3中的二叉树映射成数组是这样的：arr = {1 , 5 , 4 , 2 , 3}；
图片
（3）图2中的二叉树，3节点所在的一层，从左到右，右边的节点（4节点）没有子节点，所以4节点不用排大顶堆；从下到上，找到图3中二叉树的第一个非叶子节点（是5节点，图2中的第一个非叶子节点是3节点）的父节点，也就是1节点，以1节点为父节点的二叉子树（1节点、5节点、4节点）中右子节点5是最大的，所以5节点和1节点互换位置，就得到了图4所示的二叉树，图4中的二叉树映射成数组是这样的：arr = {5 , 1 , 4 , 2 , 3}；
图片
（4）这时候根节点为父节点的大顶堆已经排好了，也就是第一层的大顶堆已经排好；但是第二层的大顶堆还没有排好，也就是根节点的左子节点1的大顶堆还没有排序好，于是图4中的二叉树以1节点为父节点的子树（1节点、2节点、3节点）的右子节点是最大的，所以1节点和3节点互换位置，得到图5的二叉树，图5的二叉树映射的数组是这样的：arr = {5 , 3 , 4 , 2 , 1}；
图片
到了这里，图5的二叉树算是排好成大顶堆了，满足条件：父节点总比子节点的值大；看图2，这里就是先从第3层开始做比较，也就是叶子节点开始做比较，比如以3节点为父节点形成的子树（3节点、2节点、5节点），先找到较大的值（5节点）然后“顶”到父节点，然后比较第2层的节点，把第2层的较大值“顶”到父节点，最后最大的值一定3被“顶”到根节点，所以根节点的值是最大的；排大顶堆的规则无非就是先排好根节点的大顶堆，然后再排根节点的子节点的大顶堆，再排根节点的子节点的子节点的大顶堆......，以此类推，最后排好叶子节点的父节点的大顶堆，最终将这棵二叉树排成大顶堆。
好了，说了这么多，我们这里用代码实现一把：将图2的二叉树排成大顶堆。
public class HeapSort {
public static void main(String[] args) {

int[] arr = { 1, 3, 4, 2, 5 }; HeapSort hs = new HeapSort(); hs.sort(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); }

}
private void sort(int[] arr) {

for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); }

}
private void adjustHeap(int[] arr,int i,int length) {

int temp = arr[i]; //取出当前元素的值，保存在临时变量//k 是 i节点的左子节点 for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {//左子节点的值小于右子节点的值，指向右子节点 if (k+1 temp) { arr[i] = arr[k]; i = k; } else { break; } }//以i为父节点的最大值，放在了最顶 arr[i] = temp;

}
}
日志打印如下所示：
图片
从日志可以看出，打印出来的顺序确实是和图5的顺序是一样的。
1、2 小顶堆
小顶堆是具有以下性质的完全二叉树，即每个结点的值都小于或等于其左右孩子结点的值，但是我们没有要求该结点的左孩子的值和右孩子的值的大小有任何关系。
将一个无序的二叉树构成大顶堆的基本思想：
（1）将待排序序列构造成一个小顶堆。
（2）此时，整个序列的最小值就是堆顶的根节点。
（3）将其与末尾元素进行交换，此时末尾就为最小值。
（4）然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次大值；如此反复执行，便能得到一个有序序列了。
小顶堆的排序和大顶堆的排序思路是类似的，都是从下往上，从左往右，也是从 arr.length / 2 - 1 这个位置的节点开始，满足 arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 条件是成立的；一般使用小顶堆是降序排序。
我们就拿图2的二叉树来排成小顶堆来举例说明；
（1）从 arr.length / 2 - 1 这个位置的节点开始，也就是1编号的位置开始，以3节点为父节点的子树（3节点、2节点、5节点）中，3节点大于2节点，所以3节点和2节点互换位置，得到图6，图6映射出来的数组：arr = {1， 4, 2 ， 3， 5}
图片
（2）看图6，从左到右，2节点（序号为1）同一层的兄弟节点（4节点）没有子节点，所以4节点不用排序小顶堆；从下到上，2节点（序号为1）的父节点（1节点）形成的一棵小子树（1节点、2节点、4节点）中，父节点仍然是最小值，所以1节点、2节点、4节点都不用换位置，第一层的小顶堆已经排好。
（3）然后看图6的第二层的小顶堆是否排好，也就是看2节点为父节点形成的一棵小子树（2节点、3节点、5节点）中，父节点仍然是最小值，所以2节点、3节点、5节点都不用换位置，第二层的小顶堆也排好了。
（4）最终图6就排成小顶堆，对应的数组为 arr = {1 ，4 , 2 ， 3 ，5} 。
我们用代码实现一下，把图2的二叉树排序成小顶堆；
public class HeapSort {
public static void main(String[] args) {

int[] arr = { 1, 3, 4, 2, 5 }; HeapSort hs = new HeapSort(); hs.sort2(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); }

}
private void sort2(int[] arr) {

for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap2(arr, i, arr.length); }

}
private void adjustHeap2(int[] arr,int i,int length) {

int temp = arr[i]; //取出当前元素的值，保存在临时变量//k 是 i节点的左子节点 for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {//左子节点的值大于右子节点的值，指向右子节点 if (k+1 arr[k+1]) { k++; }//如果子节点小于父节点，那就把较小的值赋值给当前节点 if (arr[k] < temp) { arr[i] = arr[k]; i = k; } else { break; } }//以i为父节点的最小值，放在了最顶 arr[i] = temp;

}
}
日志打印如下所示：
图片
从日志可以看出，打印出来的顺序确实是和图6的顺序是一样的。
1、3 堆排序的速度测试
堆排序的速度是很快的，在我自己的电脑上排序9千万条数据就用了几十毫秒的时间，我在小顶堆的案例上修改一下主方法的代码；
public static void main(String[] args) {

int[] arr = new int[900 * 10000]; for (int i = 0; i < arr.length; i++) { arr[i] = (int)(Math.random() * 900 * 10000); } HeapSort hs = new HeapSort(); long start = System.currentTimeMillis(); hs.sort2(arr); long end = System.currentTimeMillis(); System.out.println("end - start = " + (end - start));

}
日志打印如下所示：
图片