堆排序算法的java实现

```    public static void heapSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}

buildMaxHeap(array);

System.out.println("buildMaxHeap " + Arrays.toString(array));

for (int i = array.length - 1; i >= 1; i--) {
exchangeElements(array, 0, i);

maxHeap(array, i, 0);

System.out.println("maxHeap " + Arrays.toString(array) + " i is "
+ i);
}

}

private static void buildMaxHeap(int[] array) {
if (array == null || array.length <= 1) {
return;
}

int half = array.length / 2 - 1;
// 根据二叉树性质，深度为k的二叉树至多有2的k次方-1个结点(k≥1）
// 所以如果最末尾节点为右节点，array.length为奇数，那么上一层父节点的编号应该为（array.length-1）/2=array.length/2
// 所以如果最末尾节点为左节点，array.length为偶数，那么上一层父节点的编号也为array.length/2
// 由于数组下标从0开始，所以应该要在堆对应的编号基础上-1

// 从下往上把比较中最大的值往顶上冒，冒过后要把被换下来的值对应的子树再做一遍堆调整。
for (int i = half; i >= 0; i--) {
maxHeap(array, array.length, i);
}
}

private static void maxHeap(int[] array, int heapSize, int index) {
// 堆编号x ，数组编号index ，a=index+1;
// 所以左节点数组编号=2a-1=index * 2 + 1
// 右节点数组编号=2a+1-1=index * 2 + 2

int left = index * 2 + 1;
int right = index * 2 + 2;

int largest = index;
if (left < heapSize && array[left] > array[index]) {
largest = left;
}

if (right < heapSize && array[right] > array[largest]) {
largest = right;
}

if (index != largest) {
exchangeElements(array, index, largest);// 将子节点更大的值换到父节点

System.out.println("maxHeap " + Arrays.toString(array)
+ " index is " + index + " left is " + left + " right is "
+ right + " largest is " + largest + " heapSize is "
+ heapSize);

maxHeap(array, heapSize, largest);// 原有父节点的值放到了子节点后可能不满足堆的性质，需要调整修改后largest节点对应的子树
}
}

private static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}```

while循环，同样父子节点交换后记录被换过的子节点位置，使用while (2 * k + 1 <= lastIndex)循环判断对应的子树是否符合堆性质并调整

```    public static void heapSort2(int[] array) {
for (int i = 0; i < array.length; i++) {
maxHeap2(array, array.length - 1 - i);
exchangeElements(array, 0, array.length - 1 - i);
System.out.println(Arrays.toString(array));
}

}

private static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}

private static void maxHeap2(int[] data, int lastIndex) {

//lastIndex= array.length - 1
//所以(lastIndex+1)/2-1等于上层最后一个有子节点的节点在数组中的索引
//(lastIndex+1)/2-1=(lastIndex-1)/2
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// 保存当前正在判断的节点
int k = i;

// 若当前节点的左节点存在
while (2 * k + 1 <= lastIndex) {//

// biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
int biggerIndex = 2 * k + 1;
if (biggerIndex < lastIndex) {
// 若右子节点存在，比较左右子节点大小，右节点不存在biggerIndex为左节点
if (data[biggerIndex] < data[biggerIndex + 1]) {
// 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值
biggerIndex++;
}
}
if (data[k] < data[biggerIndex]) {
// 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k
exchangeElements(data, k, biggerIndex);
k = biggerIndex; //k记录了原来的父节点被换到了什么位置，原来的父节点下来后不一定比子节点更大
//while循环继续去判断它对应的子树符不符合堆的性质并调整
System.out.println("k is "+k+" "+Arrays.toString(data));

} else {
//父节点已经比子节点大了，不需要调整
break;
}

//System.out.println();
}
}

}```

http://blog.csdn.net/apei830/article/details/6584645

http://blog.csdn.net/kimylrong/article/details/17150475

0 条评论

• 二路归并排序的java实现

转载请注明出处 http://www.cnblogs.com/dongxiao-yang/p/6410775.html

• PriorityBlockingQueue优先队列的二叉堆实现

转载请注明原创地址http://www.cnblogs.com/dongxiao-yang/p/6293807.html

• Java GC CMS 日志分析

https://blogs.oracle.com/poonam/entry/understanding_cms_gc_logs

• python--几种快速排序的实现以及运行时间比较

快速排序的基本思想：首先选定一个数组中的一个初始值，将数组中比该值小的放在左边，比该值大的放在右边，然后分别对左边的数组进行如上的操作，对右边的数组进行如上的操...

• php实现快速排序算法

每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在...

• 常用七种排序的python实现

算法复杂度分为时间复杂度和空间复杂度。其中， 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

• PHP数组array类常见操作示例

array_diff(arr1,arr2);//计算数组的差集（对比返回在 array1 中但是不在 array2 及任何其它参数数组中的值。）

• python 快排算法

先说两句题外话，一般意义上的栈有两层含义，一层是后进先出的数据结构栈，一层是指函数的内存栈，归根结底，函数的内存栈的结构就是一个后进先出的栈。汇编代码中，调用一...

• 跟我学习php数组常用函数-下篇

如果是递归的,结果:array('hobby' => array('a' => 'ping-pong', 'b' => 'basketball'));

• jQuery ajax+PHP实现的级联下拉列表框功能示例

本文实例讲述了jQuery ajax+PHP实现的级联下拉列表框功能。分享给大家供大家参考，具体如下：