排序算法三：堆排序（Heapsort）
堆排序（Heapsort）是一种利用数据结构中的堆进行排序的算法，分为构建初始堆，减小堆的元素个数，调整堆共3步。
（一）算法实现
protected void sort(int[] toSort) {
buildHeap(toSort);
for (int i = toSort.length - 1; i > 0; i--) {
CommonUtils.swap(toSort, 0, i);
adjustHeap(toSort, 0, i);
}
}
/**
*
* @param toSort
* array of heap, begins from 0
* @param index
* index to adjust
* @param size
* size of heap
*/
private void adjustHeap(int[] toSort, int index, int size) {
int leftNode = index * 2 + 1;
int rightNode = leftNode + 1;
int maxIndex = index;
if (leftNode < size && toSort[leftNode] > toSort[maxIndex]) {
maxIndex = leftNode;
}
if (rightNode < size && toSort[rightNode] > toSort[maxIndex]) {
maxIndex = rightNode;
}
if (maxIndex != index) {
CommonUtils.swap(toSort, index, maxIndex);
adjustHeap(toSort, maxIndex, size);
}
}
/**
*
* @param toSort
* array to sort
*/
private void buildHeap(int[] toSort) {
int lastNonLeaf = toSort.length / 2 - 1;
for (int i = lastNonLeaf; i >= 0; i--) {
adjustHeap(toSort, i, toSort.length);
}
}
Heap sort
1）堆排序是原地排序
2）堆排序的时间复杂度是O(nlgn)
3）堆排序属于比较排序
4）堆排序不是稳定排序算法
（二）仿真结果
**************************************************
Number to Sort is:2500
Array to sort is:{419836,72576,347420,355422,378503,65556,443634,137868,266344,918856...}
Cost time of 【HeapSort】 is(milliseconds):1
Sort result of 【HeapSort】:{185,874,996,1232,1448,2357,2728,2854,3137,3291...}
**************************************************
Number to Sort is:25000
Array to sort is:{169570,655593,54301,59080,890711,224726,720131,590749,600165,681962...}
Cost time of 【HeapSort】 is(milliseconds):7
Sort result of 【HeapSort】:{9,107,119,192,297,321,338,359,359,362...}
**************************************************
Number to Sort is:250000
Array to sort is:{233097,327821,972339,26697,803510,598167,178244,117664,904299,195258...}
Cost time of 【HeapSort】 is(milliseconds):59
Sort result of 【HeapSort】:{0,1,3,8,16,24,32,37,45,52...}
相关代码：
package com.cnblogs.riyueshiwang.sort;
import java.util.Arrays;
public class HeapSort extends abstractSort {
@Override
protected void sort(int[] toSort) {
buildHeap(toSort);
for (int i = toSort.length - 1; i > 0; i--) {
CommonUtils.swap(toSort, 0, i);
adjustHeap(toSort, 0, i);
}
}
/**
*
* @param toSort
* array of heap, begins from 0
* @param index
* index to adjust
* @param size
* size of heap
*/
private void adjustHeap(int[] toSort, int index, int size) {
int leftNode = index * 2 + 1;
int rightNode = leftNode + 1;
int maxIndex = index;
if (leftNode < size && toSort[leftNode] > toSort[maxIndex]) {
maxIndex = leftNode;
}
if (rightNode < size && toSort[rightNode] > toSort[maxIndex]) {
maxIndex = rightNode;
}
if (maxIndex != index) {
CommonUtils.swap(toSort, index, maxIndex);
adjustHeap(toSort, maxIndex, size);
}
}
/**
*
* @param toSort
* array to sort
*/
private void buildHeap(int[] toSort) {
int lastNonLeaf = toSort.length / 2 - 1;
for (int i = lastNonLeaf; i >= 0; i--) {
adjustHeap(toSort, i, toSort.length);
}
}
public static void main(String[] args) {
for (int j = 0, n = 2500; j < 3; j++, n = n * 10) {
System.out
.println("**************************************************");
System.out.println("Number to Sort is:" + n);
int[] array = CommonUtils.getRandomIntArray(n, 1000000);
System.out.print("Array to sort is:");
CommonUtils.printIntArray(array);
int[] array1 = Arrays.copyOf(array, n);
new HeapSort().sortAndprint(array1);
}
}
}
HeapSort.java
最新文章
- mybatis Generator生成代码及使用方式
- SVN冲突
- lecture9-提高模型泛化能力的方法
- 例子：Background Agent Sample
- 细菌觅食算法-python实现
- 原！！ java直接打印一个对象时，并不是直接调用该类的toString方法 ，而是会先判断是否为null，非null才会调用toString方法
- 初步探讨WPF的ListView控件(涉及模板、查找子控件)
- BZOJ 1051: [HAOI2006]受欢迎的牛 缩点
- HTML 页面加载动画效果
- PHP中magic_quotes_gpc和 magic_quotes_runtime区别及其反斜线转义问题
- WPF 3D：简单的Point3D和Vector3D动画创造一个旋转的正方体
- Android Studio的使用（十一）--每次打开时选择项目，而不是直接进入上次项目
- php执行linux命令的6个函数
- Java 中 compareTo方法问题
- Centos常用命令之：VI
- asp.net core 2.0 webapi集成signalr
- 【1】【JUC】Condition和生产者消费者模型
- redis的key越来越多,对速度是否有影响
- Windows平台上使用Github搭建Git服务器的图文教程
- lucene solr