java 堆排序算法

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

算法分析

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

平均性能

O(N*logN)。

其他性能

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1）.

它是不稳定的排序方法。（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前 和排序后他们的相对位置不发生变化）

特点

堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（参见二叉树的顺序存储结构），在当前无序区中选择关键字最大（或最小）的记录

注意

①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。

②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止

示例代码

package com.wepayweb.weixin.util.paixu;
/******V型知识库 www.vxzsk.com*********/

public class Heapsort {
	 final int MAX=20;  
	   int num[]=new int[MAX];  
	   {  
	       System.out.print("生成的随机数组是：");  
	       for(int i=0;i<20;i++){  
	           num[i]=(int)(Math.random()*100);  
	           System.out.print(num[i]+" ");  
	       }  
	       System.out.println();  
	   }  
	
	/*-----------------------heap排序（堆排序法--改进的选择排序）---------------------------- 
    利用堆积树的原理，先构造一个堆积树（看堆积树的定义，笔记本上有），然后将根节点与最后的叶子节点交换，并屏蔽掉最后一个叶子节点， 
    然后再将未被屏蔽的部分重新构造堆积树，然后再重复上面的步骤，直到所有的数被按顺序排好。 
--------------------------------------------------------------------------------*/  
public void heapsort(int number[]) {  
int i, m, p, s, temp;  
long start,end;  
  
start=System.nanoTime();  
int number_temp[]=new int[MAX+1];  
for(int temp_i=1;temp_i<MAX+1;temp_i++){  
    number_temp[temp_i]=number[temp_i-1];  
}  
createheap(number_temp);  
m = MAX;  
while(m > 1) {  
    temp=number_temp[1];  
    number_temp[1]=number_temp[m];  
    number_temp[m]=temp;  
    m--;  
    p = 1;  
    s = 2 * p;  
    while(s <= m) {  
        if(s < m && number_temp[s+1] > number_temp[s])  
            s++;  
        if(number_temp[p] >= number_temp[s])  
            break;  
        temp=number_temp[p];  
        number_temp[p]=number_temp[s];  
        number_temp[s]=temp;  
        p = s;  
        s = 2 * p;  
    }  
}  
for(int temp_j=1;temp_j<MAX+1;temp_j++){  
    number[temp_j-1]=number_temp[temp_j];  
}  
end=System.nanoTime();  
  
  
 System.out.println("-----------------heap排序（堆排序法--改进的选择排序）------------------");  
 System.out.print("排序后是:");  
 for(i=0;i<=MAX-1;i++){  
     System.out.print(number[i]+" ");  
 }  
 System.out.println();  
 System.out.println("排序使用时间："+(end-start)+" ns");  
}  

//将原数组构造为从下标1开始的一个新数组，便于处理，同时将这个新数组构造为最初始的堆积树结构  
public void createheap(int number[]) {  
    int i, s, p, temp;  
    int heap[] = new int[MAX+1];  
    for(i = 1; i <= MAX; i++) {  
        heap[i] = number[i];  
        s = i;  
        p = i / 2;  
        while(s >= 2 && heap[p] < heap[s]) {  
            temp=heap[p];  
            heap[p]=heap[s];  
            heap[s]=temp;  
            s = p;  
            p = s / 2;  
        }  
    }  
    for(i = 1; i <= MAX; i++){  
       number[i] = heap[i];   
    }  
}  
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Heapsort s = new Heapsort();
		s.heapsort(s.num.clone());                        //堆排序法  
	}

}

运行main方法，结果：

生成的随机数组是：29 33 79 35 81 98 27 40 57 97 13 28 92 56 13 50 87 33 44 31 
-----------------heap排序（堆排序法--改进的选择排序）------------------
排序后是:13 13 27 28 29 31 33 33 35 40 44 50 56 57 79 81 87 92 97 98 
排序使用时间：12342 ns