2018年12月23日

歸并排序

1，算法思想

遞歸法（自上而下）

申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針到達(dá)序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾

迭代法（自下而上）

將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成 $ceil(\frac{n}{2})$ (向上取整)個(gè)序列，排序后每個(gè)序列包含兩/一個(gè)元素
若此時(shí)序列數(shù)不是1個(gè)則將上述序列再次歸并，形成 $ceil(\frac{n}{4})$ 個(gè)序列，每個(gè)序列包含四/三個(gè)元素
重復(fù)步驟2，直到所有元素排序完畢，即序列數(shù)為1

2，算法圖解

3，算法實(shí)現(xiàn)

public class Merge<AnyType extends Comparable<? super AnyType>> {
    private AnyType[] aux;

    /**
     * 自上向下
     */
    public void sort(AnyType[] a) {
        aux = (AnyType[]) new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    public void sort(AnyType[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        /**
         * 因?yàn)樽笥也糠指髯杂行?         * 則只需a[mid]>a[mid+1], 才進(jìn)行排序
         */
        if (a[mid].compareTo(a[mid + 1]) > 0) {
            merge(a, lo, mid, hi);
        }
    }

    public void merge(AnyType[] a, int lo, int mid, int hi) {
        /**
         * i從左半部分開始
         * j從右半部分開始
         */
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        /**
         * 左右兩半部分各自有序
         * 若左半部分用盡，則直接取右半部分元素
         * 若右半部分用盡，則直接去左半部分元素
         * 若右半部分當(dāng)前元素小于左半部分當(dāng)前元素，則取右半部分元素
         * 若右半部分當(dāng)前元素大于左半部分當(dāng)前元素，則取左半部分元素
         */
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
            } else if (aux[j].compareTo(aux[i]) < 0) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

    /**
     * 自下向上
     * 比較適合用鏈表組織的數(shù)據(jù)
     */
    public void sortBU(AnyType[] a) {
        int N = a.length;
        aux = (AnyType[]) new Comparable[a.length];
        for (int sz = 1; sz < N; sz *= 2) {
            for (int lo = 0; lo < N - sz; lo += 2 * sz) {
                /**
                 * mid=lo+((lo+sz+sz-1)-lo)/2=lo+(sz+sz-1)/2=lo+sz-1
                 * 之所以使用Math.min, 是因?yàn)楫?dāng)N為奇數(shù)時(shí)的情況
                 */
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }

        }
    }
}

采用自上而下的方法其圖解：序列個(gè)數(shù)為偶數(shù)

當(dāng)序列的個(gè)數(shù)為奇數(shù)時(shí)：

采用自下而上的方法其圖解：當(dāng)序列個(gè)數(shù)為偶數(shù)時(shí)

當(dāng)序列個(gè)數(shù)為奇數(shù)時(shí)：

4，復(fù)雜度分析

merge方法在將兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組時(shí)，需要借助額外的存儲(chǔ)空間，其空間復(fù)雜度為 $O(N)$ 。
merge方法在合并數(shù)組時(shí)，不改變相同元素間的前后順序，因此，歸并排序時(shí)穩(wěn)定的。
對(duì)N個(gè)數(shù)歸并排序的用時(shí)等于完成兩個(gè)大小為 $\frac{N}{2}$ 的遞歸排序所用時(shí)間加上合并所用的時(shí)間，對(duì)于merge方法，其時(shí)間復(fù)雜度為 $O(N)$ ，當(dāng) $N=1$ 時(shí)，歸并排序所用時(shí)間為常數(shù)，記為1，那么有：
$T(1)=1$
$T(N)=2T(\frac{N}{2})+N$
令 $N=\frac{N}{2}$ ，再將兩邊乘2，那么：
$2T(\frac{N}{2})=2(2T(\frac{N}{4})+\frac{N}{2})=4T(\frac{N}{4})+N$
因此可以得到：
$T(N)=4T(\frac{N}{4})+2N$
同理，令 $N=\frac{N}{4}$ ，并在兩邊乘4，那么：
$4T(\frac{N}{4})=4(2T(\frac{N}{8})+\frac{N}{4})=8T(\frac{N}{8})+N$
又可以得到：
$T(N)=8T(\frac{N}{8})+3N$
總結(jié)規(guī)律有：
$T(N)=2^kT(\frac{N}{2^k})+kN$
其中 $k=logN$
最后有：
$T(N)=NT(1)+NlogN=NlogN+N$
因?yàn)闅w并排序的執(zhí)行效率與待排序數(shù)組的有序程度無(wú)關(guān)，所以其時(shí)間復(fù)雜度是非常穩(wěn)定的，因此，無(wú)論是最好、最壞還是平均情況下的時(shí)間復(fù)雜度都為 $O(NlogN)$ 。

快速排序

1，算法思想

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。

步驟為：

從數(shù)列中挑出一個(gè)元素，稱為“基準(zhǔn)”（pivot），
重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分割結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分割（partition）操作。
遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到屬于它的位置去。

2，算法圖解

3，算法實(shí)現(xiàn)

public class Quick<AnyType extends Comparable<? super AnyType>> {
    public void sort(AnyType[] a) {
        sort(a, 0, a.length - 1);
    }

    private void sort(AnyType[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private int partition(AnyType[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        AnyType pivot = a[lo];
        int size = hi - lo + 1;
        if (size >= 3) {
            pivot = medianOfThree(a, lo, hi);
        }
        while (true) {
            while (a[++i].compareTo(pivot) < 0) {
                if (i == hi) {
                    break;
                }
            }
            while (pivot.compareTo(a[--j]) < 0) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }

    private AnyType medianOfThree(AnyType[] a, int lo, int hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[lo].compareTo(a[hi]) > 0) {
            swap(a, lo, hi);
        }
        if (a[mid].compareTo(a[hi]) > 0) {
            swap(a, mid, hi);
        }
        if (a[mid].compareTo(a[lo]) > 0) {
            swap(a, mid, lo);
        }
        return a[lo];
    }

    private void swap(AnyType[] a, int i, int j) {
        AnyType temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

4，復(fù)雜度分析

最好的情況最多需要 $O(logN)$ 次的嵌套遞歸調(diào)用，所以它需要 $O(logN)$ 的空間。最壞情況下需要 $O(N)$ 次嵌套遞歸調(diào)用，因此需要 $O(N)$ 的空間。
如圖，以3位基準(zhǔn)，兩個(gè)1前后順序改變了，因此快速排序時(shí)不穩(wěn)定的

快速排序的運(yùn)行時(shí)間等于兩個(gè)遞歸調(diào)用的運(yùn)行時(shí)間加上partition方法運(yùn)行時(shí)間：
$T(N)=T(i)+T(N-i-1)+N$
$令T(0)=T(1)=1$

最好情況下，基準(zhǔn)pivot正好位于中間，那么 $T(N)=2T(\frac{N}{2})+N$ ，該情況與上面歸并排序分析相同，那么快速排序在最好情況下的時(shí)間復(fù)雜度為 $O(NlogN)$ 。
最壞情況下，每次選取的基準(zhǔn)pivot為最小元素，此時(shí) $i=0$
$T(N)=T(N-1)+N$
$T(N-1)=T(N-2)+N-1$
$T(N-2)=T(N-3)+N-3$
$……$
$T(2)=T(1)+2$
將兩邊相加后得到：
$T(N)=\sum_{i=1}^{N}i=\frac{N(N-1)}{2}$
因此，最壞情況下快速排序的時(shí)間復(fù)雜度為 $O(N^2)$ 。為了避免這種極端情況，盡量避免基準(zhǔn)pivot為最小元素，可以采用三數(shù)取中來(lái)選取pivot，即上述medianOfThree方法，該方法取頭中尾三個(gè)數(shù)之間的中位數(shù)。
平均情況下，選取基準(zhǔn)大小概率為 $\frac{1}{N}$ ,那么 $T(i)$ 的平均值為 $\frac{1}{N}\sum_{j=0}^{N-1}T(j)$ ，那么
$T(N)=T(i)+T(N-i-1)+N=\frac{2}{N}\sum_{j=0}^{N-1}T(j)+N$
那么：
$NT(N)=2\sum_{j=0}^{N-1}T(j)+N^2$
$(N-1)T(N-1)==2\sum_{j=0}^{N-2}T(j)+(N-1)^2$
由上面式子可得：
$NT(N)-(N-1)T(N-1)=2T(N-1)+2N-1$
$NT(N)=(N+1)T(N-1)+2N$
又可以得到：
$\frac{T(N)}{N+1}=\frac{T(N-1)}{N}+\frac{2}{N+1}$
$\frac{T(N-1)}{N}=\frac{T(N-2)}{N-1}+\frac{2}{N}$
$\frac{T(N-2)}{N-1}=\frac{T(N-3)}{N-2}+\frac{2}{N-1}$
$……$
$\frac{T(2)}{3}=\frac{T(1)}{2}+\frac{2}{3}$
最終可得：
$\frac{T(N)}{N+1}=\frac{T(1)}{2}+2\sum_{i=3}^{N+1}\frac{1}{i}=ln(N+1)+\gamma-\frac{3}{2}$
其中 $\gamma\approx0.577$ 叫做歐拉常數(shù)，于是
$\frac{T(N)}{N+1}=O(logN)$
$T(N)=O(NlogN)$
所以快速排序的平均時(shí)間復(fù)雜度為 $O(NlogN)$ 。

5，應(yīng)用

LeetCode 215.數(shù)組中第K個(gè)最大元素 
在未排序的數(shù)組中找到第 k 個(gè)最大的元素。
請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。

示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5

示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4

使用快速排序思想，將K左右兩邊分區(qū)，大的在左邊，小的在右邊

public class FindKthLargest {
    public static int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return Integer.MAX_VALUE;
        }
        return findKthLargest(nums, 0, nums.length - 1, k-1);
    }

    private static int findKthLargest(int[] nums, int start, int end, int k) {
        if (start > end) {
            return Integer.MAX_VALUE;
        }
       
        int pivot = nums[end];
        int left = start;
        for (int i = start; i < end; i++) {
            if (nums[i] > pivot) {
                swap(nums, left++, i);
            }
        }
        swap(nums, left, end);

        if (left == k) {
            return nums[left];
        } else if (left < k) {
            return findKthLargest(nums, left + 1, end, k);
        } else {
            return findKthLargest(nums, start, left - 1, k);
        }

    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

第一次分區(qū)查找，需要對(duì)大小為 $N$ 的數(shù)組進(jìn)行分區(qū)，即需要遍歷n個(gè)元素，平均情況下，在第二次分區(qū)查找時(shí)，需要對(duì)大小為 $\frac{N}{2}$ 的數(shù)組進(jìn)行分區(qū)，以此類推，分區(qū)遍歷元素的個(gè)數(shù)分別為 $N$ 、 $\frac{N}{2}$ 、 $\frac{N}{4}$ ……1，我們知道等比數(shù)列求和公式：
$S_n=\frac{a_1(1-q^n)}{1-q}$
令 $N=2^k$ ，那么：
$N+\frac{N}{2}+\frac{N}{4}+……+1$
$=2^k+\frac{2^k}{2}+\frac{2^k}{4}+……+1$
$=2^k+2^{k-1}+2^{k-2}+……+1$
$=2^{k+1}-1=2N-1$
所以該方法的時(shí)間復(fù)雜度為 $O(2N-1)=O(N)$ 。