堆排序思想：
先让整个数组都变成大根堆结构，建立堆的过程：
1）从上到小的方法heapify()
2）从下到上的方法heapInsert()
把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始
堆的大小减少成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"); } }
