思想：
堆排序最主要在于构建堆这个数据结构上，构建好堆后，排序工作主要是插入，取出等操作。堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

构建堆的两个最主要操作是 shiftUp（） 、 shiftDown（）。

public class QuickSort {

    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int j = partition(arr, l, r);
        quickSort(arr, l, j - 1);
        quickSort(arr, j + 1, r);
    }

    private static int partition(int[] arr, int l, int r) {
        //第一个优化：解决数组基本有序的情况下，快排时间复杂度O(n^2)
        int k = (int) Math.random() * (r - l + 1) + l;
        swap(arr, l, k);

        int i = l + 1;
        int j = r;
        int val = arr[l];
        while (true) {
            while (i <= r && arr[i] < val) {
                i++;
            }

            while (j >= l + 1 && arr[j] > val) {
                j--;
            }

            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;

    }

    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

}