堆排序算法

首先我们需要了解大根堆的概念，如果一个数 他的左右子节点的值都比他小，那么就可以称作大根堆

1.我们需要知道如何生成大根堆，遍历一个数组中所有的数，每个数都与它的父节点比较如果大于父节点，那么就和父节点更换再数组中的位置，直到它比父节点小或者没有父节点的时候结束，下面是代码：

	public static void heapInsert(int arr[],int index){
		while(arr[index]>arr[(index-1)/2]){
			swap(arr,index,(index-1)/2);
			index=(index-1)/2;//因为换位置过后可能它还是比父节点大 所以还要判断
		}
	}
	public static void swap(int arr[],int index1,int index2){
		int temp=arr[index1];
		arr[index1]=arr[index2];
		arr[index2]=temp;
	}

2.当大根堆取出最大的是(我们知道它是整体有序的，虽然左右子节点的大小不定，但是父节点的数一定是最大的)，所以数组的0位置所在的数就是最大的，即根节点的数是最大的，当我们取出这个数以后我们需要做的事情就是，把最后一个位置的数放入0位置，然后将该数的左右子节点比较，取最大的，然后与他比较，如果比他大那么和他更换位置，如果比他小那么不做更改，位置修改好过后再由之前更换数值的位置开始与它的子节点重复此操作，知道它比子节点大为止，他们就又形成了大根堆。

//将最大值返回给用户   并且删除掉最大值  heapsize是我的数组的有效长度    这个函数的代表某个数在index的时候能否往下移动
	public static void heapify(int arr[],int index,int heapsize){
		int left=index*2+1;//左子节点
		while(left<heapsize){//当它还有子节点的时候
			//1.先找出较大的子节点
			int maxNum= (arr[left]<arr[left+1] && ((left+1)<heapsize))? left+1 : left;
			//2.较大的子节点再与父节点比较  如果大一些 就和父节点换位置  同时再去看它的下一个子节点
			//System.out.println(maxNum+" " +arr[left]+" "+arr[left+1]);
			if(arr[maxNum]<arr[index]){
				break;
			}
			swap(arr,maxNum,index);
			index=maxNum;
			left=index*2+1;
		}
	}

3.堆排序 我们知道大根堆的根节点的值永远是整棵树最大的值 那么我们需要做的就是每次拍好大根堆过后将它0位置的数放到最后，并且用一个值heapsize来表示堆的有效长度，放到最后过后heapsize-1，表示我的堆将最后那个位置的值作为无效的值，不使用它，然后执行我们上面的第二步的操作，再次排序成为大根堆，继续取值，知道我们的heapsize值==0的时候我们的整个数组就成为一个有序的数组了

//堆排序的思想  先将数组整合为大根堆 然后取0位置的数与最后位置的数做交换 同时heapsize--
//然后将0位置上的数进行heapify操作  操作完以后又形成了大根堆 继续将0位置的数与堆最后位置的数做交换
//周而复始  我们每次将最大值取出  到最后 就会形成一个排好序的数组
public static void heapSort(int arr[]){
	int heapsize=0;//heapsize代指 堆的有效长度
	for(heapsize=0;heapsize<arr.length;heapsize++){//先将整个数组整合称为大根堆
		heapInsert(arr,heapsize);
	}
	swap(arr,0,--heapsize);
	while(heapsize>0){
		heapify(arr,0,heapsize);
		swap(arr,0,--heapsize);
	}
}

我们堆排序的时间复杂度，由于每次操作一个数将它放到正确的位置我们就是将它向它上一个高度的数之间进行替换，所以它的复杂度为O(n*logn)