`
mymail
  • 浏览: 17368 次
  • 性别: Icon_minigender_1
  • 来自: 苏州
最近访客 更多访客>>
社区版块
存档分类
最新评论

堆排序的java实现

阅读更多

堆排序时间的复杂度为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实现

    堆排序 java实现

    DSAA_堆排序java实现_源码

    标题中的“DSAA_堆排序java实现_源码”表明这是一个关于数据结构与算法分析(Data Structures and Algorithms Analysis,简称DSAA)的资料包,主要关注堆排序算法的Java实现。堆排序是一种高效的排序算法,它利用了...

    堆排序JAVA实现代码

    以下将详细介绍堆排序的原理、步骤以及Java实现。 **堆排序的原理** 堆排序的核心思想是构建一个完全二叉树,即堆,然后通过调整堆结构,使得根节点(最大元素或最小元素)总能处于正确的位置。这个过程分为两个...

    堆排序7.java 使用java实现的堆排序

    堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...

    堆排序JAVA实现.zip

    堆排序 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实现堆排序

    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 使用java代码实现堆排序12.java 使用...

    堆排序10.java 使用java来实现

    堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...

    堆排序之Java实现

    以下是Java实现堆排序的基本步骤: 1. 构建大顶堆:从最后一个非叶子节点(即最后一个元素的父节点)开始,自底向上、自右向左进行调整,确保每个节点都大于或等于其子节点。 2. 交换堆顶元素与末尾元素:将最大...

    应用Java和Python分别实现堆排序算法

    堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和...

    堆排序算法(java)

    java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。

    用Java实现的堆排序算法

    用Java实现的堆排序算法,二叉树转换为堆,然后排序

    堆排序Java代码示例

    附件是堆排序Java代码示例,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的! 堆排序是一种高效的比较类排序算法,它利用了二叉堆的数据结构来实现排序。堆排序可以分为两个主要步骤:建堆(将...

    堆排序 Java代码示例

    附件是堆排序Java代码示例,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的! 堆排序是一种高效的比较类排序算法,它利用了二叉堆的数据结构来实现排序。堆排序可以分为两个主要步骤:建堆(将...

    Java实现堆排序.rar

    本文件“Java实现堆排序.rar”可能包含了用Java语言编写的堆排序算法的源代码示例。下面我们将深入探讨堆排序的基本原理、步骤以及如何在Java中实现。 堆排序的核心是构建一个大顶堆或小顶堆。在大顶堆中,每个节点...

    堆排序.java 使用Java来实现

    堆排序 堆排序.java 使用Java来实现

    数据结构堆排序的java算法实现

    数据结构堆排序的java算法实现,里面用java语言实现了堆排序的算法实现,有输入和输出结果

Global site tag (gtag.js) - Google Analytics