堆排序

1. 整体思路

和选择排序是一样的，首先在所有元素中选出最大的元素放在最后的位置，然后在剩下的元素中选出最大的放在倒数第二的位置，……，以此类推，直到剩下一个与元素为止。

2. 算法过程

1. 首先把待排序的数组原地调整成一个堆结构，什么？不知道堆数据结构，可以看这篇文章；

2. 假设数组需要从小到大排序，我们使用大顶堆来完成。数组调整成堆可以使用heapify，线性时间复杂度。

3. 只要堆中的元素个数（size）大于1，执行下面的逻辑

   3.1. 把堆顶元素和数组中下标为size-1的元素做交换；

   3.2. size–；

   3.3. 对堆顶元素做heapify操作，调整堆。

3. 代码

Java

import java.util.*;

public class HeapSort {
    
    public static void main(String[] args) {
        int times = 100_0000, maxArraySize = 1000;
        Random r = new Random();
        while(times-- > 0) {
            int len = r.nextInt(maxArraySize);
            int[] arr1 = new int[len], arr2 = new int[len];
            for(int i = 0; i < len; ++i) arr1[i] = arr2[i] = r.nextInt(21) - 10;
            Arrays.sort(arr1);
            heapSort(arr2);
            for(int i = 0; i < len; ++i) {
                if(arr1[i] != arr2[i]) {
                    for(i = 0; i < len; ++i) System.out.print(arr1[i] + ",");
                    System.out.println();
                    for(i = 0; i < len; ++i) System.out.print(arr2[i] + ",");
                    System.out.println();
                    throw new RuntimeException();
                }
            }
        }
	}
    
    public static void heapSort(int[] arr) {
    	int i,len = arr.length;
        for(i = (len >> 1) - 1; i > -1; --i) heapIfy(arr,len,i); // 创建大顶堆
        for(i = len; i > 1;) {// i就是堆的size
            swap(arr,0,--i);
            heapIfy(arr,i,0);
        }
    }
    
    public static void heapIfy(int[] heap, int size, int index) {
        // 堆的元素个数是size，对下标为index的元素做heapify操作
        int child, bound = size >> 1, v = heap[index];
        while(index < bound) {
            child = (index << 1) + 1;
            if(child + 1 < size && heap[child + 1] > heap[child]) ++child;
            if(v >= heap[child]) break;
            heap[index] = heap[child];
            index = child;
        }
        heap[index] = v;
    }
    
    public static void swap(int[] arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}