普林斯頓《算法》筆記（二）

官方網站 官方代碼

第二章 排序

2.1 初級排序算法

排序就是将一組對象按照某種邏輯順序重新排列的過程。這裡我們主要關注重新排列含有元素的數組 (arrays of items)的算法，其中每個元素都有一個主鍵 (key)。排序算法的目的是重新排列所有元素，使得元素的主鍵能以某種方式排列。以下代碼是本章通用的排序算法模闆：

public class Example
{
    public static void sort(Comparable[] a)
    {   /*see text*/    }

    private static boolean less(Comparable v, Comparable w)
    { return v.compareTo(w) < 0; }

    private static void exch(Comparable[] a, int i, int j)
    { Comparable t = a[i]; a[i] = a[j]; a[j] = t; }

    private static void show(Comparable[] a)
    {
        for (int i = 0; i < a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }

    public static boolean isSorted(Comparable[] a)
    {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

    public static void main(String[] args)
    {
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}           

• 排序成本模型：在研究排序算法時，需要計算比較(compares) 和 交換(exchanges)的數量。對于不交換元素的算法，則計算通路數組 (array accesses)的次數。
• 排序算法可分為兩類：一種是無需額外記憶體的就地排序算法；一種是需要額外記憶體空間來存儲另一份數組副本的排序算法。

Comparable接口

此接口強行對實作它的每個類的對象進行整體排序。Java中的封裝數字的類型Integer和Double，以及String和其他許多進階資料類型都實作了Comparable接口，是以可以直接用這些類型的數組作為參數調用排序算法，如下圖快速排序調用數組a：

在建立自己的資料類型時，隻要實作Comparable接口就能保證用例代碼可以将其排序。要做到這一點，需要實作一個compareTo ()方法來定義目标類型對象的自然次序 。如下圖的Date資料類型：

compareTo() 方法 實作了對主鍵 (key) 的抽象 —— 對于任何實作了Comparable接口的資料類型，該方法定義了對象的大小順序。

選擇排序 (Selection Sort)

public class Selection
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for (i = 0; i < N; i++)
        {
            int min = i;
            for (j = i+1; j < N; j++)
                if (less(a[j], a[min]))  min = j;
            exch(a, i, min);
        }
    }
}           

對于長度為N的數組，選擇排序需要大約 \(~N^2/2\)次比較和N次交換。

選擇排序的特點：

1. 運作時間和輸入無關：一個以及排好序的數組或主鍵全部相等的數組和一個随機排列的數組所用的排序時間相同。
2. 資料移動是最少的：總共N次交換，交換次數和數組大小是線性關系，其他排序算法都不具備這個特征 (大多為線性對數或平方級别)。

插入排序 (Insert Sort)

public class Insertion
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for (int i = 1; i < N; i++)
        {
            for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
                exch(a, j, j-1);
        }
    }
}           

和選擇排序不同，插入排序所需的時間取決于輸入元素的初始順序，對一個很大且其中元素已經有序 (或接近有序) 的數組進行排序要比對随機數組或逆序數組進行排序要快得多。

提高插入排序速度的方式：在内循環中将較大的元素向右移動而不總是交換兩個元素(這樣通路數組的次數就能減半)。

public class InsertionX
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for (int i = 1; i < N; i++)
        {
            Comparable temp = a[i];
            for (j = i; j > 0 && less(temp, a[j-1]）; j--)
                a[j] = a[j-1];
        }
        a[j] = temp;
    }
}

// alternative way
public class InsertionX
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for (int i = 1; i < N; i++)
        {
            Comparable temp = a[i];
            int j = i;
            while (j > 0 && less(temp, a[j-1]))
            {
                a[j] = a[j-1];
                j--;
            }
            a[j] = temp;
        }
    }
}           

排序算法的比較

public class SortCompare
{
    public static double time(String alg, Comparable[] a)
    {
        Stopwatch timer = new Stopwatch();
        if (alg.equals("Insertion")) Insertion.sort(a);
        if (alg.equals("Selection")) Selection.sort(a);
        if (alg.equals("Shell"))     Shell.sort(a);
        if (alg.equals("Merge"))     Merge.sort(a);
        if (alg.equals("Quick"))     Quick.sort(a);
        if (alg.equals("Heap"))      Heap.sort(a);
        return timer.elapsedTime();
    }

    public static double timeRandomInput(String alg, int N, int T)
    {
        double total = 0.0;
        Double[] a = new Double[N];
        for (int t = 0; t < T; t++)
        {
            for (int i = 0; i < N; i++)
                a[i] = StdRandom.uniform();
            total += time(alg, a);
        }
        return total;
    }

    public static void main(String[] args)
    {
        String alg1 = args[0];
        String alg2 = args[1];
        int N = Integer.parseInt(args[2]);
        int T = Integer.parseInt(args[3]);
        double t1 = timeRandomInput(alg1, N, T);
        double t2 = timeRandomInput(alg2, N, T);
        StdOut.printf("For %d random Doubles\n   %s is", N, alg1);
        StdOut.printf(" %.1f times faster than %s\n", t2/t1, alg2);
    }
}


/**********************************************
% java SortCompare Insertion Selection 1000 100
For 1000 random Doubles
Insertion is 1.7 times faster than Selection
**********************************************/           

希爾排序 (Shell Sort)

希爾排序是插入排序的改進，插入排序的缺點是每次隻能交換相鄰的元素，若主鍵最小的元素恰好在數組的末尾，則需要N-1次移動。希爾排序的思想是通過交換不相鄰的元素使數組中任意間隔為h的元素都是有序的，并最終用插入排序将局部有序的數組排序。

public class Shell
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        int h = 1;
        while (h < N/3) h = 3*h + 1;
        while (h >= 1)
        {
            for (int i = h; i < N; i++)
            {
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                    exch(a, j, j-h)
            }
            h = h/3;
        }
    }
}


/********************************************
% java SortCompare Shell Insertion 100000 100
For 100000 random Doubles
Shell is 600 times faster than Insertion
*********************************************/           

2.2 歸并排序 (Mergesort)

歸并排序一般是 (遞歸地) 将數組分成兩半分别排序，然後将結果歸并起來。歸并排序的優點是所需的時間和 \(NlgN\) 成正比，這使得其優于選擇排序和插入排序。缺點是輔助數組所需的額外空間與N的大小成正比。歸并排序是分治 (divide-and-conquer) 思想的典型展現。

自上而下的歸并排序

public class Merge
{
    private static Comparable[] aux;

    public static void sort(Comparable[] a)
    {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid, hi);
    }

    public static boid merge(Comparable[] a, int lo, int mid, int hi)
    {
        int i = lo, j = mid+1;

        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++)
        if         (i > mid)              a[k] = aux[j++];
        else if    (j > hi)               a[k] = aux[i++];
        else if    (less(aux[j], aux[i])) a[k] = aux[j++];
        else                              a[k] = aux[i++];
    }

    private static boolean less(Comparable v, Comparable w)
    { return v.compareTo(w) < 0; }
}           

自下而上的歸并排序

public class MergeBU
{
    private static Comparable[] aux;

    public static void sort(Comparable[] a)
    {
        int N = a.length;
        aux = new Cmparable[N];
        for ( int sz = 1; sz < N; sz = sz+sz)
            for (int lo = 0; lo < N-sz; lo += sz+sz)
                merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
    }

    public staic boid merge(Comparable[] a, int lo, int mid, int hi)
    {
        int i = lo, j = mid+1;

        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++)
        if         (i > mid)              a[k] = aux[j++];
        else if    (j > hi)               a[k] = aux[i++];
        else if    (less(aux[j], aux[i])) a[k] = aux[j++];
        else                              a[k] = aux[i++];
    }

    private static boolean less(Comparable v, Comparable w)
    { return v.compareTo(w) < 0; }
}           

2.3 快速排序 (Quicksort)

在一般應用中快速排序都比其他排序算法快得多，除此之外快速排序是原地排序，所需時間和 \(NlgN\)成正比。主要缺點是非常脆弱，在實作時需要非常小心才能避免低劣的性能。

快速排序也是一種分治的排序算法。與歸并排序的差別：歸并排序将兩個子數組分别排序後，歸并前整個數組不是有序的；快速排序則是當子數組都有序時整個數組也就自然有序了。在歸并排序中，一個數組被分成兩半；快速排序中，切分 (partition) 的位置取決于數組的内容。

快速排序遞歸地将子數組 a[lo...hi] 排序，先用partition()方法将a[j] 放到一個合适位置，然後遞歸地将其他位置的元素排序。這裡的關鍵在于切分，切分後數組滿足三個條件：

1. 對于某個j，a[j] 在其最終位置
2. a[lo] 到 a[j-1] 的所有元素都不大于 a[j]
3. a[j+1] 到 a[hi] 的所有元素都不小于 a[j]

切分的實作方法：先取a[lo] 作為切分元素，然後從數組左端開始向右掃描直到找到一個大于等于它的元素，再從右端開始向左掃描知道找到一個小于等于它的元素，最後交換這兩個元素的位置。當兩個指針相遇時，将切分元素a[lo] 和左子數組最右側的元素 (a[j]) 交換，這樣切分值就留在a[j]中。

public class Quick
{
    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

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

    private static int partition(Comparable[] a, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while (true)
        {
            while (less(a[++i], v)) if (i == hi) break;
            while (less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
}           

• 上述快速排序的實作有一個潛在的缺點：在切分不平衡時可能會極為低效，達到平方級别。例如如果從最小的元素切分，第二次從第二小的元素切分，如此這般每次隻移除一個元素，這會導緻一個大數組需要切分很多次。是以快速排序前需要現将數組随機排序。
• 切換到插入排序： 對于小數組，快速排序比插入排序慢，是以可将上述算法中sort() 方法從

  if (hi <= lo) return;

  改為

  if (hi <= lo + M) { Insertion.sort(a, lo, hi); return; }

三向切分排序

當數組中存在大量重複元素時，快速排序的效率可以通過三向切分排序進一步改進，能将排序時間從線性對數級下降到線性級别。将數組分為三部分，分别對應小于、等于和大于切分元素的數組元素。使用Comparable 接口對a[i] 進行三向比較：

1. a[i] 小于v，将a[lt] 和 a[i] 交換，将 lt 和 i 加一
2. a[i] 大于v，将 a[gt] 和 a[i] 交換，将 gt 減一
3. a[i] 等于v，将 i 加一

public class Quick3way
{
    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt)
        {
            int cmp = a[i].compareTo(v);
            if      (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else              i++;
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }
}           

2.4 優先隊列 (Prior Queues)

普通的隊列 (queue) 是一種先進先出的資料結構，元素在隊列尾追加，而從隊列頭删除。在優先隊列中，元素被賦予優先級。當通路元素時，具有最高優先級的元素最先删除。這種隊列不是直接将新元素放在隊列尾部，而是放在比它優先級低的元素前面。

優先隊列最重要的操作是删除最大元素 (delMax()) 和插入元素 (insert()) ，見以下API：

以下是一個優先隊列的測試用例，列印數字最大的M行：

public class TopM
{
    public static void main(String[] args)
    {
        int M = Integer.parseInt(args[0]);
        MinPQ<Transaction> pq = new MinPQ<Transaction>(M+1);
        while (StdIn.hasNextLine())
        {
            pq.insert(new Transaction(StdIn.readLine()));
            if (pq.size() > M)
                pd.delMin();
        }
        Stack<Transaction> stack = new Stack<Transaction>();
        while (!pq.isEmpty()) stack.push(pq.delMin());
        for (Transaction t : stack) StdOut.println(t);
    }
}           

堆的定義

資料結構二叉堆 (binary heap) 能很好地實作優先隊列的基本操作。二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數組中按照層級存儲 (不使用數組的第一個位置)。堆有序 (heap-ordered) 指的是一顆二叉樹的每個結點都大于等于它的兩個子結點。

在一個堆中，位置為k的結點的父結點位置為\(\left\lfloor k/2 \right\rfloor\) ，兩個子結點的位置分别為 \(2k\) 和 \(2k+1\)。一顆大小為N的完全二叉樹的高度為\(\left\lfloor lgN \right\rfloor\)

堆的算法

自下而上的堆有序化 —— 上浮 (swim)

如果某個結點比其父結點大，則需要交換二者以保持堆的有序化，這樣的循環過程為swim() 方法：

private void swim(int k)
{
    while (k > 1 && less(k/2, k))
    {
        exch(k/2, k);
        k = k/2;
    }
}           

自上而下的堆有序化 —— 下沉 (sink)

如果某個結點比其兩個子結點的其中之一小，則需要将它和兩個子結點的較大者交換以保持堆的有序化這樣的循環過程為sink() 方法：

private void sink(int k)
{
    while (2*k <= N)
    {
        int j = 2*k;
        if (j < N && less(j, j+1)) j++;
        if (!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}           

插入元素：将新元素加到數組末尾，增加堆的大小并将這個元素上浮到合适位置。

删除最大元素：從數組頂端删去最大元素并将數組最後一個元素放到頂端，再讓這個元素下沉到合适位置。

下列代碼實作了優先隊列，優先隊列由一個基于堆的完全二叉樹表示，存儲于數組 pq[1...N] 中，pq[0] 沒有使用。

public class MaxPQ<Key extends Comparable<Key>>
{
    private Key[] pq;
    private int N = 0;

    public MaxPQ(int maxN)
    { pq = (Key[]) new Comparable[maxN+1]; }

    public boolean isEmpty()
    { return N == 0; }

    public int size()
    { return N; }

    public void insert(Key v)
    {
        pq[++N] = v;
        swim(N);
    }

    public Key delMax()
    {
        Key max = pq[1];
        exch(1, N--);
        pq[N+1] = null;
        sink(1);
        return max;
    }

    private boolean less(int i, int j)
    { return pq[i].compareTo(pq[j]) < 0; }

    private void exch(int i, int j)
    { Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }

    private void swim(int k)
    {
        while (k > 1 && less(k/2, k))
        {
            exch(k/2, k);
            k = k/2;
        }
    }

    private void sink(int k)
    {
        while (2*k <= N)
        {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
}           

索引優先隊列 (Index Priority Queue)

索引優先隊列即在優先隊列的基礎上給數組中每個元素添加一個索引。以下實作用

pq[]

儲存索引，

qp[]

儲存

pq[]

的逆序，即

pq[]

中元素的位置。舉例：

pq = [1,2,0], 則qp = [2,0,1]，pq[qp[1]]=1

。數組

keys[]

儲存元素。

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.In;

public class IndexMinPQ<Key extends Comparable<Key>>
{
    private int maxN;
    private int n;
    private int[] pq;
    private int[] qp;
    private Key[] keys;

    public IndexMinPQ(int maxN)
    {
        this.maxN = maxN;
        n = 0;
        keys = (Key[]) new Comparable[maxN + 1];
        pq = new int[maxN + 1];
        qp = new int[maxN + 1];
        for (int i = 0; i <= maxN; i++)
            qp[i] = -1;
    }

    public boolean isEmpty()
    { return n == 0; }

    public boolean contains(int i)
    { return qp[i] != -1; }

    public int size()
    { return n; }

    public void insert(int i, Key key)
    {
        n++;
        qp[i] = n;
        pq[n] = i;
        keys[i] = key;
        swim(n);
    }

    public int minIndex()
    { return pq[1]; }

    public Key minKey()
    { return keys[pq[1]]; }

    public int delMin()
    {
        int min = pq[1];
        exch(1, n--);
        sink(1);
        assert min == pq[n+1];
        qp[min] = -1;
        keys[min] = null;
        pq[n+1] = -1;
        return min;
    }

    public void changeKey(int i, Key key)
    {
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }

    public void delete(int i)
    {
        int index = qp[i];
        exch(index, n--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }

    private boolean greater(int i, int j)
    { return keys[pq[i]].compareTo(keys[pq[j]]) > 0; }

    private void exch(int i, int j)
    {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    private void swim(int k)
    { 
        while (k > 1 && greater(k/2, k))
        {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k)
    {
        while (2*k <= n)
        {
            int j = 2*k;
            if (j < n && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    /******************************************************
    以下為用例：多向歸并問題，将多個有序的輸入流歸并成一個有序的輸出流 
    ******************************************************/
    
    public static void merge(In[] streams)
    {
        int N = streams.length;
        IndexMinPQ<String> pq = new IndexMinPQ<String>(N);

        for (int i = 0; i < N; i++)
            if (!streams[i].isEmpty())
                pq.insert(i, streams[i].readString());

        while (!pq.isEmpty())
        {
            StdOut.printf(pq.minKey() + " ");
            int i = pq.delMin();
            if (!streams[i].isEmpty())
                pq.insert(i, streams[i].readString());
        }
    }

    public static void main(String[] args)
    {
        int N = args.length;
        In[] streams = new In[N];
        for (int i = 0; i < N; i++)
            streams[i] = new In(args[i]);
        merge(streams);
        StdOut.println();
    }
}

/*************
輸入：
% more m1.txt
A B C F G I I Z
% more m2.txt
B D H P Q Q
% more m3.txt
A B E F J 

輸出：
% java IndexMinPQ m1.txt m2.txt m3.txt
A A B B B C D E F F G H I I J N P Q Q Z 
**************************************/           

堆排序 (Heapsort)

堆排序可分為兩個階段：

1. 堆的構造：将原始數組重新組織安排進一個堆中
2. 下沉 (sink) 排序：從堆中按遞減順序取出所有元素并得到排序結果

堆的構造通過從下到上遞歸地建構子堆來實作。如果一個結點的兩個子結點都已經是堆了，那麼在該結點上調用sink() 就能把它們變成一個堆，這樣就能按數組逆序從下而上地建構堆。隻需對數組中一半元素使用 sink()方法，因為剩下的元素都是葉結點。完成後堆的最大元素将位于數組的開頭。

下沉排序階段将頂端和末端元素進行交換，然後将最大元素從堆中删除并用 sink() 重新調整堆的結構，如此循環最後得到一個有序序列。

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Heap
{
    private Heap() {  }

    public static void sort(Comparable[] pq)
    {
        int n = pq.length;
        for (int k = n/2; k >= 1; k--)
            sink(pq, k, n);
        while (n > 1)
        {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }

    private static void sink(Comparable[] pq, int k, int n)
    {
        while (2*k <= n)
        {
            int j = 2*k;
            if (j < n && less(pq, j, j+1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }

    private static boolean less(Comparable[] pq, int i, int j)
    { return pq[i-1].compareTo(pq[j-1]) < 0; }

    private static void exch(Object[] pq, int i, int j)
    {
        Object swap = pq[i-1];
        pq[i-1] = pq[j-1];
        pq[j-1] = swap;
    }

    private static void show(Comparable[] a)
    {
        for (int i = 0; i < a.length; i++)
            StdOut.println(a[i]);
    }

    public static void main(String[] args)
    {
        String[] a = StdIn.readAllStrings();
        Heap.sort(a);
        show(a);
    }
}           

2.5 應用

• 排序算法的穩定性：如果一個排序算法能夠保留數組中重複元素的相對位置則可以被稱為是穩定的。

找出重複元素

隻需線性對數的時間，先将數組排序，再周遊數組，記錄連續出現的重複元素。如果用平方級别的算法則要将所有元素互相比較一遍。

Quick.sort(a);
int count = 1;
for (int i = 1; i < a.length; i++)
    if (a[i].compareTo(a[i-1]) != 0)
        count++;           

/