堆排序

  1 package my_basic;
  2 
  3 import java.util.Arrays;
  4 
  5 public class HeapSort {
  6     
  7     public static void heapSort(int[] arr) {
  8         if (arr == null || arr.length <2) {
  9             return;
 10         }
 11         //建堆
 12         for (int i = 0; i < arr.length; i++) {
 13             heapInsert(arr,i);
 14         }
 15         int size = arr.length;
 16         swap(arr, 0, --size);
 17         
 18         /*调整堆*/
 19         while ( size > 0 ) {
 20             heapify(arr, 0, size);
 21             swap(arr, 0, --size);
 22         }
 23     }
 24 
 25     public static void heapInsert(int[] arr, int index) {
 26         while (arr[index] > arr[(index-1)/2]) {
 27             swap(arr,index,(index-1)/2);
 28             index = (index-1)/2;
 29         }
 30     }
 31     
 32     public static void swap(int[] arr, int i, int j) {
 33         int tmp = arr[i];
 34         arr[i] = arr[j];
 35         arr[j] = tmp;
 36         
 37     }
 38     /**
 39      * 调整堆
 40      * @param arr
 41      * @param index  要开始调整的位置
 42      * @param heapSize  标记越界
 43      */
 44     public static void heapify(int[] arr, int index, int heapSize) {
 45         int left = index * 2 + 1;
 46         while (left < heapSize) {
 47             int large = ((left+1) < heapSize && arr[left+1]>arr[left])
 48                     ? left+1
 49                     : left;
 50             large = arr[large] > arr[index] ? large : index;
 51             if (large == index) {
 52                 break;
 53             }
 54             swap(arr, large, index);
 55             index = large;
 56             left = index * 2 + 1;
 57         }
 58     }
 59     
 60     public static int[] generateRandomArray(int maxSize, int maxValue) {
 61         int[] arr = new int[(int) ((maxSize+1) * Math.random())];
 62         for (int i = 0; i < arr.length; i++) {
 63             arr[i] = (int) ((maxValue+1) * Math.random() - (maxValue) * Math.random());
 64         }
 65         return arr;
 66     }
 67     public static int[] copyArray(int[] arr1) {
 68         int[] arr2 = new int[arr1.length];
 69         for (int i = 0; i < arr1.length; i++) {
 70             arr2[i] = arr1[i];
 71         }
 72         return arr2;
 73         
 74     }
 75     public static void comparator(int[] arr2) {
 76         Arrays.sort(arr2);
 77         
 78     }
 79     public static boolean isEqual(int[] arr1, int[] arr2) {
 80         if ((arr1==null && arr2!=null) || ((arr1!=null && arr2==null))) {
 81             return false;
 82         }
 83         if (arr1.length != arr2.length) {
 84             return false;
 85         }
 86         for (int i = 0; i < arr2.length; i++) {
 87             if (arr1[i] != arr2[i]) {
 88                 return false;
 89             }
 90         }
 91         return true;
 92     }
 93     
 94     public static void main(String[] args) {
 95         int testTime = 500000;
 96         int maxSize = 100;
 97         int maxValue = 100;
 98         boolean succeed = true;
 99         for (int i = 0; i < testTime; i++) {
100             int[] arr1 = generateRandomArray(maxSize, maxValue);
101             int[] arr2 = copyArray(arr1);
102             heapSort(arr1);
103             comparator(arr2);
104             if (!isEqual(arr1, arr2)) {
105                 succeed = false;
106                 break;
107             }
108         }
109         System.out.println(succeed ? "Nice!" : "Fucking fucked!");
110 
111     }
112 
113 }