wiki中的算法，改用了list做
package com.lee.sort;
import java.util.ArrayList;
import java.util.List;
public class HeapSort2List2 {
private static List<Integer> sort = new ArrayList<Integer>();
public static void main(String[] args) {
sort.add(3);
sort.add(1);
sort.add(4);
sort.add(10);
sort.add(5);
sort.add(9);
sort.add(4);
sort.add(8);
sort.add(2);
sort.add(11);
sort.add(0);
sort.add(15);
buildMaxHeapify(sort);
heapSort(sort);
print(sort);
//printArr(sort);
}
private static void print(List<Integer> sort) {
System.out.println();
for(int s : sort){
System.out.print(s + " ");
}
}
private static void buildMaxHeapify(List<Integer> data) {
int len = data.size();
// 没有子节点的才需要创建最大堆，从最后一个的父节点开始
int startIndex = getParentIndex(len - 1);
// 从尾端开始创建最大堆，每次都是正确的堆
for (int i = startIndex; i >= 0; i--) {
maxHeapify(data, len, i);
}
}
/**
* 创建最大堆
*
* @param data
* @param heapSize
* 需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了
* @param index
* 当前需要创建最大堆的位置
*/
private static void maxHeapify(List<Integer> data, int heapSize, int index) {
// 当前点与左右子节点比较
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
int largest = index;
if (left < heapSize && data.get(index) < data.get(left)) {
largest = left;
}
if (right < heapSize && data.get(largest) < data.get(right)) {
largest = right;
}
// 得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
if (largest != index) {
swap(data, index, largest);
maxHeapify(data, heapSize, largest);
}
}
private static void swap(List<Integer> list, int one, int two) {
list.set(one, list.get(one) ^ list.get(two));
list.set(two, list.get(one) ^ list.get(two));
list.set(one, list.get(one) ^ list.get(two));
}
/**
* 排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的
*
* @param data
*/
private static void heapSort(List<Integer> data) {
// 末尾与头交换，交换后调整最大堆
for (int i = data.size() - 1; i > 0; i--) {
swap(data, 0, i);
maxHeapify(data, i, 0);
System.out.println();
print(data);
}
}
/**
* 父节点位置
*
* @param current
* @return
*/
private static int getParentIndex(int current) {
return (current - 1) >> 1;
}
/**
* 左子节点position 注意括号，加法优先级更高
*
* @param current
* @return
*/
private static int getChildLeftIndex(int current) {
return (current << 1) + 1;
}
/**
* 右子节点position
*
* @param current
* @return
*/
private static int getChildRightIndex(int current) {
return (current << 1) + 2;
}
private static void print(int[] data) {
int pre = -2;
for (int i = 0; i < data.length; i++) {
if (pre < (int) getLog(i + 1)) {
pre = (int) getLog(i + 1);
System.out.println();
}
System.out.print(data[i] + " |");
}
}
private static void printArr(int [] data){
for(int i : data){
System.out.print(i + " ");
}
}
/**
* 以2为底的对数
*
* @param param
* @return
*/
private static double getLog(double param) {
return Math.log(param) / Math.log(2);
}
}
输出结果
11 10 9 8 5 4 4 3 2 1 0 15
10 8 9 3 5 4 4 0 2 1 11 15
9 8 4 3 5 1 4 0 2 10 11 15
8 5 4 3 2 1 4 0 9 10 11 15
5 3 4 0 2 1 4 8 9 10 11 15
4 3 4 0 2 1 5 8 9 10 11 15
4 3 1 0 2 4 5 8 9 10 11 15
3 2 1 0 4 4 5 8 9 10 11 15
2 0 1 3 4 4 5 8 9 10 11 15
1 0 2 3 4 4 5 8 9 10 11 15
0 1 2 3 4 4 5 8 9 10 11 15
0 1 2 3 4 4 5 8 9 10 11 15
另一种方式：
package com.lee.sort;
import java.util.Date;
public class HeapSortTest {
/*
* 将数组调整为小根堆，即由小到大排序
*/
public static int[] heap = new int[100];
public static void main(String[] args) {
for(int i = 0; i < 100; i++){
int j = (int)(Math.random()*100);
heap[i] = j;
}
System.out.println(new Date());
int temp;
/*
* 创建堆（对该堆进行简单的排序）
*/
CreateHeap();
int out = 0;
for (int i = heap.length - 1; 0 < i; i--) {
temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
/*
* 展示每次排序后的结果
*/
for (int j = 0; j < heap.length; j++) {
System.out.print(heap[j] + " ");
}
System.out.println();// 换行
/*
* 从堆顶进行调整，使未排序堆中最大关键字到堆顶
*/
AdjustHeap(0, i);
out++;
if(out > 10){
break;
}
}
System.out.println(new Date());
}
/*
* 调整堆使其堆顶为未排序堆中最大关键字
*/
public static void AdjustHeap(int location, int unSortlength) {
int temp;
int tempLoc;
/*
* 确保左右节点存在
*/
if ((tempLoc = (location + 1) << 1 ) < unSortlength) {
/*
* 判断左右节点大小
*/
if (heap[tempLoc] >= heap[tempLoc - 1]) {
/*
* 判断父节点与子节点的大小，若父节点小，则与大的子节点换位
*/
if (heap[location] < heap[tempLoc]) {
temp = heap[location];
heap[location] = heap[tempLoc];
heap[tempLoc] = temp;
/*
* 递归法对换位后的子节点及其子节点进行调整
*/
AdjustHeap(tempLoc, unSortlength);
}
} else {
/*
* 左节点大于右节点
*/
if (heap[location] < heap[tempLoc - 1]) {
temp = heap[location];
heap[location] = heap[tempLoc - 1];
heap[tempLoc - 1] = temp;
/*
* 递归法对换位后的子节点及其子节点进行调整
*/
AdjustHeap(tempLoc - 1, unSortlength);
}
}
}
/*
* 确保左节点存在
*/
else if ((tempLoc = ((location + 1) << 1) - 1) < unSortlength) {
/*
* 与左节点进行比较
*/
if (heap[location] < heap[tempLoc]) {
/*
* 左子节点大于父节点，将两者进行换位
*/
temp = heap[location];
heap[location] = heap[tempLoc];
heap[tempLoc] = temp;
AdjustHeap(tempLoc, unSortlength);
}
}
}
/*
* 创建堆（对该堆进行简单的排序）
*/
public static void CreateHeap() {
for (int i = heap.length - 1; i >= 0; i--) {
AdjustHeap(i, heap.length);
}
}
}
输出结果：
8 97 97 96 96 88 85 93 91 87 95 80 82 85 58 87 90 90 77 58 85 81 94 74 52 65 63 74 81 54 31 65 74 83 84 37 90 30 40 51 51 80 76 62 73 67 90 69 68 31 19 21 39 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 82 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 62 69 4 32 47 21 98
21 97 88 96 96 82 85 93 91 87 95 80 65 85 58 87 90 90 77 58 85 81 94 74 52 39 63 74 81 54 31 65 74 83 84 37 90 30 40 51 51 80 76 62 73 67 90 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 82 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 62 69 4 32 47 97 98
47 96 88 96 95 82 85 93 91 87 94 80 65 85 58 87 90 90 77 58 85 81 90 74 52 39 63 74 81 54 31 65 74 83 84 37 90 30 40 51 51 80 76 62 73 67 69 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 82 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 62 21 4 32 97 97 98
32 96 88 93 95 82 85 90 91 87 94 80 65 85 58 87 84 90 77 58 85 81 90 74 52 39 63 74 81 54 31 65 74 83 82 37 90 30 40 51 51 80 76 62 73 67 69 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 62 21 4 96 97 97 98
4 95 88 93 94 82 85 90 91 87 90 80 65 85 58 87 84 90 77 58 85 81 69 74 52 39 63 74 81 54 31 65 74 83 82 37 90 30 40 51 51 80 76 62 73 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 32 21 96 96 97 97 98
21 94 88 93 90 82 85 90 91 87 81 80 65 85 58 87 84 90 77 58 85 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 90 30 40 51 51 80 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 8 49 23 32 95 96 96 97 97 98
32 93 88 91 90 82 85 90 90 87 81 80 65 85 58 87 84 90 77 58 85 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 82 30 40 51 51 80 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 8 49 23 94 95 96 96 97 97 98
23 91 88 90 90 82 85 90 90 87 81 80 65 85 58 87 84 82 77 58 85 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 32 30 40 51 51 80 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 8 49 93 94 95 96 96 97 97 98
49 90 88 90 87 82 85 90 90 85 81 80 65 85 58 87 84 82 77 58 80 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 32 30 40 51 51 23 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 8 91 93 94 95 96 96 97 97 98
8 90 88 90 87 82 85 90 82 85 81 80 65 85 58 87 84 49 77 58 80 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 32 30 40 51 51 23 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 90 91 93 94 95 96 96 97 97 98
4 90 88 90 87 82 85 87 82 85 81 80 65 85 58 74 84 49 77 58 80 73 69 74 52 39 63 74 81 54 31 65 58 83 82 37 32 30 40 51 51 23 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 8 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 90 90 91 93 94 95 96 96 97 97 98
另一种可以选择升序降序的方式
package com.lee.sort;
public class HeapSort2 {
public static void main(String[] args) {
HeapSort2 heapSort = new HeapSort2();
int[] A = new int[] { 1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12,
17, 34, 11 };
boolean isInc = false;
heapSort.sort(A, isInc);
printIntArray(A);
}
private static void printIntArray(int[] A){
for(int a : A){
System.out.print(a + " ");
}
}
private IntArray A = null;
public HeapSort2() {
A = new IntArray();
}
private class IntArray {
public int[] aArray = null;
public int heapSize = 0;
}
public void sort(int[] A) {
maxHeapSort(A);
}
public void sort(int[] A, boolean isInc) {
if (isInc) {
maxHeapSort(A);
} else {
minHeapSort(A);
}
}
/**
* 最大堆排序，升序
*
* @param A
* int数组
*/
private void maxHeapSort(int[] A) {
this.A.aArray = A;
this.A.heapSize = A.length;
buildMaxHeap(this.A);
for (int i = A.length; i >= 2; i--) {
exchange(1, i);
this.A.heapSize = this.A.heapSize - 1;
maxHeapify(this.A, 1);
}
}
/**
* 最小堆排序，降序
*
* @param A
* int数组
*/
private void minHeapSort(int[] A) {
this.A.aArray = A;
this.A.heapSize = A.length;
buildMinHeap(this.A);
for (int i = A.length; i >= 2; i--) {
exchange(1, i);
this.A.heapSize = this.A.heapSize - 1;
minHeapify(this.A, 1);
}
}
/**
* 使得以index为根的子树成为最大堆
*
* @param A
* int数组
* @param index
* 以index为根，从1开始
*/
private void maxHeapify(IntArray A, int index) {
while (index < A.heapSize / 2 + 1) {
int left = left(index);
int right = right(index);
int largest = 0;
if (left <= A.heapSize && A.aArray[left - 1] > A.aArray[index - 1]) {
largest = left;
} else {
largest = index;
}
if (right <= A.heapSize
&& A.aArray[right - 1] > A.aArray[largest - 1]) {
largest = right;
}
if (index != largest) {
exchange(index, largest);
index = largest;
} else {
index = A.heapSize / 2 + 1;
}
}
}
/**
* 使得以index为根的子树成为最小堆
*
* @param A
* int数组
* @param index
* 以index为根，从1开始
*/
private void minHeapify(IntArray A, int index) {
while (index < A.heapSize / 2 + 1) {
int left = left(index);
int right = right(index);
int smallest = 0;
if (left <= A.heapSize && A.aArray[left - 1] < A.aArray[index - 1]) {
smallest = left;
} else {
smallest = index;
}
if (right <= A.heapSize
&& A.aArray[right - 1] < A.aArray[smallest - 1]) {
smallest = right;
}
if (index != smallest) {
exchange(index, smallest);
index = smallest;
} else {
index = A.heapSize / 2 + 1;
}
}
}
/**
* 建最大堆
*
* @param A
* int数组
*/
private void buildMaxHeap(IntArray A) {
for (int i = A.aArray.length / 2; i >= 1; i--) {
maxHeapify(A, i);
}
}
/**
* 建最小堆
*
* @param A
* int数组
*/
private void buildMinHeap(IntArray A) {
for (int i = A.aArray.length / 2; i >= 1; i--) {
minHeapify(A, i);
}
}
private int left(int index) {
return 2 * index;
}
private int right(int index) {
return 2 * index + 1;
}
private void exchange(int i, int j) {
int temp = A.aArray[i - 1];
A.aArray[i - 1] = A.aArray[j - 1];
A.aArray[j - 1] = temp;
}
}
分享到：
相关推荐
堆排序详细图解（通俗易懂）+排序算法----堆排序（超详细）堆排序详细图解（通俗易懂）+排序算法----堆排序（超详细）堆排序详细图解（通俗易懂）+排序算法----堆排序（超详细）堆排序详细图解（通俗易懂）+排序算法...
堆排序是一种基于比较的排序算法，它利用了数据结构中的“堆”这一概念。在计算机科学中，堆通常被理解为一个完全二叉树，其中每个父节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。堆排序分为...
常用的排序算法--堆排序，通过创建堆的方法进行排序
数据结构从入门到精通-堆排序
JAVADevOps 堆排序 堆排序 堆排序 堆排序 堆排序
Python 堆排序 堆排序 堆排序 堆排序 堆排序
https://www.geeksforgeeks.org/sorting-algorithms/ 堆排序 堆排序 堆排序 堆排序 堆排序
堆排序 堆排序 堆排序 堆排序 堆排序
第27周-第04章节-Python3.5-堆排序.avi
但是，快速排序的实际执行时间却比堆排序更快，这是因为快速排序的 cache freundliness 比堆排序更好。 快速排序、堆排序和归并排序都是 O(nlogn) 的时间复杂度，但是它们的稳定性、辅助空间和 cache freundliness ...
堆排序是一种基于比较的排序算法，它利用了数据结构中的“堆”这一概念。在计算机科学中，堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序有两种...
第28周-第01章节-Python3.5-堆排序复习.mp4
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念，包括如何对数组进行排序以及如何在Java中实现堆排序。此外，文档还包括一个逐步指南，介绍了如何在Java中实现堆排序，包括详细的代码示例和...
堆排序
堆排序是一种基于比较的排序算法，它通过构建一个大顶堆或小顶堆来实现排序。在计算机科学中，堆通常被理解为一种特殊的树形数据结构，满足堆的性质：父节点的值总是大于或等于（对于大顶堆）或小于或等于（对于小...
堆排序是一种基于比较的排序算法，它利用了数据结构中的“堆”这一概念。在计算机科学中，堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序有两种...
JavaSE…… Java JavaEE : javaIO, /Socket JDBCTomcat/Servlet, 堆排序 堆排序 堆排序 堆排序 堆排序
比较详细地讲述了堆排序的思路和代码实现，适合初学者
堆排序是一种树形选择排序算法，它的基本思想是将待排序的数组构建成一个大根堆（或小根堆），然后将堆顶元素与堆底元素交换位置，再将剩余元素重新构建成堆，重复执行交换和重构堆的操作，直到整个数组有序。堆排序...
该资源是一个入门级别的C++算法练习，旨在帮助读者学习和理解堆排序算法。文档中包含了堆排序的基本原理和实现方法，并提供了详细的代码示例和解析。 通过学习和完成这个练习，读者将能够掌握堆排序算法的思想和...