堆排序宇宙最简单版本

 1 package com.array;
 2 
 3 import java.util.Arrays;
 4 
 5 public class HeapSort {
 6     public static void main(String[] args) {
 7         int[] a = {45,14,5,24,5,62,7,84,34,14};
 8         buildHeap(a);
 9 
10         System.out.println(Arrays.toString(a));
11         heapSort(a);
12         System.out.println(Arrays.toString(a));
13     }
14     public static void heapSort(int[] arr) {
15         buildHeap(arr);
16         for (int i = arr.length - 1; i >= 0; i--) {
17             swap(arr, 0, i);
18             heapfy(arr, 0, i-1);
19         }
20     }
21 
22     public static void buildHeap(int[] arr) {
23         for (int i = arr.length / 2 - 1; i >= 0; i--) {
24             heapfy(arr, i, arr.length - 1);
25         }
26     }
27 
28     public static void heapfy(int[] arr, int root, int limit) {
29         int lson = 2 * root + 1;
30         int rson = 2 * root + 2;
31         int temp;
32         if (lson <= limit && rson <= limit) {
33             temp = arr[lson] > arr[rson] ? lson : rson;
34         } else if (lson <= limit) {
35             temp = lson;
36         } else if (rson <= limit) {
37             temp = rson;
38         } else return;
39 
40         if (arr[temp] > arr[root]) {
41             swap(arr, temp, root);
42             heapfy(arr, temp, limit);
43         }
44     }
45 
46 
47     public static void swap(int[] arr, int i, int j) {
48         int temp = arr[i];
49         arr[i] = arr[j];
50         arr[j] = temp;
51     }
52 }