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

Java構(gòu)建堆，以及實(shí)現(xiàn)堆排序，堆實(shí)質(zhì)是一棵完全二叉樹(shù)，這里用數(shù)組表示
一個(gè)完全二叉樹(shù)，即堆，堆可分為小頂堆、大頂堆，堆化可分為從上到下和
從下到上兩種方式。
public static class Heap{
   private List<Integer> list = new ArrayList<>();    public void build(Integer[] arr) {        //堆其實(shí)質(zhì)是一個(gè)完全二叉樹(shù) 用數(shù)組表示時(shí) i節(jié)點(diǎn)對(duì)應(yīng)的左子節(jié)點(diǎn)為2i，右子節(jié)點(diǎn)為2i+1        //假設(shè)數(shù)組長(zhǎng)度為n 則n-1標(biāo)的父節(jié)點(diǎn)為 (n-1)/2  因此 (n-1)/2+1 到 n-1節(jié)點(diǎn)均為葉子節(jié)點(diǎn) 不需要堆化 我們只需要堆化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));    }
    /**     * 插入的核心思想是 將元素先追加到數(shù)組后面 然后從下向上進(jìn)行堆化     * @param val     */    public void insert(int val) {        list.add(val);        int pos = list.size() - 1;        //父節(jié)點(diǎn)的index > 0 and 父節(jié)點(diǎn)的值小于當(dāng)前子節(jié)點(diǎn)的值        while ((pos-1)/2 >= 0 && list.get(pos) > list.get((pos-1)/2)) {            int parent = (pos-1)/2;            //子節(jié)點(diǎn)和父節(jié)點(diǎn)的數(shù)據(jù)做交換            swap(pos, parent);            //設(shè)置當(dāng)前位移為父節(jié)點(diǎn) 繼續(xù)向上堆化            pos = parent;        }    }
    /**     * 數(shù)據(jù)交換     * @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);        //數(shù)據(jù)交換        swap(0, list.size() - 1);        list.remove(list.size()-1);        //數(shù)組轉(zhuǎn)化        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.先構(gòu)建堆    buildHeap(arr);
    //2.再排序    int k = arr.length-1;    while (k > 0) {        //將堆頂元素和最后的元素進(jìn)行交換 將最大的元素沉底        swap(arr, 0, k);        //對(duì)0到k-1的元素重新堆化 因?yàn)槎秧敩F(xiàn)在不是最大的數(shù)了        heapify(arr, --k, 0);    }    printAll(arr);}
public static void printAll(Integer arr[]) {    for (int i : arr) {        System.out.print(i + ", ");    }}
/** * 一個(gè)無(wú)序數(shù)組 構(gòu)建一個(gè)堆 * @param arr */public static void buildHeap(Integer[] arr) {    //堆其實(shí)質(zhì)是一個(gè)完全二叉樹(shù) 用數(shù)組表示時(shí) i節(jié)點(diǎn)對(duì)應(yīng)的左子節(jié)點(diǎn)為2i，右子節(jié)點(diǎn)為2i+1    //假設(shè)數(shù)組長(zhǎng)度為n 則n-1標(biāo)的父節(jié)點(diǎn)為 (n-1)/2  因此 (n-1)/2+1 到 n-1節(jié)點(diǎn)均為葉子節(jié)點(diǎn) 不需要堆化 我們只需要堆化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;        //當(dāng)前節(jié)點(diǎn)和左子節(jié)點(diǎn)比較        if(2*i+1 <= n && arr[maxPos] < arr[2*i + 1]) {            maxPos = 2*i+1;        }        //當(dāng)前節(jié)點(diǎn)和右子節(jié)點(diǎn)比較        if(2*i+2 <= n && arr[maxPos] < arr[2*i + 2]) {            maxPos = 2*i+2;        }        //如果當(dāng)前節(jié)點(diǎn)大于左右子節(jié)點(diǎn) 則結(jié)束循環(huán)        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：以第一個(gè)數(shù)為中位數(shù)，比中位數(shù)大的數(shù)移動(dòng)到中位數(shù)左邊，比中位數(shù)小的數(shù)移動(dòng)到中位數(shù)右邊 最后返回中位數(shù)的下標(biāo)     * 2：接著遞歸排序[0-中位數(shù)下標(biāo)]和[中位數(shù)下標(biāo)+1，length-1] 兩個(gè)子集 直到 low >= high 退出循環(huán)     * @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);    }
    /**     * 找到中位數(shù)下標(biāo)     * @param arr     * @param low     * @param high     * @return     */    public static int partition(int[] arr, int low, int high) {        int midValue = arr[low];        while (low < high) {            //從右向左移動(dòng)            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];        }    }