即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

java 堆排序

编程语言 u012438476 15℃ 0评论

1、基本思想:

  堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种,对直接选择排序的有效改进。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]]
>= A[i]。
在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

  堆的定义下:具有n个元素的序列 (h1,h2,…,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二 叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。

  思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个 堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对 它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

2、实例

初始序列:46,79,56,38,40,84

  建堆:

   交换,从堆中踢出最大数

依次类推:最后堆中剩余的最后两个结点交换,踢出一个,排序完成。

3.算法实现:

public class sort {// 堆排序

 private static int[] sort = new int[] { 1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12, 17, 34, 11 };

 public static void main(String[] args) {
  buildMaxHeapify(sort);
  heapSort(sort);
  print(sort);
 }

 private static void buildMaxHeapify(int[] data) {
  // 没有子节点的才需要创建最大堆,从最后一个的父节点开始
  int startIndex = getParentIndex(data.length - 1);
  // 从尾端开始创建最大堆,每次都是正确的堆
  for (int i = startIndex; i >= 0; i--) {
   maxHeapify(data, data.length, i);
  }
 }

 /**
  * 创建最大堆
  * @paramheapSize需要创建最大堆的大小,一般在sort的时候用到,因为最多值放在末尾,末尾就不再归入最大堆了
  * @paramindex当前需要创建最大堆的位置
  */
 private static void maxHeapify(int[] data, int heapSize, int index) {
  // 当前点与左右子节点比较
  int left = getChildLeftIndex(index);
  int right = getChildRightIndex(index);

  int largest = index;
  if (left < heapSize && data[index] < data[left]) {
   largest = left;
  }
  if (right < heapSize && data[largest] < data[right]) {
   largest = right;
  }
  // 得到最大值后可能需要交换,如果交换了,其子节点可能就不是最大堆了,需要重新调整
  if (largest != index) {
   int temp = data[index];
   data[index] = data[largest];
   data[largest] = temp;
   maxHeapify(data, heapSize, largest);
  }
 }

 /**
  * 排序,最大值放在末尾,data虽然是最大堆,在排序后就成了递增的
  */
 private static void heapSort(int[] data) {
  // 末尾与头交换,交换后调整最大堆
  for (int i = data.length - 1; i > 0; i--) {
   int temp = data[0];
   data[0] = data[i];
   data[i] = temp;
   maxHeapify(data, i, 0);
  }
 }

 /**
  * 父节点位置
  */
 private static int getParentIndex(int current) {
  return (current - 1) >> 1;
 }

 /**
  * 左子节点position注意括号,加法优先级更高
  */
 private static int getChildLeftIndex(int current) {
  return (current << 1) + 1;
 }

 /**
  * 右子节点position
  */
 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]+ " ");
  }
 }

 /**
  * 以2为底的对数
  */
 private static double getLog(double param) {
  return Math.log(param) / Math.log(2);
 }
}



转载请注明:CodingBlog » java 堆排序

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情