堆排序时间的复杂度为N lgN,空间复杂度为常量,没有很深的调用堆栈,是本人比较偏好的一种排序方法,堆排序的一般步骤是:
1 创建堆
2 不断取出根元素重建堆
package heapsort;
import java.util.Random;
public class HeapSort{
public static void sort(Comparable[] array) {
for (int i = 1; i < array.length; i++) {
makeHeap(array, i);
}
for (int i = array.length-1; i > 0; i--) {
Comparable temp = array[i];
array[i] = array[0];
array[0] = temp;
rebuildHeap(array, i);
}
}
// 把 array[k-1]看成一个堆 , 把添加到队中
private static void makeHeap(Comparable[] array,int k) {
int current = k;
while (current > 0 && array[current].compareTo(array[(current-1)/2]) >0 ) {
Comparable temp = array[current];
array[current] = array[(current-1)/2];
array[(current-1)/2] = temp;
current = (current-1)/2;
}
}
//堆的根元素已删除,末尾元素已移到根位置,开始重建
public static void rebuildHeap(Comparable[] array, int size) {
int currentIndex = 0;
int right = currentIndex * 2 + 2;
int left = currentIndex * 2 + 1;
int maxIndex = currentIndex;
boolean isHeap = false;
while (!isHeap) {
if (left < size && array[currentIndex].compareTo(array[left]) < 0) {
maxIndex = left;
}
if (right < size && array[maxIndex].compareTo(array[right]) < 0) {
maxIndex = right;
}
if (currentIndex == maxIndex) {
isHeap = true;
} else {
Comparable temp = array[currentIndex];
array[currentIndex] = array[maxIndex];
array[maxIndex] = temp;
currentIndex = maxIndex;
right = currentIndex * 2 + 2;
left = currentIndex * 2 + 1;
}
}
}
public static void main(String[] args) {
Random random = new Random();
int len = 200;
Integer[] arrInteger = new Integer[len];
for (int i = 0; i < arrInteger.length; i++) {
arrInteger[i] = random.nextInt(200);
System.out.print(arrInteger[i]+"\t");
}
System.out.print("\n");
Integer[] mmInteger = new Integer[len];
System.arraycopy(arrInteger, 0, mmInteger, 0, len);
long start = System.nanoTime();
sort(arrInteger);
long end = System.nanoTime();
System.out.println("time use" + (end - start));
start = System.nanoTime();
for (int i = 0; i <mmInteger.length; i++) {
for (int j = 0; j < mmInteger.length-i-1; j++) {
if (mmInteger[j].compareTo(mmInteger[j+1]) >0) {
Integer temp = mmInteger[j];
mmInteger[j] = mmInteger[j+1];
mmInteger[j+1] = temp;
}
}
}
end = System.nanoTime();
System.out.println("Quick sort time use" + (end - start));
System.out.println("排序后");
for (Integer integer : arrInteger) {
System.out.print(integer+"\t");
}
System.out.print("\n");
for (Integer integer : mmInteger) {
System.out.print(integer+"\t");
}
System.out.print("\n");
}
}
分享到:
相关推荐
堆排序 java实现
标题中的“DSAA_堆排序java实现_源码”表明这是一个关于数据结构与算法分析(Data Structures and Algorithms Analysis,简称DSAA)的资料包,主要关注堆排序算法的Java实现。堆排序是一种高效的排序算法,它利用了...
以下将详细介绍堆排序的原理、步骤以及Java实现。 **堆排序的原理** 堆排序的核心思想是构建一个完全二叉树,即堆,然后通过调整堆结构,使得根节点(最大元素或最小元素)总能处于正确的位置。这个过程分为两个...
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
堆排序 public static class MyMaxHeap { private int[] heap; private final int limit; private int heapSize; public MyMaxHeap(int limit) { heap = new int[limit]; this.limit = limit; ...
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...
以下是Java实现堆排序的基本步骤: 1. 构建大顶堆:从最后一个非叶子节点(即最后一个元素的父节点)开始,自底向上、自右向左进行调整,确保每个节点都大于或等于其子节点。 2. 交换堆顶元素与末尾元素:将最大...
堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和...
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
用Java实现的堆排序算法,二叉树转换为堆,然后排序
附件是堆排序Java代码示例,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的! 堆排序是一种高效的比较类排序算法,它利用了二叉堆的数据结构来实现排序。堆排序可以分为两个主要步骤:建堆(将...
附件是堆排序Java代码示例,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的! 堆排序是一种高效的比较类排序算法,它利用了二叉堆的数据结构来实现排序。堆排序可以分为两个主要步骤:建堆(将...
本文件“Java实现堆排序.rar”可能包含了用Java语言编写的堆排序算法的源代码示例。下面我们将深入探讨堆排序的基本原理、步骤以及如何在Java中实现。 堆排序的核心是构建一个大顶堆或小顶堆。在大顶堆中,每个节点...
堆排序 堆排序.java 使用Java来实现
数据结构堆排序的java算法实现,里面用java语言实现了堆排序的算法实现,有输入和输出结果