堆排序

对于堆，简单的来说就是一个完全二叉树。

堆可以分为大根堆和小根堆。

先看大根堆。

大根堆就是在每一个子节点下都有最大的值放在节点上。

小根堆就是每一个子节点的最小值放在节点上。

看下大根堆的实现代码

public static void Sort(int[] arr){
		for (int i = 0; i < arr.length; i++) {
			insertSort(arr,i);
		}
	}
	public static void insertSort(int[] arr , int index){
		while(arr[index]>arr[(index - 1) / 2]){ //判断进来的index下标的值是否比它的父节点大，如果大执行下面的操作
			swap(arr, index, (index - 1) / 2);//index下标的值和父节点的值交换
			index = (index - 1 ) / 2 ;  //index和父节点交换
		}
	}

再看小根堆实现代码

public static void heapify(int[] arr, int index, int size) {
		int left = index * 2 + 1;   //找到左孩子
		while (left < size) {//判断是否存在子节点
			int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;  //判断是否有右节点，有就和左节点比较，返回大的下标。
			largest = arr[largest] > arr[index] ? largest : index;  //把得到的左右孩子较大的那个和父节点比较，返回大的下标
			if (largest == index) { //如果index 大于等于子孩子，退出循环。
				break;
			}
			swap(arr, largest, index);  //交换
			index = largest;
			left = index * 2 + 1; 
		}
	}

知道了大根堆和小根堆的实现，现在来看堆排序的实现。

package com.堆;

public class HeadSort {
	public static void Sort(int[] arr){
		for (int i = 0; i < arr.length; i++) {
			insertSort(arr,i);
		}
	}
	public static void insertSort(int[] arr , int index){
		while(arr[index]>arr[(index - 1) / 2]){ //判断进来的index下标的值是否比它的父节点大，如果大执行下面的操作
			swap(arr, index, (index - 1) / 2);//index下标的值和父节点的值交换
			index = (index - 1 ) / 2 ;  //index和父节点交换
		}
	}
	public static void swap(int[] arr, int i ,int j){
		int temp = arr[i] ;
		arr[i] = arr[j] ;
		arr[j] = temp ;
	}
	public static void heapify(int[] arr, int index, int size) {
		int left = index * 2 + 1;   //找到左孩子
		while (left < size) {//判断是否存在子节点
			int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;  //判断是否有右节点，有就和左节点比较，返回大的下标。
			largest = arr[largest] > arr[index] ? largest : index;  //把得到的左右孩子较大的那个和父节点比较，返回大的下标
			if (largest == index) { //如果index 大于等于子孩子，退出循环。
				break;
			}
			swap(arr, largest, index);  //交换
			index = largest;
			left = index * 2 + 1; 
		}
	}
	public static void main(String[] args) {
		int[]  arr = new int[]{1,2,3,4,5,6,7};
		Sort(arr);
		int size = arr.length;
		swap(arr, 0, --size);
		while (size > 0) {
			heapify(arr, 0, size);
			swap(arr, 0, --size);
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+",");
		}
	}
}