堆及堆排序、快速排序、归并排序

Java构建堆，以及实现堆排序，堆实质是一棵完全二叉树，这里用数组表示
一个完全二叉树，即堆，堆可分为小顶堆、大顶堆，堆化可分为从上到下和
从下到上两种方式。
public static class Heap{
   private List<Integer> list = new ArrayList<>();    public void build(Integer[] arr) {        //堆其实质是一个完全二叉树 用数组表示时 i节点对应的左子节点为2i，右子节点为2i+1        //假设数组长度为n 则n-1标的父节点为 (n-1)/2  因此 (n-1)/2+1 到 n-1节点均为叶子节点 不需要堆化 我们只需要堆化0到(n-1)/2的元素        for(int i=arr.length-1/2; i>=0; i--) {            heapify(arr, arr.length-1, i);        }        this.list = new ArrayList<>(Arrays.asList(arr));    }
    /**     * 插入的核心思想是 将元素先追加到数组后面 然后从下向上进行堆化     * @param val     */    public void insert(int val) {        list.add(val);        int pos = list.size() - 1;        //父节点的index > 0 and 父节点的值小于当前子节点的值        while ((pos-1)/2 >= 0 && list.get(pos) > list.get((pos-1)/2)) {            int parent = (pos-1)/2;            //子节点和父节点的数据做交换            swap(pos, parent);            //设置当前位移为父节点 继续向上堆化            pos = parent;        }    }
    /**     * 数据交换     * @param a     * @param b     */    private void swap(int a, int b) {        int temp = list.get(a);        list.set(a, list.get(b));        list.set(b, temp);    }
    /**     * 删除堆顶元素     * 思路是将堆顶元素删除，然后将排在最后的元素移到堆顶     */    public int removeMax() {        int max = list.get(0);        //数据交换        swap(0, list.size() - 1);        list.remove(list.size()-1);        //数组转化        Integer[] arr = list.toArray(new Integer[list.size()]);        //从上到下堆化        heapify(arr, list.size() - 1, 0);        this.list = new ArrayList<>(Arrays.asList(arr));        return max;    }}
/** * 堆排序 */public static void sort(Integer arr[]) {
    //1.先构建堆    buildHeap(arr);
    //2.再排序    int k = arr.length-1;    while (k > 0) {        //将堆顶元素和最后的元素进行交换 将最大的元素沉底        swap(arr, 0, k);        //对0到k-1的元素重新堆化 因为堆顶现在不是最大的数了        heapify(arr, --k, 0);    }    printAll(arr);}
public static void printAll(Integer arr[]) {    for (int i : arr) {        System.out.print(i + ", ");    }}
/** * 一个无序数组 构建一个堆 * @param arr */public static void buildHeap(Integer[] arr) {    //堆其实质是一个完全二叉树 用数组表示时 i节点对应的左子节点为2i，右子节点为2i+1    //假设数组长度为n 则n-1标的父节点为 (n-1)/2  因此 (n-1)/2+1 到 n-1节点均为叶子节点 不需要堆化 我们只需要堆化0到(n-1)/2的元素    for(int i=arr.length-1/2; i>=0; i--) {        heapify(arr, arr.length-1, i);    }}
/** * 从上到下堆化 * @param arr * @param i */public static void heapify(Integer[] arr, int n, int i) {    while (true) {        int maxPos = i;        //当前节点和左子节点比较        if(2*i+1 <= n && arr[maxPos] < arr[2*i + 1]) {            maxPos = 2*i+1;        }        //当前节点和右子节点比较        if(2*i+2 <= n && arr[maxPos] < arr[2*i + 2]) {            maxPos = 2*i+2;        }        //如果当前节点大于左右子节点 则结束循环        if(maxPos == i) {            break;        }        swap(arr, maxPos, i);        i = maxPos;    }}
public static void swap(Integer[] arr, int a, int b) {    int temp = arr[a];    arr[a] = arr[b];    arr[b] = temp;}
快排和归并排序：
public static void quickSort(int[] arr) {        quickSort(arr, 0, arr.length - 1);    }
    /**     * 快速排序     * 1：以第一个数为中位数，比中位数大的数移动到中位数左边，比中位数小的数移动到中位数右边 最后返回中位数的下标     * 2：接着递归排序[0-中位数下标]和[中位数下标+1，length-1] 两个子集 直到 low >= high 退出循环     * @param arr     */    public static void quickSort(int[] arr, int low, int high) {
        if(arr == null || arr.length <= 1 || low >= high) {            return;        }
        int midIndex = partition(arr, low, high);
        quickSort(arr, low, midIndex);
        quickSort(arr, midIndex + 1, high);    }
    /**     * 找到中位数下标     * @param arr     * @param low     * @param high     * @return     */    public static int partition(int[] arr, int low, int high) {        int midValue = arr[low];        while (low < high) {            //从右向左移动            while (low < high && arr[high] >= midValue) {                high--;            }            if(low < high) {                arr[low] = arr[high];                low++;            }            while (low < high && arr[low] <= midValue) {                low++;            }            if(low < high) {                arr[high] = arr[low];                high--;            }        }        arr[low] = midValue;        return low;    }
    public static void swap(int[] arr, int low, int high) {        int temp = arr[low];        arr[low] = arr[high];        arr[high] = temp;    }
    public static void mergeSort(int[] arr) {        mergeSort(arr, 0, arr.length - 1);    }
    public static void mergeSort(int[] arr, int low, int high) {
        if(low >= high) {            return;        }
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid+1, high);
        mergeArr(arr, low, mid, high);    }
    public static void mergeArr(int[] arr, int low, int mid, int high){        if(low >= high) {            return;        }        int i=0,j = 0,k=0;        int arrTemp[] = new int[high - low + 1];
        while (low + i <= mid || high >= mid + 1 + j) {
            if(low + i <= mid && arr[low + i] <= arr[mid + 1 + j]) {                arrTemp[k++] = arr[low + i];                i++;            }            if(low + i > mid) {                while (mid + 1 + j <= high) {                    arrTemp[k++] = arr[mid + 1 + j];                    j++;                }                break;            }            if(mid + 1 + j <= high && arr[low + i] > arr[mid + 1 + j]) {                arrTemp[k++] = arr[mid + 1 + j];                j++;            }
            if(mid + 1 + j > high) {                while (low + i <= mid) {                    arrTemp[k++] = arr[low + i];                    i++;                }                break;            }        }
        for (int a=0; a<arrTemp.length; a++) {            arr[low + a] = arrTemp[a];        }    }