堆排序实现难点

 

  堆排序的步骤如下:

     首先建立堆,然后引入了循环不变式,就是初始情况下,整个数组都为堆,然后始终把堆的根,也就是第一个元素与堆的最后一个元素交换,这样每次交换后,从堆最后一个元素开始到结束是有序的,最后堆化前面无序区,直到堆只剩下一个元素!

这个不变式和选择排序等不变式一样,分成两部分,前面堆部分为无序区,后面为有序区!

      堆排序与选择排序的区别在于:选择排序每次都比较得到最大的值,而堆排序也是每次得到最大值,但是通过堆的特点记录了上次部分比较结果,使得下次比较次数减少!

      堆排序的核心在于堆化部分,开始是堆化整个数组,后面是依次堆化数组中的无序部分!

      为整个数组建堆的过程是自底向上的,理解这一点很重要,因为堆的定义是递归定义的!所以建堆过程是从最后高度为二的节点开始的,也就是length/2.

      在为每一个节点堆化的过程中,我们是从该节点和其左右子节点中,寻找出最大的那个,并且把最大值与该节点交换!当最大的节点为子节点的某一个时候,交换后还需要递归堆化该子节点!(在理解这一点时,我花了瞒长时间,因为我忽略了其左右子节点为堆这个事实!)

       上面部分是原理部分!

       编写具体代码上,以下卡了一段时间

       在堆化的过程中,分清楚数组的值是从0开始的,而堆元素的根是从1这个序列开始,把该节点和其左右子节点的计算和在数组中的位置表示出来,如果混用的化,则得不到理想的结果!

       每次在无序区堆化的时候,特别注意的是,无序区动态减少,所以堆化的堆大小每次循环时候都减小的事实,不可以忽略!

 

以下是实现代码:

  

public class HeapSort {

	
	public static void main(String[] args) {
		
		int[] arr = {1,2,3,4,5,6,7,8,9};
		buildHeap(arr);
		System.out.println("this is build heap result:");
		for(int i:arr){
			System.out.print(i);
		}
		heapSort(arr);
		System.out.println("");
		System.out.println("this is sorted by heapSort result:");
		for(int i:arr){
			System.out.print(i);
		}

	}
	
	public static void heapfy(int[] arr,int i,int heapSize){
		int largest;
		int l = 2*i-1;
		int r = 2*i;
		
		if(l<heapSize&&arr[l]>arr[i-1])
			largest = l;
		else
			largest = i-1;
		
		if(r<heapSize&&arr[r]>arr[largest])
			largest = r;
		
		if(largest!= i-1){
			swap(arr,i-1,largest);
			heapfy(arr,largest+1,heapSize);
		}
	}
	public static void swap(int[] arr,int i,int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	public static void buildHeap(int[] arr){
		
		for(int i=arr.length/2;i>0;i--){
			heapfy(arr,i,arr.length);
		}
		
	}
	
	public static void heapSort(int[] arr){
		buildHeap(arr);
		for(int i=0;i<arr.length;i++){
			swap(arr,0,arr.length-1-i);
			heapfy(arr,1,arr.length-i-1);
		}
	}

}