[数据结构与算法]堆排序，，

堆排序思想：

1. 先让整个数组都变成大根堆结构，建立堆的过程：
   1）从上到小的方法heapify()
   2）从下到上的方法heapInsert()
2. 把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始
3. 堆的大小减少成0之后，排序完成

如果只要求数组组织成堆结构（大根堆或小根堆），并不要求有序的话，在一次性给出所有数的前提下，建成堆的时间复杂度可以优化为O(N)
如果用户不是一次性给出所有数，而是一个一个数给，那么，建成堆的时间复杂度只能为O(N*logN)

package com.harrison.class04;

import java.util.Arrays;

public class Code02_HeapSort {
	public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
//		for(int i=0; i<arr.length; i++) {
//			heapInsert(arr, i);
//		}
		// 时间复杂度优化为O(N)
		for(int i=arr.length-1; i>=0; i--) {
			heapify(arr, i, arr.length);
		}
		int heapSize=arr.length;
		swap(arr, 0, --heapSize);
		while(heapSize>0) {
			heapify(arr, 0, heapSize);
			swap(arr, 0, --heapSize);
		}
	}
	
	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 heapify(int[] arr,int index,int heapSize) {
		int left=2*index+1;
		while(left<heapSize) {
			int largest=(left+1<heapSize && arr[left+1]>arr[left])?left+1:left;
			int allLargest=arr[largest]>arr[index]?largest:index;
			if(allLargest==index) {
				break;
			}
			swap(arr, allLargest, index);
			index=allLargest;
			left=2*index+1;
		}
	}
	
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i]; 
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		int testTimes=100000;
		int maxSize=100;
		int maxValue=100;
		boolean succeed=true;
		for(int i=0; i<testTimes; i++) {
			int[] arr1=generateRandomArray(maxSize, maxValue);
			int[] arr2=copyArray(arr1);
			heapSort(arr1);
			comparator(arr2);
			if(!isEqual(arr1, arr2)) {
				succeed=false;
				printArray(arr1);
				printArray(arr2);
				break;
			}
		}
		System.out.println(succeed?"Nice":"Oops");
	}
}