算法:堆排序

堆排序

最近重温了经典的堆排序的算法，堆是一种优先队列，堆排序是基于完全二叉树结构的，由选择排序优化而来，常数时间内最坏最好情况时间复杂度都是O(nlogn)，而堆又分为两种，分别是大顶堆和小顶堆，由于一般排序算法都是实现序列升序化，故堆排序在一般教材里都是以小顶堆形式出现，算法实现步骤分为三步:建堆，调整堆，输出堆顶元素，废话不多说，上代码

public class 堆 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.println("待排序的数字数量:");
		int n = in.nextInt();
		int heap[] = new int[n+1];//堆数组
		System.out.println("请输入待排序的数字:");
		//创建堆
		for(int i = 1;i<=n;i++) {
			heap[i] = in.nextInt();
	  	}
		int len = heap.length-1;
		long begin = System.nanoTime();
		alterheap(heap, len);//算法入口
		long end = System.nanoTime();
		System.out.println("time"+(end-begin));//计算排序时间
	}
	
	//调整堆
	static void alterheap(int[] heap,int l) {
		int len = l;
		while(len > 0) {
			int gap = len >> 1;
			//向上调整
			for(int i = gap;i>=1;i--) {
				if((i<<1)+1 > len)//表示只有左孩子
				{
					if(heap[i]>heap[i<<1]) {
						swap(i,i<<1,heap);
					}
				}else {
					//左右子孩子都存在，选择其中最小的一个进行交换
					boolean isLeft = heap[i<<1]<heap[(i<<1)+1]?true:false;
					if(isLeft && heap[i] > heap[i<<1]) {
						swap(i,i<<1,heap);
					}
					if(!isLeft && heap[i] > heap[(i<<1) +1]) {
						swap(i,(i<<1)+1,heap);
					}
				}
			}
			
			//调整完成，输出顶部元素
			System.out.println(heap[1]);
			//将堆顶元素和堆里最后一个元素交换，堆缩容
			swap(1,len,heap);
			len--;
		}
	}
	
	//交换元素
	static void swap(int a,int b,int[] heap) {
		heap[a] = heap[a]^heap[b];
		heap[b] = heap[a]^heap[b];
		heap[a] = heap[a]^heap[b];
	}
}

只能说有待优化吧，我测了一下和java库里的快排速率的比较，我写的简直菜爆了，不过能理会思想，也是一种学习吧