java 堆排序算法

2018年04月23日 09:15 | 1621次浏览 作者原创 版权保护

堆排序(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



小说《我是全球混乱的源头》
此文章本站原创,地址 https://www.vxzsk.com/824.html   转载请注明出处!谢谢!

感觉本站内容不错,读后有收获?小额赞助,鼓励网站分享出更好的教程