堆排序

给定数组创建一个最大堆或者最小堆然后进行排序，分为两个步骤，根据数组创建最大堆，然后堆排序

最大堆适用于升序，最小堆适用于降序

 1 package everySort;
 2 
 3 public class MaxHeapSort {
 4     public static void main(String[] args) {
 5             int arr[] = {4, 6, 8, 5, 9};
 6             sort(arr);
 7             for(int i : arr){
 8                 System.out.print(i + " ");
 9             }
10      }
11      public static void sort(int[] nums){
12         //根据数组找到第一个非叶子节点，就是 nums.length / 2 - 1
13         for(int i = nums.length / 2 - 1; i >= 0; i--){
14             //构建最大堆
15             heapSort(nums, i, nums.length);
16         }
17 
18         for(int j = nums.length - 1; j > 0 ; j--){
19             swap(nums, 0, j);
20             heapSort(nums, 0 , j);
21         }
22      }
23     public static void heapSort(int[] arr, int i, int len){
24 
25         int k = 2 * i +1;
26         int temp = arr[i];
27         if(k < len - 1 && arr[k] < arr[k + 1]){
28             k ++;
29         }
30         if(k < len && arr[k] > arr[i]){
31             System.out.println("i :" + i + "-->k :" + k);
32             arr[i] = arr[k];
33             arr[k] = temp;
34             i = k;
35             //替换后点子节点要进行检查
36             heapSort(arr, i, len);
37         }
38     }
39     public static void swap(int arr[], int i, int j){
40         int temp = arr[i];
41         arr[i] = arr[j];
42         arr[j] = temp;
43     }
44 }

MaxHeap

 1 package everySort;
 2 
 3 public class MinHeapSort {
 4     public static void main(String[] args) {
 5         int[] nums = {4, 6, 8, 5, 9};
 6         sort(nums);
 7         for(int j : nums){
 8             System.out.print(j + " ");
 9         }
10     }
11     public static void sort(int[] nums){
12         //根据数组找到第一个非叶子节点，就是 nums.length / 2 - 1
13         for(int i = nums.length / 2 - 1; i >= 0; i--){
14             //构建最小堆
15             heapSort(nums, i, nums.length);
16         }
17         for(int j = nums.length - 1; j > 0; j--){
18             swap(nums, 0, j);
19             heapSort(nums, 0, j);
20         }
21 
22     }
23     public static void heapSort(int[] nums, int i, int len){
24         int k = 2 * i + 1;
25         int temp = nums[i];
26         if(k < len - 1 && nums[k] > nums[k + 1]){
27             k ++;
28         }
29         if(k < len && nums[k] < nums[i]){
30             nums[i] = nums[k];
31             nums[k] = temp;
32             i = k;
33             heapSort(nums, i, len);
34         }
35     }
36     public static void swap(int[] nums, int i, int j){
37         int temp = nums[i];
38         nums[i] = nums[j];
39         nums[j] = temp;
40     }
41 }

MinHeap