[数据结构与算法]八大排序算法---堆排序

?这是一个大顶堆，每个父节点都比孩子大。

package suanfa;

import java.util.Arrays;

public class Duipaixu {
	
	//维护大顶堆
	static void dadingdui(int[] arr,int n,int i) {
		int largest = i;//父节点i
		int lson = 2*i+1;//左孩子
		int rson = 2*i+2;//右孩子
		//如果哪个孩子的值大于父节点则把最大值的下标给到largest
		if(lson<n&&arr[lson]>arr[largest]) {
			largest = lson;
		}
		if(rson<n&&arr[rson]>arr[largest]) {
			largest = rson;
		}
		if(largest!=i) {//若相等则说明大顶堆成立，不需要交换
//			swap(arr[largest],arr[i]);
			//上面的方法因为java没有指针所以就在这里交换吧
			arr[largest]=arr[largest]^arr[i];
			arr[i]=arr[largest]^arr[i];
			arr[largest]=arr[largest]^arr[i];
			dadingdui(arr,n,largest);
		}	
	}
	
	 static void duipaixu(int[] arr,int n) {
		//建堆
		 int i;//n/2-1时就是大顶堆最后一个小大顶堆的父节点
		 for(i=n/2-1;i>=0;i--) {
			 dadingdui(arr,n,i);
		 }
		 //排序
		 for(i=n-1;i>0;i--) {
			 //将堆顶与最后一个元素交换
//			 swap(arr[i],arr[0]);
			 arr[i]=arr[i]^arr[0];
			 arr[0]=arr[i]^arr[0];
			 arr[i]=arr[i]^arr[0];
			 //交换后维护堆顶,此时i代表剩余元素，将最后一个拿出
			 dadingdui(arr,i,0);
		 }
		 System.out.println(Arrays.toString(arr));
	}

	public static void main(String[] args) {
		int[] arr = {7,8,4,2,5,3,1,6,9,10};
		duipaixu(arr,arr.length);
		
	}

}