一. 寫在前面

要學(xué)習(xí)算法，“排序”是一個(gè)回避不了的重要話題谬盐，在分析完并查集算法和常用數(shù)據(jù)結(jié)構(gòu)之后试躏，今天我們終于可以走近排序算法這個(gè)大家族了。計(jì)算機(jī)科學(xué)發(fā)展到今天设褐，已經(jīng)有了成百上千種讓你眼花繚亂颠蕴，多的數(shù)不清的排序算法，而且還會(huì)有更新更厲害的算法尚未問世助析，它們都是人類無窮智慧的結(jié)晶犀被，有太多太有意思的內(nèi)容等待我們?nèi)ニ伎迹テ肺锻饧健Ｗ鳛橐黄腴T級(jí)的學(xué)習(xí)筆記寡键，我們不會(huì)在這里展開討論，但是雪隧，我們將從“排序算法”這個(gè)百寶袋中西轩，抓取幾個(gè)經(jīng)典的，膾炙人口的算法脑沿，作為這次我們討論的主題藕畔。我們會(huì)先聊聊三種最基本的算法：選擇，插入和Shell排序庄拇；然后我們走入分治思想的世界注服，聊聊歸并排序韭邓；然后我們將登上世界之巔，來看看20世紀(jì)最偉大的算法之一——快速排序溶弟，了解一下這幾十年來人們?yōu)榱搜芯克甲隽四男┚薮筘暙I(xiàn)女淑；最后，我們將認(rèn)識(shí)一個(gè)新朋友辜御，一個(gè)為排序而生的數(shù)據(jù)結(jié)構(gòu)——優(yōu)先級(jí)隊(duì)列鸭你，并以一些排序算法的實(shí)際應(yīng)用作為本算法分析筆記的結(jié)束，在讀完本篇文章之后擒权，相信你會(huì)獲得對(duì)排序算法有一個(gè)基礎(chǔ)的了解袱巨。
當(dāng)然，本篇文章介紹的內(nèi)容都是我在學(xué)習(xí)Princeton大學(xué)Sedgewick教授的Coursera上公開課“Algorithms”時(shí)的一些心得菜拓，文章中的一些圖示瓣窄，例子和代碼笛厦，均來自于老教授的課件和英文原版教科書纳鼎，所有這一切的知識(shí)和成果，都是他老人家辛苦整理的智慧結(jié)晶裳凸。感謝Sedgewick老師贱鄙，感謝這位可敬的老人帶給我算法學(xué)習(xí)中的不少樂趣。

1.1 排序算法怎么玩

排序是一種將某元素的集合按照某種邏輯順序進(jìn)行排列的過程姨谷。我們之所以要排序逗宁，是因?yàn)樗軡M足我們的某種需要，特別是對(duì)于有強(qiáng)迫癥的人來說梦湘，排列整齊總是比雜亂無章要好的瞎颗。最簡(jiǎn)單的例子是，在前面介紹并查集算法時(shí)捌议，我們?cè)?jīng)聊到過二叉搜索算法哼拔，它能很快地從集合中查找元素，但前提是該集合內(nèi)的元素是已排序的瓣颅。實(shí)際生活中的例子還有很多：比如人員名單在中國通常按筆畫數(shù)排序倦逐，在英美國家則是字母順序；學(xué)校里老師要按照分?jǐn)?shù)對(duì)考試成績(jī)進(jìn)行排序宫补，看看前十名都有哪些人檬姥；銀行要按照資產(chǎn)情況對(duì)客戶信息進(jìn)行排序，存款最多的用戶也許能發(fā)展成為該行的VIP客戶粉怕；超市要按照時(shí)間順序?qū)灰子涗涍M(jìn)行排序健民，以打印賬單等等。幾乎所有需要用計(jì)算機(jī)去處理相關(guān)事務(wù)的領(lǐng)域贫贝，你都會(huì)看到排序算法的身影荞雏，它們往往是重要算法的關(guān)鍵一環(huán)。

1.2 排序算法的抽象設(shè)計(jì)

應(yīng)用越廣泛的東西，遇到的問題也就越多凤优。如果我們只對(duì)簡(jiǎn)單的元素進(jìn)行排序悦陋，那一點(diǎn)都不難，比如對(duì)數(shù)字進(jìn)行排序筑辨，對(duì)字符串進(jìn)行排序俺驶。但實(shí)際生活中我們往往要面對(duì)的是復(fù)雜的情況和復(fù)雜的對(duì)象。首先棍辕，不是所有的元素集合都能排序暮现，比如我們愛玩的“石頭剪刀布”游戲，石頭干掉剪刀楚昭，剪刀干掉布栖袋，然后布又干掉石頭，你把哪個(gè)放在前面都對(duì)抚太，又都不對(duì)塘幅，無法排序；其次尿贫，對(duì)一個(gè)元素集合我們可能會(huì)按照多種標(biāo)準(zhǔn)進(jìn)行排序电媳，比如一條學(xué)生成績(jī)記錄可能包含姓名，學(xué)號(hào)庆亡，科目和分?jǐn)?shù)等等匾乓，那我既可以按分?jǐn)?shù)高低排序選出優(yōu)秀學(xué)生，也可以按照姓名排序進(jìn)行點(diǎn)名又谋，更可以按照科目分?jǐn)?shù)排序找出某一科的佼佼者拼缝。這些都會(huì)在實(shí)際生活中遇到，如何處理彰亥？
對(duì)于第一個(gè)問題咧七，我們要先弄清楚的是究竟什么樣的元素集合是可以排序的。答案是：如果你能在這個(gè)元素集合上找到一個(gè)“全序”（Total Order）關(guān)系剩愧，那么它就是可以排序的猪叙。全序的定義是：1）自反（Reflexive），對(duì)所有元素e仁卷，e=e都成立穴翩；2）反對(duì)稱（Antisymmetric），對(duì)所有元素v和w锦积，v < w則w > v芒帕，w = v則v = w；3）傳遞（Transitive）丰介，對(duì)所有的v背蟆，w和x鉴分，v <= w且w <= x，那么v <= x带膀≈菊洌“石頭剪刀布”顯然就不滿足，因?yàn)殡m然石頭能干掉剪刀垛叨，剪刀能干掉布伦糯，但石頭并不能干掉布，而是被布給干掉了嗽元，不滿足傳遞性敛纲。不過在實(shí)際編程工作中我們也不用太在意，知道有這么回事就好剂癌，我們只需要通過某種方式告訴排序算法如何判斷兩個(gè)元素誰大誰小就可以了淤翔。
那么怎樣告訴排序算法兩個(gè)元素誰大誰小呢？我們的方法是基于“回調(diào)”機(jī)制實(shí)現(xiàn)佩谷，而各種不同的編程語言在“回調(diào)”的基礎(chǔ)上建立了自己的處理方法：C語言使用函數(shù)指針旁壮，C++通過定義函對(duì)象重載函數(shù)調(diào)用操作符實(shí)現(xiàn)，Python語言通過FP的方式實(shí)現(xiàn)琳要，Java語言和Go語言則是通過“接口”來實(shí)現(xiàn)寡具〕用“面向接口編程”是一種重要的思想稚补，在設(shè)計(jì)這種通用算法的時(shí)候就特別有用，這些通用的算法通過“回調(diào)”來處理具體的對(duì)象框喳，而不需要知道對(duì)象的細(xì)節(jié)课幕，這便是依賴倒置原則：細(xì)節(jié)依賴于抽象，而抽象并不依賴于細(xì)節(jié)五垮。
在Java中乍惊，只要我們的類滿足Comparable接口，通過實(shí)現(xiàn)compareTo()函數(shù)就能告訴排序算法兩個(gè)元素誰大誰小放仗。例如一個(gè)實(shí)現(xiàn)了Comparable接口的Date類如下所示润绎，這樣我們就可以用排序算法對(duì)Date進(jìn)行按日期的排序排序。compareTo()函數(shù)返回一個(gè)整型來表示大小關(guān)系：正數(shù)表示大于诞挨，負(fù)數(shù)表示小于莉撇，0則表示等于。

public class Date implements Comparable<Date> { 
  /* ... */ 
  public int compareTo(Date that) { 
    if (this.year < that.year) return -1; 
    if (this.year > that.year) return +1; 
    if (this.month < that.month) return -1; 
    if (this.month > that.month) return +1; 
    if (this.day < that.day) return -1; 
    if (this.day > that.day) return +1; 
    return 0; 
  } 
  /* ... */
}

除此之外惶傻，我們還要實(shí)現(xiàn)兩個(gè)輔助函數(shù)：less和exch棍郎，less函數(shù)用于對(duì)元素的比較進(jìn)行進(jìn)一步“包裝”——因?yàn)閏ompareTo返回的是整型值，而我們需要一個(gè)返回布爾值的函數(shù)银室；exch函數(shù)則用于交換兩個(gè)元素涂佃，這些都是排序算法中所需要的励翼。這樣，我們?cè)趯?shí)現(xiàn)排序算法時(shí)就通過這些函數(shù)辜荠，以一種統(tǒng)一的形式去操作數(shù)據(jù)結(jié)構(gòu)汽抚，而不去關(guān)心它們是怎么比較大小或者怎么交換元素的。

private static boolean less(Comparable v, Comparable w) { 
  return (v.compareTo(w) < 0);
}
private static void exch(int[] a, int i, int j) { 
  int swap = a[i]; 
  a[i] = a[j]; 
  a[j] = swap;
}

那如果我們要對(duì)同一記錄進(jìn)行多種形式的排序又該怎么做呢伯病？這就要用到Java的另一個(gè)更高級(jí)的接口——Comparator殊橙。這個(gè)接口只包含一個(gè)函數(shù)compare()，它同樣通過返回一個(gè)整型值來表示大小關(guān)系：正數(shù)表示大于狱从，負(fù)數(shù)表示小于膨蛮，而0表示相等。比如我們有一個(gè)表示商業(yè)事務(wù)的類Transaction季研，包含客戶姓名敞葛，日期和資產(chǎn)，我們需要對(duì)商業(yè)事務(wù)的記錄按照姓名与涡、日期和資產(chǎn)進(jìn)行排序惹谐，那么我們就可以在Transaction中 實(shí)現(xiàn)三個(gè)滿足Comparator接口的類：WhoOrder，WhenOrder以及HowMuchOrder驼卖。

import java.util.Arrays;
import java.util.Comparator;
public class Transaction implements Comparable<Transaction> {
  private final String  who;      // customer
  private final Date    when;     // date
  private final double  amount;   // amount
  /* ... */
  /**     * Compares two transactions by customer name.     */
  public static class WhoOrder implements Comparator<Transaction> {
    public int compare(Transaction v, Transaction w) {
        return v.who.compareTo(w.who);
    }
  }

  /**     * Compares two transactions by date.     */
  public static class WhenOrder implements Comparator<Transaction> {
    public int compare(Transaction v, Transaction w) {
        return v.when.compareTo(w.when);
    }
  }

  /**     * Compares two transactions by amount.     */
  public static class HowMuchOrder implements Comparator<Transaction> {
    public int compare(Transaction v, Transaction w) {
        if      (v.amount < w.amount) return -1;
        else if (v.amount > w.amount) return +1;
        else                          return  0;
    }
  }

  public static void main(String[] args) {
    Transaction[] a = new Transaction[4];
    a[0] = new Transaction("Turing   6/17/1990  644.08");
    a[1] = new Transaction("Tarjan   3/26/2002 4121.85");
    a[2] = new Transaction("Knuth    6/14/1999  288.34");
    a[3] = new Transaction("Dijkstra 8/22/2007 2678.40");

    StdOut.println("Unsorted");
    for (int i = 0; i < a.length; i++)
        StdOut.println(a[i]);
    StdOut.println();
    
    StdOut.println("Sort by date");
    Arrays.sort(a, new Transaction.WhenOrder());
    for (int i = 0; i < a.length; i++)
        StdOut.println(a[i]);
    StdOut.println();

    StdOut.println("Sort by customer");
    Arrays.sort(a, new Transaction.WhoOrder());
    for (int i = 0; i < a.length; i++)
        StdOut.println(a[i]);
    StdOut.println();

    StdOut.println("Sort by amount");
    Arrays.sort(a, new Transaction.HowMuchOrder());
    for (int i = 0; i < a.length; i++)
        StdOut.println(a[i]);
    StdOut.println();
  }
}

相應(yīng)地氨肌，less函數(shù)和exch函數(shù)也要做一些輕微的調(diào)整，如下所示酌畜。實(shí)際工作中怎囚，我們可以按照需求選擇Comparable或者Comparator接口來設(shè)計(jì)我們的類。好了桥胞，以上就是我們?yōu)檠芯扛鞣N排序算法搭好的一個(gè)基本“框架”恳守，我們介紹了Java的兩個(gè)接口，介紹了回調(diào)機(jī)制以及“面向接口編程”的重要思想贩虾，下面催烘，我們就來深入學(xué)習(xí)一下各種算法的思想及其實(shí)現(xiàn)吧。

// is v < w ?
private static boolean less(Comparator c, Object v, Object w)  {
  return (c.compare(v, w) < 0);
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
  Object swap = a[i];
  a[i] = a[j];
  a[j] = swap;
}

二. 基礎(chǔ)排序算法

我們以選擇排序缎罢，插入排序和Shell排序?yàn)槔寥海榻B三種最基本的排序算法。第一個(gè)要認(rèn)識(shí)的就是選擇排序算法策精，選擇排序只能作為入門介紹舰始，因?yàn)樗愀獾男阅軣o法在實(shí)際生活中使用，而后兩種算法就不同了蛮寂，它們?cè)谝恍┨厥馇闆r和場(chǎng)景下會(huì)很有用蔽午，這個(gè)后面會(huì)有討論。

2.1 選擇排序

用一句話來描述選擇排序酬蹋，就是把當(dāng)前最小的元素放到它應(yīng)該在的位置及老。算法會(huì)遍歷序列中的每一個(gè)位置i抽莱，然后在i的右邊選擇一個(gè)（當(dāng)前的）最小值，把它放到位置i骄恶，把位置i上原先存在的元素交換出去食铐。算法第一次運(yùn)行時(shí)，會(huì)把最小的元素放在位置0僧鲁，第二次運(yùn)行時(shí)把第二小的元素放在位置1……這樣當(dāng)遍歷完最后一個(gè)元素時(shí)虐呻，整個(gè)序列就排好序了，如圖2-1所示寞秃。

圖2-1 選擇排序追蹤圖

public class Selection {
  // This class should not be instantiated.
  private Selection() { }
  public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) 
    {
        int min = i;
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        exch(a, i, min);
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
  }
}

從上面的代碼我們可以分析它的性能斟叼，算法總共的比較次數(shù)為(N-1) + (N-2) + ... + 1 + 0 = N(N-1)/2，交換次數(shù)為N次春寿，故性能為O(N^2)朗涩。而且選擇排序是一個(gè)“油鹽不進(jìn)”的排序算法，隨便你給出什么樣的輸入序列——哪怕它已經(jīng)是有序的——都需要平方時(shí)間才能完成排序绑改，因此選擇排序就跟冒泡排序一樣谢床，了解了解就好，沒有什么實(shí)際的用處厘线。

2.2 插入排序

插入排序名字取得不好识腿，它應(yīng)該叫“撲克排序”，想想你斗地主的時(shí)候是怎么理牌的造壮，你就知道插入排序的大致步驟了渡讼。在插入排序運(yùn)行的過程中，我們總是假定位置i之前已經(jīng)是有序的费薄，我們的任務(wù)就是將位置i的元素放到合適的位置硝全，就好比摸了一張新牌栖雾，要把這張新牌插入到合適的位置一樣楞抡。如圖2-2所示，我們手里已經(jīng)有了三張排好序的牌析藕，當(dāng)我們?cè)倜矫坊?時(shí)召廷，因?yàn)樗冗@幾張牌都要小，所以我們最終將它插入到了最開始的位置账胧。

2-2 插入排序很像打撲克

public class Insertion {
  // This class should not be instantiated.
  private Insertion() { }
  public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
  }
}

最壞情況下（輸入序列逆序）竞慢，待插入的元素要跟之前所有的元素相比較，因此需要N^{2/2次比較和交換治泥；最好情況下（輸入序列已排序）筹煮，待插入元素?zé)o需移動(dòng)姑子，且只比較一次圈匆，總共需要N-1次比較；平均情況下，插入排序大概需要N}2/4次比較和交換褒侧，因此它是一個(gè)O(N^2)的算法，遇到很大的序列令蛉，排序時(shí)間會(huì)比較慢荡陷。
但如果你就此下結(jié)論，說插入排序是一個(gè)沒用的算法沟饥，那就太輕率了添怔。插入排序有一些很有趣的性質(zhì)，科學(xué)家們對(duì)插入排序更進(jìn)一步的研究發(fā)現(xiàn)贤旷，插入排序?qū)^小的序列很有效广料，而且對(duì)部分有序的序列效率很高。要理解部分有序幼驶，首先要認(rèn)識(shí)一個(gè)“逆”的 概念性昭，一個(gè)序列中的“逆”，是指序列中的逆序?qū)ο厍玻热纭癆 E E L M O T R X P S”中“T-R T-P T-S R-P X-P X-S”就是其中存在的6個(gè)逆糜颠。若一個(gè)序列元素有N個(gè)，則“部分有序”是指該序列的逆序數(shù)小于等于cN萧求，其中c為常數(shù)其兴。
如果一個(gè)序列是部分有序的，那么插入排序的運(yùn)行效率將會(huì)是線性的夸政，即O(N)時(shí)間內(nèi)就能完成元旬，為什么呢？仔細(xì)觀察插入排序的代碼你就會(huì)發(fā)現(xiàn)守问，每進(jìn)行一次交換匀归，序列的逆序數(shù)就會(huì)減一（因此插入排序可以用來計(jì)算一個(gè)序列的逆序數(shù)，歸并排序也能）耗帕，因此交換的次數(shù)就等于逆序數(shù)穆端，既然逆序數(shù)小于等于cN，那么交換的性能為O(N)仿便；關(guān)鍵在于比較的次數(shù)体啰，首先，每個(gè)元素至少都要跟它前面的那個(gè)元素進(jìn)行一次比較嗽仪，所以一定有(N-1)次荒勇，其次，每發(fā)生一次交換就意味著有過一次比較闻坚，且比較的結(jié)果是該元素比它之前的那個(gè)元素小沽翔，因此總的比較次數(shù)一定是(N-1)再加上交換的次數(shù)，比較的性能仍然是O(N)窿凤，所以在面對(duì)部分有序的序列時(shí)仅偎，插入排序能做到線性時(shí)間內(nèi)完成西潘。
這一事實(shí)導(dǎo)致了兩個(gè)有趣的結(jié)果。首先哨颂，你會(huì)發(fā)現(xiàn)插入排序總是跟歸并排序和快速排序算法玩“曖昧”喷市，在歸并排序和快速排序?qū)⑿蛄蟹纸獬梢欢ㄒ?guī)模的小數(shù)組之后，使用插入排序?qū)@些小數(shù)組進(jìn)行排序要比繼續(xù)分解要好威恼，能夠節(jié)省一些開銷品姓，如圖2-3和2-4所示。在1993年Bentley 和 McIlroy那篇著名的論文“Engineering a Sort Function”中箫措，兩位大神給出了一種具有實(shí)際工程意義的快速排序?qū)崿F(xiàn)腹备，該算法在處理較小的數(shù)組時(shí)，就使用了插入排序斤蔓。時(shí)至今日植酥，該論文已經(jīng)成為各種編程語言排序算法標(biāo)準(zhǔn)庫實(shí)現(xiàn)的必備參考，你如果有心去閱讀這些語言的源代碼弦牡，就能發(fā)現(xiàn)該論文的身影友驮。比如Go語言sort包中快速排序的實(shí)現(xiàn)就借鑒了該論文的思想，如圖2-5和2-6所示驾锰。
另一個(gè)有趣的結(jié)果是卸留，因?yàn)椴迦肱判驅(qū)Σ糠钟行虻臄?shù)組工作的很好，科學(xué)家們就挖空心思地鉆研如何將序列弄得部分有序椭豫，這誕生了另一個(gè)有趣的算法——Shell排序耻瑟，你可以將Shell排序當(dāng)成插入排序的一個(gè)變種，這也是我們接下來要分析的赏酥。

圖2-3 歸并排序中使用插入排序進(jìn)行局部?jī)?yōu)化

圖2-4 快速排序中使用插入排序進(jìn)行局部?jī)?yōu)化

圖2-5 實(shí)現(xiàn)排序算法標(biāo)準(zhǔn)庫必備參考論文

圖2-6 Go語言標(biāo)準(zhǔn)庫sort中快速排序的實(shí)現(xiàn)使用到了插入排序

2.3 Shell排序

如上所述喳整，Shell排序是對(duì)插入排序的一種改進(jìn)。既然插入排序?qū)Σ糠钟行虻男蛄泻苡行惴觯敲次覀兙鸵聊ヒ幌略鯓幼屝蛄凶兊貌糠钟行蚩蚨肌hell排序的思路是，與其像插入排序那樣挨個(gè)排序姓言，還不如間隔h個(gè)元素進(jìn)行排序瞬项，也就是每次排序向前跳h個(gè)位置，這樣序列雖然整體上看貌似無序何荚，但每間隔h個(gè)元素的序列卻是交錯(cuò)有序的，這種排序被稱為h-排序猪杭，而排序后的序列被稱為“h-有序的”餐塘，如圖2-7所示。Shell排序有個(gè)重要的概念皂吮，一個(gè)h-有序的序列在g-排序后仍然是h-有序的戒傻，那么如果我們以某種方式逐步縮小h直到h變?yōu)?税手，那么當(dāng)進(jìn)行h為1的那次排序時(shí)，序列已經(jīng)部分有序需纳，而且排序也退化為一般的插入排序芦倒，那么算法的執(zhí)行效率也就有了提高。在一開始時(shí)不翩，因?yàn)閔很大兵扬，所以子序列很短，隨著算法的進(jìn)行口蝠，h越來越小器钟，子序列越來越長(zhǎng)，整個(gè)序列部分有序的程度越來越高妙蔗，執(zhí)行插入排序的效率也就越來越高傲霸。那么h的跳數(shù)該怎么選擇呢？人們已經(jīng)找到不少有效的計(jì)算公式眉反，但一個(gè)簡(jiǎn)單實(shí)用的“3X+1”即可滿足絕大部分的性能要求了昙啄。

圖2-7 每隔4個(gè)元素交錯(cuò)有序的序列

public class Shell {
  // This class should not be instantiated.
  private Shell() { }
  public static void sort(Comparable[] a) {
    int N = a.length;
    // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1;
    while (h < N/3) h = 3*h + 1; 

    while (h >= 1) 
    {
        // h-sort the array
        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 /= 3;
    }
    assert isSorted(a); 
   }
}

首先，我們讓h增大到大約N/3的位置寸五，然后一邊對(duì)序列進(jìn)行h排序跟衅，一邊減小h的值，每次減小到原來的1/3播歼，這樣最后一次h的值就為1伶跷，有科學(xué)家研究，該算法最壞情況下的運(yùn)行效率為O(N^3/2)秘狞，算法演示如圖2-8所示叭莫。Shell排序是一個(gè)頗具神秘魅力的算法，因?yàn)閷?duì)它的平均情況效率還沒有得出可用的結(jié)論烁试。但這并不妨礙Shell排序成為一個(gè)實(shí)用的算法雇初。除非遇到巨大的序列，Shell排序還是很快的减响，在嵌入式和硬件領(lǐng)域應(yīng)用較為廣泛靖诗。

圖2-8 Shell排序舉例

2.4 隨機(jī)洗牌算法

大多數(shù)時(shí)候，我們希望得到的信息是排列有序支示，讓人賞心悅目的刊橘，但有些時(shí)候我們卻希望信息是亂序的，是隨機(jī)的颂鸿，是讓人猜不準(zhǔn)下一步會(huì)得到什么的促绵。比如你在網(wǎng)上開了一家虛擬賭場(chǎng)，讓大家都來你這里打牌斗地主，你就希望洗牌算法每次得到的結(jié)果都不一樣败晴，否則每次拿到一樣的牌浓冒，這地主還怎么斗下去呢，這也不符合實(shí)際情況呀尖坤。所以我們的目標(biāo)是：重新排列數(shù)組稳懒，使得得到的排列是均勻分布的。其中的一種辦法是慢味，我們?yōu)閿?shù)組中的每一個(gè)位置用滿足均勻分布的偽隨機(jī)數(shù)生成器產(chǎn)生一個(gè)隨機(jī)數(shù)场梆，對(duì)隨機(jī)數(shù)進(jìn)行排序，就能得到想要的結(jié)果（當(dāng)然贮缕，舉一反三地想想辙谜，如果我們使用產(chǎn)生滿足其他概率分布的隨機(jī)數(shù)生成器，就能生成滿足其他性質(zhì)的隨機(jī)序列）感昼，如圖2-9所示装哆。

圖2-9 隨機(jī)洗牌后的撲克牌

還有一種隨機(jī)洗牌算法更常用，是牛人Knuth他老人家發(fā)明的定嗓，叫做Knuth Shuffle蜕琴，這種方法的基本思想就是：對(duì)于元素arr[i]，用隨機(jī)挑選的另一個(gè)元素arr[r]與它進(jìn)行互換宵溅，其中r是[0, i]或者[i, N-1]區(qū)間內(nèi)隨機(jī)選出來的一個(gè)元素凌简，如下所示。

public static void shuffle(Object[] a) {
  int N = a.length;
  for (int i = 0; i < N; i++) {
    int r = StdRandom.uniform(i + 1);
    exch(a, i, r);
  }
}
public static void shuffle(int[] a) {
  int N = a.length;
  for (int i = 0; i < N; i++) {
    int r = i + uniform(N-i); // between i and N-1
    int temp = a[i];
    a[i] = a[r];
    a[r] = temp;
  }
}

實(shí)際上恃逻，開發(fā)隨機(jī)數(shù)算法一定要慎之又慎雏搂，因?yàn)樯圆蛔⒁饩蜁?huì)出現(xiàn)一些很小的漏洞，如果在線撲克牌游戲中出現(xiàn)這樣那樣的一些漏洞寇损，黑客就可以利用它推算出程序?qū)⒁l(fā)什么牌凸郑，這有時(shí)候是災(zāi)難性的，網(wǎng)上有一篇著名的博文當(dāng)隨機(jī)不夠隨機(jī)：一個(gè)在線撲克游戲的教訓(xùn)就介紹了上世紀(jì)90年代末國外一個(gè)很流行的在線撲克平臺(tái)出現(xiàn)過的嚴(yán)重錯(cuò)誤矛市，是隨機(jī)洗牌算法的一個(gè)很好的反面教材芙沥，提醒我們算法設(shè)計(jì)一定要小心，有興趣的可以看一看浊吏。

三. 算法名人堂——?dú)w并排序

基本排序介紹完了而昨，現(xiàn)在我們登堂入室，來認(rèn)識(shí)一個(gè)家喻戶曉的著名算法——?dú)w并排序找田。不像Shell排序歌憨，人們對(duì)歸并排序的性能可謂了如指掌，所以她被大量運(yùn)用到各種計(jì)算系統(tǒng)中午阵。Java就用她來排序各種對(duì)象躺孝，而C++和Python等編程語言則使用她來實(shí)現(xiàn)一種“穩(wěn)定”的排序算法享扔，我們對(duì)歸并排序的介紹底桂，就從“穩(wěn)定性”這個(gè)概念開始植袍。

3.1 排序算法的穩(wěn)定性

“穩(wěn)定性”是在對(duì)記錄進(jìn)行多種方式排序時(shí)通常要考慮的問題，如果記錄可以通過Key1排序籽懦，又可以通過Key2排序于个，那么在Key2排序之后，如果Key2相同的一眾記錄相對(duì)于Key1而言仍然是有序的暮顺，那么我們就說該排序算法是穩(wěn)定排序厅篓，否則，就是不穩(wěn)定的捶码，圖3-1中所示的例子中羽氮，我們先對(duì)學(xué)生記錄按照姓名進(jìn)行排序，然后又按照分區(qū)進(jìn)行排序惫恼，結(jié)果第3區(qū)的學(xué)生不再是按姓名排序的档押，因此選擇排序并不是一個(gè)穩(wěn)定的算法。在我們介紹過的算法中祈纯，只有插入排序是穩(wěn)定的令宿，因?yàn)樗看我苿?dòng)元素的跨度很小，不會(huì)跑到跟它一樣大的元素前面去腕窥。而選擇排序和Shell排序跨度都比較大粒没，比如Shell排序一開始就每間隔h個(gè)元素進(jìn)行排序，自然無法保證穩(wěn)定性簇爆。
歸并排序不但效率最優(yōu)癞松，而且滿足穩(wěn)定性，是一個(gè)優(yōu)秀的算法入蛆。它的基本思想就是將序列一分為二响蓉，分別排序左半部分和右半部分，然后再將這兩部分歸并成一個(gè)有序的序列安寺，其中對(duì)左半部分和右半部分的排序是遞歸的厕妖，仍然是一分為二然后歸并，如圖3-2所示挑庶。歸并排序就是一個(gè)很典型的“分治”算法思想的體現(xiàn)：某問題解決起來困難言秸，那么我們就將該問題不斷拆分成眾多子問題，然后將子問題的解匯總成最終問題的解迎捺【倩“分治”算法不但高效且容易進(jìn)行數(shù)學(xué)分析，這個(gè)后面會(huì)看到凳枝。

圖3-1 選擇排序不是穩(wěn)定的算法

圖3-2 歸并算法演示

圖3-3 歸并排序演示

3.2 歸并排序中的歸并

如圖3-3所示抄沮，在歸并排序中跋核，歸并是一個(gè)重要的組成部分，它的基本思想是：拷貝并使用一個(gè)同樣大小的輔助序列aux叛买，用兩個(gè)索引分別指向已排序的子序列aux[lo..mid]和aux[mid+1..hi]砂代，同時(shí)遍歷兩個(gè)序列，比較遍歷到的元素率挣，每次都將最小的元素放入arr刻伊，如果其中有哪個(gè)子序列歸并完了，那么就將另一子序列的元素一個(gè)一個(gè)拷進(jìn)去椒功。使用輔助數(shù)組aux意味著這種歸并排序的空間效率不高——每次都要使用額外的O(N)空間捶箱，其實(shí)歸并排序的版本不止一種，還有一些比較復(fù)雜的算法實(shí)現(xiàn)了真正的就地歸并动漾。這里還可以學(xué)到一個(gè)新技能：斷言丁屎。通常每個(gè)算法的執(zhí)行都會(huì)有一個(gè)前置狀態(tài)（Precondition），當(dāng)滿足前置條件時(shí)執(zhí)行該算法才是正確的旱眯，而算法正確執(zhí)行之后總會(huì)帶來某種狀態(tài)的改變晨川，稱為后置狀態(tài)（Postcondition），比如歸并键思，前置狀態(tài)要求兩個(gè)子序列是排序的础爬，后置狀態(tài)要求整個(gè)序列是排序的，很多語言都提供了大同小異斷言機(jī)制吼鳞，比如Java的assert指令看蚜，并提供了激活斷言的開關(guān)功能。那么我們就可以在代碼中使用斷言赔桌，這至少有兩個(gè)好處供炎，首先斷言能夠盡可能早地發(fā)現(xiàn)程序中出現(xiàn)的潛在問題，提醒開發(fā)者代碼執(zhí)行的條件沒有被滿足疾党；其次音诫，它是一種文檔，明確地告知了算法執(zhí)行的先決條件和帶來的改變雪位，能夠提高代碼的易讀性竭钝。

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

  // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
  assert isSorted(a, lo, mid);
  assert isSorted(a, mid+1, hi);

  // copy to aux[]
  for (int k = lo; k <= hi; k++) {
    aux[k] = a[k]; 
  }

  // merge back to a[]
  int i = lo, j = mid+1;
  for (int k = lo; k <= hi; k++) {
    if      (i > mid)              a[k] = aux[j++];   // this copying is unnecessary
    else if (j > hi)               a[k] = aux[i++];
    else if (less(aux[j], aux[i])) a[k] = aux[j++];
    else                           a[k] = aux[i++];
  }

  // postcondition: a[lo .. hi] is sorted
  assert isSorted(a, lo, hi);
}

3.3 各個(gè)擊破：自頂向下的歸并

有了歸并，排序就被設(shè)計(jì)為一個(gè)遞歸的過程：每次都計(jì)算一個(gè)中間位置mid雹洗，然后遞歸地排序左右兩部分香罐，最后歸并排序好的子序列，當(dāng)hi <= lo時(shí)遞歸返回时肿，因?yàn)榇藭r(shí)子序列中沒有元素庇茫，不需要做任何操作，代碼如下所示螃成。因?yàn)閟ort是遞歸調(diào)用旦签，因此每個(gè)sort調(diào)用都會(huì)包含自己的merge過程查坪，也就保證了子序列在歸并前已經(jīng)是有序的了。歸并排序是一個(gè)速度很快的算法宁炫，有科學(xué)家做過經(jīng)驗(yàn)分析偿曙，通過實(shí)驗(yàn)分別在家用計(jì)算機(jī)和超級(jí)計(jì)算機(jī)上對(duì)比了她與插入排序的運(yùn)行效率，得到如圖3-4所示的實(shí)驗(yàn)結(jié)果淋淀，可以看到即使是百萬級(jí)的記錄歸并排序仍然是瞬間完成遥昧，插入排序卻需要等上300多年覆醇。

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

3-4 歸并與插入排序的效率對(duì)比

3-5 歸并排序的遞推公式

3-6 歸并算法效率的直觀解釋

對(duì)歸并排序的數(shù)學(xué)分析代表了對(duì)“分治”這一類算法進(jìn)行分析的基本模式朵纷，掌握了這種分析方法，當(dāng)我們面對(duì)各種分治算法時(shí)我們就可以用同樣的方法去分析它們的效率永脓。分治算法的效率分析通撑鄞牵可以通過解某一遞推公式來完成，就歸并排序而言常摧，因?yàn)槲覀兠看味紝⑿蛄幸环譃槎判蚝筮M(jìn)行歸并搅吁，如果我們假設(shè)C(N)為算法對(duì)長(zhǎng)度為N的序列進(jìn)行排序所需比較次數(shù)，那么我們可以得到如圖3-5所示的遞推公式落午。解這個(gè)遞推公式可以得到歸并排序的效率為NlgN谎懦，具體的推導(dǎo)過程這里就不贅述了，《算法導(dǎo)論》這本書上有全面而詳細(xì)的指導(dǎo)溃斋。這里只給出一個(gè)比較直觀的解釋界拦，如圖3-6所示。假設(shè)N為2的冪梗劫，我們可以將歸并排序一分為二的過程看成一棵樹享甸，這棵樹每一層都有N個(gè)結(jié)點(diǎn)，它會(huì)一直分解梳侨，而樹的高度為lgN蛉威，所以最后得到NlgN。

3.4 積少成多：自底向上的歸并

自頂向下的方法通常都存在著一個(gè)對(duì)稱的逆過程走哺，有時(shí)候我們也可以反過來想蚯嫌，用自底向上的思路去解決問題。前面提到丙躏，長(zhǎng)度為1的序列是天然有序的择示。那么我們可以多遍歷幾次，第一次將長(zhǎng)度為1的子序列歸并為有序的2-序列彼哼，然后將有序的2-序列歸并為4-序列……這樣反復(fù)進(jìn)行下去对妄，直到整個(gè)序列都?xì)w并為有序的，這樣連遞歸都不用了敢朱，兩層循環(huán)就能搞定剪菱。說起來簡(jiǎn)單摩瞎，但要真正實(shí)現(xiàn)的話，一些細(xì)微的地方要注意孝常。從下面的代碼示例可以看到旗们，外層循環(huán)從1開始，每次加倍构灸，因?yàn)榈谝淮我幚泶笮?的序列上渴，第二次要處理大小為2的序列，第三次則是大小為4的喜颁，以此類推稠氮。然后在每一次循環(huán)的內(nèi)部，用索引i來記錄每次要處理的序列頭部（一次迭代跳過sz+sz個(gè)元素）半开。我們分別計(jì)算lo隔披，m和hi，使得aux[lo..m]和aux[m+1..hi]為兩個(gè)相等長(zhǎng)度的待歸并子序列寂拆，然后仍然用上面提到的歸并方法進(jìn)行處理奢米。

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

3.5 基于比較的排序算法，其極限何在纠永？

我們已經(jīng)分析過的選擇排序鬓长，插入排序，Shell排序和歸并排序尝江，以及下面會(huì)談到的快速排序涉波，都可以看作是一類排序算法——基于比較的排序算法，也就是說茂装，它們只知道元素之間的大小關(guān)系怠蹂，其他的信息（比如是否有重復(fù)元素，是否部分有序等等）則完全不知少态。對(duì)于這一類算法城侧，我們可以通過一種叫“決策樹”的工具，得到一個(gè)計(jì)算復(fù)雜度方面的重要結(jié)論彼妻。圖3-7展示了對(duì)三個(gè)不同元素a嫌佑，b和c的排序過程。從根節(jié)點(diǎn)到某一葉子結(jié)點(diǎn)的路徑表示某次排序的比較序列侨歉，葉子結(jié)點(diǎn)表示最后得到的結(jié)果屋摇。首先，對(duì)于N個(gè)不同元素的排序決策樹幽邓，至少有N炮温！個(gè)葉子結(jié)點(diǎn)，因?yàn)橛蠳牵舵！種排列的可能柒啤。其次倦挂，二叉樹有一個(gè)重要的性質(zhì)，即高度為h的二叉樹最多有2^{h個(gè)葉子結(jié)點(diǎn)担巩。故得到公式2}h >= #leaf >= N!方援，即h >= lgN! >= NlgN（根據(jù)斯特林公式得到）。也就是說涛癌，我們對(duì)基于比較的排序算法建立的決策樹模型犯戏，其高度至少是NlgN，而樹的高度表示算法最大比較次數(shù)拳话，那么我們就能得出一個(gè)結(jié)論：最壞情況下所有基于比較的排序算法至少要用NlgN次比較先匪。
要注意，這是一個(gè)很重要的結(jié)論假颇。從這個(gè)結(jié)論胚鸯，我們可以得出這樣一個(gè)事實(shí)：歸并排序是時(shí)間最優(yōu)的，因?yàn)樗顗那闆r下比較次數(shù)為NlgN笨鸡。其次，不可能找到比較次數(shù)比這個(gè)還少的算法——因?yàn)檫@違反客觀規(guī)律了坦冠，但是形耗，這個(gè)結(jié)論同時(shí)啟發(fā)我們，應(yīng)該可以找到時(shí)間是NlgN辙浑，但空間效率更優(yōu)的算法激涤，可以從這個(gè)方向去想。另外一個(gè)細(xì)微之處在于判呕，該結(jié)論依據(jù)的基本假設(shè)條件是該序列是由N個(gè)不同的元素組成的倦踢，若序列中出現(xiàn)重復(fù)元素，或該序列是部分有序的侠草，那么算法的效率會(huì)比NlgN還要高辱挥。使用某個(gè)結(jié)論之前要考慮該結(jié)論成立的條件是否滿足，否則會(huì)鬧笑話的边涕。

圖3-7 比較排序算法的決策樹模型