摘要：我們討論比較排序算法的理論基礎(chǔ)，并結(jié)合本章應(yīng)用排序和優(yōu)先級(jí)隊(duì)列算法。基本排序引入了選擇排序，插入排序和。描述了，一種保證在線性時(shí)間內(nèi)運(yùn)行的排序算法。當(dāng)我們后續(xù)實(shí)現(xiàn)排序算法時(shí)，我們實(shí)際上將這個(gè)機(jī)制隱藏在我們的實(shí)現(xiàn)下面。

上一篇：棧和隊(duì)列
下一篇：歸并排序

排序是重新排列一系列對(duì)象以便按照某種邏輯順序排列的過程。排序在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學(xué)計(jì)算中起著重要作用。在交易處理，組合優(yōu)化，天體物理學(xué)，分子動(dòng)力學(xué)，語言學(xué)，基因組學(xué)，天氣預(yù)報(bào)和許多其他領(lǐng)域中的應(yīng)用比比皆是。
在本章中，我們考慮了幾種經(jīng)典的排序方法和一種稱為優(yōu)先級(jí)隊(duì)列的基本數(shù)據(jù)類型的有效實(shí)現(xiàn)。我們討論比較排序算法的理論基礎(chǔ)，并結(jié)合本章應(yīng)用排序和優(yōu)先級(jí)隊(duì)列算法。

2.1 基本排序引入了選擇排序，插入排序和 shellort。
2.2 Mergesort 描述了megesort，一種保證在線性時(shí)間內(nèi)運(yùn)行的排序算法。
2.3 Quicksort 描述了quicksort，它比任何其他排序算法使用得更廣泛。
2.4 優(yōu)先級(jí)隊(duì)列引入優(yōu)先級(jí)隊(duì)列數(shù)據(jù)類型和使用二進(jìn)制堆的有效實(shí)現(xiàn)。它還引入了 heapsort。
2.5 應(yīng)用程序描述了排序的應(yīng)用程序，包括使用備用排序，選擇，系統(tǒng)排序和穩(wěn)定性

進(jìn)行排列我們應(yīng)該遵循哪些規(guī)則呢？讓我們先看看典型基本排序問題。
比如，大學(xué)有很多學(xué)生檔案，對(duì)于每個(gè)學(xué)生有一些信息，可能是姓名、班級(jí)編號(hào)、成績、電話號(hào)碼、地址。

我們查看一個(gè)元素，那個(gè)元素有一條記錄，這個(gè)記錄就是我們要排序的信息，準(zhǔn)確地說，記錄中有一部分叫做關(guān)鍵字 (key)，
我們將記錄根據(jù)關(guān)鍵字進(jìn)行排列，這就是排序問題。

下圖將數(shù)組中的 n 個(gè)元素根據(jù)元素中的定義的關(guān)鍵字 (此為姓) 升序排列

排序的應(yīng)用：
排序的應(yīng)用很多，比如快遞的包裹，紙牌游戲，手機(jī)聯(lián)系人，圖書館的圖書編號(hào)等等。我們的目標(biāo)是能夠?qū)θ魏晤愋偷臄?shù)據(jù)進(jìn)行排序。
來看幾個(gè)客戶端程序。

public class StringSorter
{
     public static void main(String[] args)
     {
         String[] a = StdIn.readAllStrings();
         Insertion.sort(a);
         for (int i = 0; i < a.length; i++)
         StdOut.println(a[i]);
     }
}

這個(gè)例子中：

用 readString() 方法從文件中讀取字符串。

這個(gè)方法在我們的 StdIn 類里，需要一個(gè)文件作為參數(shù)，將第一個(gè)命令行參數(shù)作為文件名，從文件中讀取一個(gè)字符串?dāng)?shù)組，字符串以空白字符分隔，接下來又調(diào)用 Insertion.sort() 方法。

Insertion.sort 這個(gè)方法以數(shù)組 a 作為第一個(gè)實(shí)參，然后將數(shù)組中的字符串排序

這個(gè)例子中，words3.txt 有一些單詞，這個(gè)客戶端輸出的結(jié)果就是這些單詞重新按照字母表的順序排序的結(jié)果。

% more words3.txt
bed bug dad yet zoo ... all bad yes

% java StringSorter < words3.txt
all bad bed bug dad ... yes yet zoo
[suppressing newlines]

public class Experiment
{
     public static void main(String[] args)
     {
         int n = Integer.parseInt(args[0]);
         Double[] a = new Double[n];
         for (int i = 0; i < n; i++)
         a[i] = StdRandom.uniform();
         //調(diào)用插入排序方法
         Insertion.sort(a);
         for (int i = 0; i < n; i++)
         StdOut.println(a[i]);
     }
}

這個(gè)客戶端程序調(diào)用插入排序方法。它從標(biāo)準(zhǔn)輸入中讀取數(shù)字，放進(jìn)數(shù)組，然后調(diào)用 Insertion.sort（插入排序），最后打印輸出。
下邊的打印輸出的數(shù)字是從小到大排好序的。這看起來有點(diǎn)像人為設(shè)計(jì)的輸入，也有很多應(yīng)用中可以用隨機(jī)輸入作為好的輸入模型。

% java Experiment 10
0.08614716385210452
0.09054270895414829
0.10708746304898642
0.21166190071646818
0.363292849257276
0.460954145685913
0.5340026311350087
0.7216129793703496
0.9003500354411443
0.9293994908845686

import java.io.File;
public class FileSorter
{
     public static void main(String[] args)
     {
         File directory = new File(args[0]);
         File[] files = directory.listFiles();
         Insertion.sort(files);
         for (int i = 0; i < files.length; i++)
         StdOut.println(files[i].getName());
     }
}

% java FileSorter .
Insertion.class
Insertion.java
InsertionX.class
InsertionX.java
Selection.class
Selection.java
Shell.class
Shell.java
ShellX.class
ShellX.java

這個(gè)例子中，給定目錄中的文件名，我們要對(duì)文件排序。這次又用到了Java的File文件類。

我們用這個(gè)類中的 listFiles() 方法獲得包含給定目錄中所有文件名的數(shù)組。

Insertion.sort() 使用這個(gè)數(shù)組作為第一實(shí)參。

同樣，程序?qū)@些文件名進(jìn)行了排序，然后依次將文件名以字母表的順序打印輸出

這是三個(gè)不同的客戶端，對(duì)應(yīng)三種完全不同類型的數(shù)據(jù)。
任務(wù)的第一條規(guī)則：我們要考慮如何才能完成實(shí)現(xiàn)一個(gè)排序程序，可以被三個(gè)不同的客戶端用來對(duì)三種不同數(shù)據(jù)類型排序。
這里采取的方式是一種叫做回調(diào)的機(jī)制。

我們的基本問題是：在沒有元素關(guān)鍵字類型的任何信息的情況下如何比較所有這些數(shù)據(jù)。
答案是我們建立了一個(gè)叫做回調(diào)的機(jī)制

Callback = 對(duì)可執(zhí)行代碼的引用

客戶端將對(duì)象數(shù)組傳遞給排序函數(shù)sort()

sort() 方法根據(jù)需要調(diào)用 object 的比較函數(shù) compareTo()

有很多實(shí)現(xiàn)回調(diào)函數(shù)的辦法，和具體編程語言有關(guān)。不同的語言有不同的機(jī)制。核心思想是將函數(shù)作為實(shí)參傳遞給其他函數(shù)。
涉及到函數(shù)式編程思想，需要更深的理論，可以追溯到圖靈和徹奇。

?Java: interfaces.
?C: function pointers.
?C++: class-type functors.
?C#: delegates.
?Python, Perl, ML, Javascript: first-class functions.

Java中，有一種隱含的機(jī)制，只要任何這種對(duì)象數(shù)組具有 compareTo() 方法。排序函數(shù)就會(huì)在需要比較兩個(gè)元素時(shí)，回調(diào)數(shù)組中的對(duì)象對(duì)應(yīng)的compareTo()方法。

對(duì)于Java，因?yàn)橐诰幾g時(shí)檢查類型，使用了叫做接口的特殊方法。
接口 interfaces：一種類型，里頭定義了類可以提供的一組方法

public interface Comparable
{
   //可以看作是一種類似于合同的形式，這個(gè)條款規(guī)定：這種方法（和規(guī)定的行為）
   public int compareTo(Item that);
}

實(shí)現(xiàn)接口的類：必須實(shí)現(xiàn)所有接口方法

public class String implements Comparable//String 類承諾履行合同的條款
{
     ...
     public int compareTo(String that)
     {
     // 類遵守合約
     ...
     }
}

"簽署合同后的影響"：

可以將任何 String 對(duì)象視為 Comparable 類型的對(duì)象

在Comparable對(duì)象上，可以調(diào)用（僅調(diào)用）compareTo() 方法。

啟用回調(diào)。

后面我們會(huì)詳細(xì)介紹如何用Java接口實(shí)現(xiàn)回調(diào)。這個(gè)比較偏向編程語言的細(xì)節(jié)，但是確實(shí)值得學(xué)習(xí)，因?yàn)樗刮覀兡軌蛞灶愋桶踩姆绞绞褂脼槿魏晤愋蛿?shù)據(jù)開發(fā)的排序算法。

注：key point: no dependence on type of data to be sorted 關(guān)鍵點(diǎn)：不依賴于要排序的數(shù)據(jù)類型

我們已經(jīng)看了一些客戶端程序。這是那個(gè)對(duì)字符串進(jìn)行排序的客戶端程序 (上邊的例1)。

客戶端以某類型對(duì)象數(shù)組作為第一實(shí)參(Comparable[] a)，直接調(diào)用 sort() 方法。

Java中內(nèi)置了一個(gè)叫做Comparable（可比較的）的接口 ( java.lang.Comparable interface )

Comparable 接口規(guī)范要求實(shí)現(xiàn) Comparable 的數(shù)據(jù)類型要有一個(gè)compareTo()方法。這個(gè)方法是泛化的，會(huì)對(duì)特定類型的元素進(jìn)行比較
public interface Comparable{public int compareTo(Item that);}

當(dāng)我們實(shí)現(xiàn)要排序的對(duì)象（這里為String ）時(shí)我們就實(shí)現(xiàn) Comparable 接口
public class String implements Comparable

因?yàn)榕判蚴窃诤芏嗲樾沃幸褂玫牟僮?，Java標(biāo)準(zhǔn)庫中會(huì)用到排序的類型很多都實(shí)現(xiàn)了Comparable接口，意味著，這些數(shù)據(jù)類型具有實(shí)現(xiàn) compareTo()方法的實(shí)例方法。它將當(dāng)前對(duì)象 (a[j]) 與參數(shù)表示的對(duì)象 (a[j-1]) 相比較，根據(jù)具體的一些測(cè)試返回比較的結(jié)果，比如
返回 -1 表示小于；返回 +1 表示大于；返回0表示相等，排序算法的實(shí)現(xiàn)就只需要這么一個(gè)compareTo()方法。
在函數(shù)聲明的時(shí)候，它要求參數(shù)必須是 Comparable 類型數(shù)組 (Comparable[] a)，這意味著數(shù)組中的對(duì)象需要實(shí)現(xiàn) Comparable 接口，或者說對(duì)象必須有compareTo() 方法，然后排序代碼直接使用 compareTo() 對(duì)一個(gè)對(duì)象實(shí)例 (a[j]) 調(diào)用這個(gè)方法, 以另一個(gè)對(duì)象實(shí)例 (a[j-1]) 作為實(shí)參。
在這個(gè)例子中測(cè)試第一個(gè)是否小于第二個(gè)。關(guān)鍵在于排序?qū)崿F(xiàn)與數(shù)據(jù)類型無關(guān)，具體的比較由 Comparable 接口處理，不同類型的 Comparable 數(shù)組最終會(huì)以相同的方式排序，依賴于接口機(jī)制，回調(diào)到實(shí)際的被排序?qū)ο箢愋?(String) 的 compareTo() 代碼。

compareTo() 方法實(shí)現(xiàn)的是全序關(guān)系(total order)
全序關(guān)系整體來說就是元素在排序中能夠按照特定順序排列。

全序關(guān)系是一種二元關(guān)系 ≤ 滿足：

反對(duì)稱性 Antisymmetry ：v ≤ w 并且 w ≤ v 則這種情況成立的唯一可能是 v = w

傳遞性 Transitivity：v ≤ w 并且 w ≤ x，則 v ≤ x

完全性 Totality：要么 v ≤ w ，要么 w ≤ v，要么 v = w （沒有其他情況了）

有幾條很自然的規(guī)則，有三個(gè)性質(zhì)：

我們一般考慮作為排序關(guān)鍵字的很多數(shù)據(jù)類型具有自然的全序關(guān)系，如整數(shù)、自然數(shù)、實(shí)數(shù)、字符串的字母表順序、日期或者時(shí)間的先后順序等等

但不是所有的有序關(guān)系都是全序關(guān)系。
比如石頭、剪刀、布是不具有傳遞性。如果已知 v ≤ w，w ≤ x，你并不一定知道 v 是否 ≤ x
還有食物鏈也是，違反了反對(duì)稱性

Surprising but true. The <= operator for double is not a total order. (!)

按照 Java 中的規(guī)定我們需要實(shí)現(xiàn) compareTo() 方法，使得 v 和 w 的比較是全序關(guān)系。
而且按照規(guī)定：

如果是小于，返回負(fù)整數(shù)

如果相等返回0

如果當(dāng)前對(duì)象大于作為參數(shù)傳入的對(duì)象則返回正整數(shù)。

如果對(duì)象類型不相容，或者其中一個(gè)是空指針，compareTo() 會(huì)拋出異常

Java 內(nèi)置的可比類型：Java中很多數(shù)字、日期和文件等等標(biāo)準(zhǔn)類型按照規(guī)定都實(shí)現(xiàn)了 compareTo() 方法
自定義可比類型：如果我們自己實(shí)現(xiàn)的類型要用于比較，就要根據(jù)這些規(guī)則，自己去實(shí)現(xiàn) Comparable 接口

實(shí)現(xiàn)一般是直截了當(dāng)?shù)?。這里有個(gè)例子，這是Java中實(shí)現(xiàn)的 Date 日期數(shù)據(jù)類型的簡化版，我們用來演示實(shí)現(xiàn)Comparable接口

//在類聲明之后，我們寫implements Comparable 然后在泛型類型填上類名，因?yàn)槲覀兒竺嬷辉试S日期類型與其他日期類型比較
public class Date implements Comparable
{
     //Date類有三個(gè)實(shí)例變量: month,day,year
     private final int month, day, year;
     //構(gòu)造函數(shù)通過參數(shù)設(shè)置這些變量
     public Date(int m, int d, int y)
     {
         month = m;
         day = d;
         year = y;
     }
     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;
     }
}

如果想要比較兩個(gè)不同的日期,首先是檢查 this.year 是否小于 that.year, 當(dāng)前日期對(duì)象和作為參數(shù)的日期對(duì)象的年份進(jìn)行對(duì)比, 如果為“真”那么就是小于，返回-1。如果 this.year 更大，返回+1 否則，年份就是相同的，那么我們就必須檢查月份來進(jìn)行比較, 這樣一直比較到日期。只有三個(gè)變量完全相同才返回0.
這個(gè)例子實(shí)現(xiàn)了 Comparable 接口, 實(shí)現(xiàn)了compareTo()方法，可以將日期按照你期望的順序排列。

Java語言為我們提供了Comparable接口的機(jī)制，使我們能夠?qū)θ魏晤愋蛿?shù)據(jù)排序。當(dāng)我們后續(xù)實(shí)現(xiàn)排序算法時(shí)，我們實(shí)際上將這個(gè)機(jī)制隱藏在我們的實(shí)現(xiàn)下面。

我們采用的方式是將引用數(shù)據(jù)的兩個(gè)基本操作：比較和交換，封裝為靜態(tài)方法

Less. Is item v < w ?

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

方法 less() 以兩個(gè) Comparable 對(duì)象作為參數(shù)，返回 v.compareTo(w) < 0.

Exchange. Swap item in array a[] at index i with the one at index j.

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

當(dāng)我們對(duì)數(shù)組中的元素進(jìn)行排序時(shí)另一個(gè)操作是 swap，將給定索引 i 的對(duì)象與索引 j 的對(duì)象交換.
這個(gè)操作是每個(gè)程序員學(xué)習(xí)賦值語句的入門語句，將 a[i] 保存在變量 swap 中，a[j] 放進(jìn) a[i]，然后 swap 放回到 a[j]

我們的排序方法引用數(shù)據(jù)時(shí)只需要使用這兩個(gè)靜態(tài)方法。這么做有個(gè)很充分的理由。
舉個(gè)例子，假設(shè)我們想檢驗(yàn)數(shù)組是否是有序的。這個(gè)靜態(tài)方法中如果數(shù)組有序，則返回“真”，無序則返回“假”。
這個(gè)方法就是從頭至尾過一遍數(shù)組，檢查每個(gè)元素是否小于前一個(gè)元素。如果有一個(gè)元素比前一個(gè)元素小，那么數(shù)組就是無序的，返回“假”。如果直到數(shù)組結(jié)尾也沒有檢測(cè)到，那么數(shù)組是有序的。非常簡單的代碼。

第一個(gè)基本排序方法很簡單，叫做選擇排序。

選擇排序的思想如下：從未排序數(shù)組開始，我們用這些撲克牌舉例，在第 i 次迭代中，我們?cè)跀?shù)組剩下的項(xiàng)中找到最小的，這個(gè)情況下，2 是所有項(xiàng)中最小的，然后，我們將它和數(shù)組中的第一項(xiàng)交換，這一步就完成了。
選擇排序就是基于這樣的思想迭代操作。

基本的選擇排序方法是在第 i 次迭代中，在數(shù)組中第i項(xiàng)右邊剩下的或者索引比 i 更大的項(xiàng)中找到最小的一項(xiàng)，然后和第 i 項(xiàng)交換。
開始 i 是 0，從最左端開始掃描所有右邊剩下的項(xiàng)，最小的是2，右起第3項(xiàng)，那么我們把第 i 項(xiàng)和最小項(xiàng)交換，這是第一步。
i左邊部分的數(shù)組就是排過序的。然后 i + 1，繼續(xù)重復(fù)的操作。
i + 1 為了尋找最小的項(xiàng)都要掃描全部剩下的項(xiàng)，但一旦找到之后，只需要交換兩張牌，這就是選擇排序的關(guān)鍵性質(zhì)。

最后 8 是最小的，這時(shí)，我們知道已經(jīng)是有序的了，但是程序不知道，所以必須檢查并且做決定。i 和 min 相同，自己和自己交換，最后一次迭代。這個(gè)過程結(jié)束后，我們知道整個(gè)數(shù)組已經(jīng)是最終狀態(tài)，是有序的了。

選擇排序的完整動(dòng)態(tài)演示點(diǎn)此

理解算法工作方式的一個(gè)辦法是考慮其不變性。
對(duì)于選擇排序，我們有個(gè)指針，變量 i，從左到右掃描。 假設(shè)我們用箭頭表示這個(gè)指針，如下圖， 不變式就是：

箭頭左邊的項(xiàng)不會(huì)再變了，它們已經(jīng)是升序了

箭頭右邊的項(xiàng)都比箭頭左邊的項(xiàng)大，這是我們確立的機(jī)制

算法通過找到右邊最小的項(xiàng)，并和箭頭所指的右邊下一項(xiàng)交換來維持不變性。

為了維持算法的不變式，我們需要：

向右移動(dòng)指針 i 加 1

在指針的右邊找到最小的索引

交換最小索引與當(dāng)前指針的值

向右移動(dòng)指針 i 加1后，不變式有可能被破壞，因?yàn)橛锌赡茉谥羔樣疫呌幸粋€(gè)元素比指針?biāo)傅脑匦?dǎo)致不變式被破壞，我們要做的是找到最小項(xiàng)的索引，然后交換，一旦我們完成了交換，我們又一次保留了不變式。這時(shí)指針左邊元素不會(huì)再變了，右邊也沒有更小的元素，這也就給出了實(shí)現(xiàn)選擇排序的代碼。

實(shí)現(xiàn)不變性的代碼如下：

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

public class Selection {
    public static void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
        //在指針右邊找到最小項(xiàng)
            int min = i;
            for (int j = i + 1; j < n; j++)
                if (less(a[j], a[min]))
                    min = j;
            //交換最小索引與當(dāng)前指針的值
            exch(a, i, min);
        }
    }

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

    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
    
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i]);
        }
    }
    
    //寫一個(gè)超簡單的客戶端
    public static void main(String[] args) {
        String[] a = {"1","5","3","8","4","1","4","5"};
        Selection.sort(a);
        show(a);
    }
}

我們將數(shù)組的長度記為 n, for循環(huán)遍歷數(shù)組中每個(gè)元素變量, min用來存儲(chǔ)指針 i 右邊最小元素的索引, 內(nèi)層的 j 的for循環(huán)，如果找到更小的值，則重設(shè)min 一旦檢查完 i 右側(cè)所有的元素，將最小的和第 i 項(xiàng)交換, 這就是選擇排序的完整實(shí)現(xiàn)。

值得注意的是當(dāng)我們嘗試編譯的時(shí)候會(huì)出現(xiàn)如下警告：

發(fā)生的原因：

實(shí)質(zhì)上，此警告表示 Comparable 對(duì)象無法與任意對(duì)象進(jìn)行比較。 Comparable 是一個(gè)泛型接口，其中類型參數(shù) T 指定可以與此對(duì)象進(jìn)行比較的對(duì)象的類型。

因此，為了正確使用Comparable ，需要使排序列表具有通用性，以表達(dá)一個(gè)約束，即列表存儲(chǔ)的對(duì)象可以與同個(gè)類型的對(duì)象相互比較，如下所示：

public class SortedList> {
    public void add(T obj) { ... }
    ...
}

所以我們的代碼要改成沒有編譯警告的類型安全的版本：

為選擇排序的開銷建立數(shù)學(xué)模型非常容易.
命題：選擇排序使用大約 n^2 / 2 個(gè)比較以及，整 n 次交換。

(n – 1) + (n – 2) + ... + 1 + 0 ~ n^2 / 2

只要看看這個(gè)選擇排序運(yùn)行的跟蹤記錄，這就是這個(gè)命題的圖形證明。
圖中：

黑色的項(xiàng)是每次為了尋找最小項(xiàng)檢查的項(xiàng)

最小項(xiàng)是紅色的

灰色的項(xiàng)是未檢查的項(xiàng)，已經(jīng)在最終位置了

你可以看到這基本就是 n x n 的正方形，其中大約一半的元素是黑色的，即大約 n^2 / 2，你也能看出準(zhǔn)確的表達(dá)式(n – 1) + (n – 2) + ... + 1 + 0, 就是總共比較的次數(shù)。然后在變量 i 的這 n 個(gè)取值各有一次交換，所以這是交換次數(shù)的開銷。

關(guān)于選擇排序的這個(gè)命題說明了很有意思的一點(diǎn)，就是它和輸入的序列本身的順序無關(guān)。

選擇排序需要平方時(shí)間因?yàn)樗傄榭?strong>所有的項(xiàng)尋找最小項(xiàng)

另一個(gè)性質(zhì)就是要完成排序這已經(jīng)是移動(dòng)開銷最小的了，選擇排序只需要線性次數(shù)的交換
每一項(xiàng)都是僅僅一次交換就放在了最終位置。

選擇排序指針由左至右掃描，每次掃描找到右邊最小的項(xiàng)，交換到它最終的位置上。如果數(shù)組一部分已經(jīng)排好序了，這對(duì)選擇排序不影響，依然要一遍一遍掃描，即使是完全有序的，依然要掃描右邊的項(xiàng)來找最小的元素。這就是選擇排序，我們第一個(gè)基本排序方法

Q. 如果數(shù)組已經(jīng)排好序，那么插入排序比較需要多少次？

對(duì)數(shù)級(jí)

線性級(jí)

平方級(jí)

立方級(jí)別

A. 查看附錄

插入排序，這是另外一種基本排序方法，有趣的是 相比選擇排序插入排序具有相當(dāng)不同的性能。

下邊是一個(gè)插入排序的演示。對(duì)于插入排序，我們要做的和之前一樣，從左到右移動(dòng)索引 i，但現(xiàn)在，在第 i 個(gè)迭代中 我們將會(huì)把 a[ i ] 移動(dòng)到其左側(cè)的位置，讓我們用牌的示例來看看這是怎么工作的。
現(xiàn)在我們從初始化 i 為第一張牌開始，我們的想法是 i 的左邊的所有紙牌將會(huì)被排序，右邊的紙牌，我們?nèi)肯榷疾蝗タ?br>所以，i 左側(cè)所有的紙牌是升序，右側(cè)所有的紙牌我們現(xiàn)在還沒檢查過，第二步我們?cè)黾?i ，在這種情況下指針左邊已經(jīng)排好序了，我們什么也不用做。
當(dāng) i 是數(shù)組中的第三項(xiàng)時(shí)，此時(shí)我們從索引 j 開始，然后，j 從 i 開始向左邊移動(dòng)，我們要做的是將5與它左邊更大的元素交換，那么，首先與10交換，依然沒有到最終位置，所以再和7交換，現(xiàn)在已經(jīng)到數(shù)組最前面了，一旦我們檢查完左側(cè)所有項(xiàng)或者找到一個(gè)更小的元素，i 左邊所有項(xiàng)就排好序了

插入排序完整演示在此

一旦完成之后，從 i 開始它左側(cè)的數(shù)組就是升序的，i 左邊就都排好序了，所以這個(gè)情形中我們用更少的工作量就完成了排序，并不總是需要一直檢查到數(shù)組的開頭

我們?cè)購牟蛔兪降慕嵌葋砜床迦肱判?/p>

指針依然是從左至右掃描，

指針左邊的所有元素，包括指針指向的元素，都是排好序的

而右邊的元素都還完全沒有檢查過

我們來看隨著指針遞增維持不變式的代碼

將指針向右側(cè)移動(dòng)，增加 1，因?yàn)橹羔樦赶虻脑貨]排過序，所以破壞了不變式，那么為了維持不變式， 要將它排序，需要將它和左邊每個(gè)更大的元素交換。下面的代碼完成的就是這個(gè), 索引 j 從 i 開始，逐漸變小， j 指向的元素與左邊的元素交換, a[j] 與左邊的元素 a[j-1] 交換, 只要a[j]小于 a[j-1] 并且 j > 0 就一直交換, 我們就馬上得到了插入排序的代碼。

import edu.princeton.cs.algs4.StdOut;

public class InsertionPedantic {

    public static > void sort(Comparable[] a) {
        int n = a.length;
       
        for (int i = 0; i < n; i++)
            for (int j = i; j > 0; j--)
            // a[j] 與左邊的元素 a[j-1] 交換, 只要a[j]小于 a[j-1] 并且 j > 0 就一直交換
                if (less(a[j], a[j - 1]))
                    exch(a, j, j - 1);
                else break;
    }

    // 以下代碼與選擇排序一樣
    private static > boolean less(Key v, Key w) {
        return v.compareTo(w) < 0;
    }

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

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

    public static void main(String[] args) {
        String[] a = {"1", "5", "3", "8", "4", "1", "4", "5"};
        InsertionPedantic.sort(a);
        show(a);
    }
}

與選擇排序的代碼類似，而且一樣簡單，有兩個(gè)嵌套的for循環(huán)，選擇排序也是一樣，循環(huán)中需要進(jìn)行一次檢查，一次比較大小，和一次交換。這是基本排序方法的一個(gè)良好的實(shí)現(xiàn)。

插入排序更復(fù)雜一些，我們的命題是：
對(duì)具有不同關(guān)鍵值的隨機(jī)序列排序，
Average case 平均情況：插入排序平均需要使用大約 1/4 n^2 次比較, 與大約相同的 1/4 n^2 的交換次數(shù)。
這個(gè)要證明的話更復(fù)雜一些，和隨機(jī)順序的數(shù)組有關(guān)。和選擇排序的證明一樣，從這個(gè) nxn 的算法步驟中, 你可以找到命題來源的思路。
黑色的元素依然是我們比較的，實(shí)際上，也是進(jìn)行交換的。紅色的是到達(dá)的最終位置。

你可以看到對(duì)于隨機(jī)順序的大數(shù)組，要移動(dòng)到最終位置平均要移動(dòng)大約一半的位置，這意味著對(duì)角線以下的元素，平均一半是黑色的 對(duì)角線以下的元素有1/2 n^2 個(gè) 一半就是1/4 n^2 精確的分析比這個(gè)詳細(xì)不了多少,這個(gè)步驟更多，下圖再次顯示排序過程中對(duì)比和交換的操作涉及到對(duì)角線下大約一半的元素。

因?yàn)?1/4 n^2 和 1/2 n^2 相比小一半, 插入排序的速度大約是選擇排序的兩倍, 所以相同時(shí)間內(nèi)演示中我們能夠?qū)Υ蠹s兩倍的元素進(jìn)行排序

插入排序運(yùn)行時(shí)間取決于數(shù)據(jù)開始的順序。
我們來看看最好與最壞的情況，當(dāng)然這些都是異常的情況：

Best case：
如果數(shù)組恰好已經(jīng)排好序了，插入排序?qū)嶋H上只需要驗(yàn)證每個(gè)元素比它左邊的元素大，所以不用進(jìn)行交換，只需要 n-1 次比較就能完成排序工作。

Worst case：
如果數(shù)組是降序排列的，并且不存在重復(fù)值，每個(gè)元素都移動(dòng)到數(shù)組開頭那么就需要進(jìn)行1/2 n^2 次比較與1/2 n^2 次交換

所以第一種情況下，插入排序比選擇排序快得多, 是線性時(shí)間的而不是平方時(shí)間的, 而第二種情形中，比選擇排序慢，因?yàn)樾枰粯拥谋容^次數(shù)，但是多得多的交換次數(shù)。元素降序排列的情況，每次得到一個(gè)新元素，都必須一直交換到最開頭。這是實(shí)際應(yīng)用中我們不想見到的最壞的情況。

但也有好的情況，在很多實(shí)際應(yīng)用中我們都在利用這一點(diǎn)，就是數(shù)組已經(jīng)部分有序的情況，用定量的方法考慮問題。

我們定義：一個(gè)“逆序?qū)Α?inversion)是數(shù)組中亂序的關(guān)鍵值對(duì)

例如：
A E E L M O T R X P S
其中有6個(gè)逆序?qū)Γ篢-R T-P T-S R-P X-P X-S

T和R是亂序的，因?yàn)镽應(yīng)該在T的前面 T和P是亂序的，等等

我們定義：如果一個(gè)數(shù)組的逆序?qū)?shù)量是線性的(或者說逆序?qū)Φ臄?shù)量 ≤ cn， 其中 c 代表一個(gè)常數(shù)），那么這個(gè)數(shù)組是部分有序的。

部分有序的數(shù)組在實(shí)際應(yīng)用中經(jīng)常遇到，例如有一個(gè)大數(shù)組是有序的，只有最后加上的幾個(gè)元素是無序的，那么這個(gè)數(shù)組就是部分有序的；
或者另外的情況，只有幾個(gè)項(xiàng)不在最終位置，這個(gè)數(shù)組也是部分有序的。
實(shí)際應(yīng)用中經(jīng)常出現(xiàn)這樣的情況，插入排序有意思的地方在于對(duì)于部分有序的數(shù)組。

我們定義：插入排序在部分有序數(shù)組上的運(yùn)行時(shí)間是線性的
證明：

就是交換的次數(shù)與逆序?qū)Φ膫€(gè)數(shù)相等 (沒交換一次，逆序?qū)蜏p少一個(gè))

比較的次數(shù) ≤ 交換的次數(shù) + (n-1) (可能除了最后一個(gè)元素，在每次迭代中，一次比較會(huì)觸發(fā)一次交換)

Binary insertion sort
使用二分查找來找出插入點(diǎn)

對(duì)比所需要的次數(shù) ~ nlgn (lg 以 2 為底)

二分查找的算法分析在這有

但是訪問數(shù)組的次數(shù)依舊是平方級(jí)的

這就是插入排序 我們學(xué)習(xí)的第二個(gè)基本排序方法。

Q. 如果數(shù)組已經(jīng)是升序排好的，那么插入排序?qū)⑦M(jìn)行多少次比較？

常數(shù)次

對(duì)數(shù)次

線性次

平方級(jí)次

A. 見附錄

希爾排序的出發(fā)點(diǎn)是插入排序。插入排序有時(shí)之所以效率低下是因?yàn)槊總€(gè)元素每次只向前移動(dòng)一個(gè)位置，即使我們大概知道那些元素還需要移動(dòng)很遠(yuǎn)。
希爾排序的思想在于每次我們會(huì)將數(shù)組項(xiàng)移動(dòng)若干位置(移動(dòng) h 個(gè)位置)，這種操作方式叫做對(duì) 數(shù)組進(jìn)行 h-sorting (h - 排序)。
所以h-sorted array h-有序的 數(shù)組 包含 h 個(gè)不同的交叉的有序子序列。
例如，這里 h = 4，如果從 L 開始，檢查每第四個(gè)元素 - M，P，T - 這個(gè)子數(shù)組(L M P T)是有序的,
從第二個(gè)位置 E 開始，檢查每第四個(gè)元素，- H, S, S - 是有序的...

這里一共有4個(gè)交叉的序列，這個(gè)數(shù)組 是經(jīng)過 h-sorting 后的 h-sorted 數(shù)組，這里即是數(shù)組 {L E E A M H L E P S O L T S X R} 是經(jīng)過 4-排序 后的 4-有序 的數(shù)組。

我們想用一系列遞減 h 值的 h-排序 實(shí)現(xiàn)一種排序方法，這種排序方法由希爾(Shell)于1959年發(fā)明，是最早的排序方法之一。

又一例子：

這個(gè)例子中，從這里所示的輸入 {S H E L L S O R T E X A M P L E} 開始，首先進(jìn)行13-排序，移動(dòng)幾個(gè)項(xiàng)，然后是 4-排序，移動(dòng)的項(xiàng)多了一些，最后，1-排序。
這種算法的思想在于每次排序的實(shí)現(xiàn)基于前面排過序的序列，只需要進(jìn)行少數(shù)幾次交換。

Q. 那么首先我們?cè)鯓訉?duì)序列進(jìn)行 h-排序呢？
A. 實(shí)際上很簡單, 直接用插入排序，但是之前是每次獲取新的項(xiàng)往回走一個(gè)，現(xiàn)在往回走 h 個(gè)，所以代碼和插入排序是一樣的，只不過順著數(shù)組往回查看的時(shí)候之前每次只退1個(gè)，現(xiàn)在跳 h 個(gè)。這就是對(duì)數(shù)組進(jìn)行h-排序的方法。

這里我們使用插入排序的原因基于我們對(duì)插入排序原理的理解有兩點(diǎn)：

首先是如果增量 h 很大。那么進(jìn)行排序的子數(shù)組長度就很小，包括插入排序在內(nèi)的任何排序方法都會(huì)有很好的性能

另一點(diǎn)是如果增量小，因?yàn)槲覀冎耙呀?jīng)用更大的h值進(jìn)行了 h-排序，數(shù)組是部分有序的，插入排序就會(huì)很快

用選擇排序作為 h-排序 的基礎(chǔ)就不行，因?yàn)闊o論序列是什么順序，它總需要平方時(shí)間，數(shù)組是否有序?qū)x擇排序沒有任何影響。

我們看一個(gè)希爾排序的例子，增量是7、3、1
下圖每一行的標(biāo)注了紅色的項(xiàng)就是本次迭代中發(fā)生過移動(dòng)的項(xiàng)

我們從 input 序列開始，先對(duì)它進(jìn)行7-排序，進(jìn)行的就是插入排序，只不過每次回退7。如果是增量是 7，也就是兩個(gè)元素間隔 6 個(gè)元素這么取子序列，有4個(gè)子序列，各只包含2個(gè)元素。

然后進(jìn)行3-排序。因?yàn)橐呀?jīng)進(jìn)行過7-排序，進(jìn)行 3-排序 的元素要么已經(jīng)在最終位置，要么只需要移動(dòng)幾步。這個(gè)例子中，只有 A 移動(dòng)了兩步。

然后進(jìn)行 1-排序，因?yàn)閿?shù)組已經(jīng)經(jīng)過 7-排序 和 3-排序，需要進(jìn)行 1-排序 時(shí)，數(shù)組已經(jīng)基本有序了，大多數(shù)的項(xiàng)只移動(dòng)一兩個(gè)位置。

所以我們只需要進(jìn)行幾次額外的高增量排序，但是每個(gè)元素都只向它們的最終位置移動(dòng)了幾次，這是希爾排序的高效之處。實(shí)際上一旦進(jìn)行了 1-排序，就是進(jìn)行了插入排序，所以最終總能得到正確排序的結(jié)果。唯一的區(qū)別就是能有多高效

對(duì)希爾排序更直觀的理解可以通過數(shù)學(xué)證明。如果序列經(jīng)過 h-排序的，用另一個(gè)值 g 進(jìn)行 g-排序，序列仍然是 h-有序的。
一個(gè) h-有序的 數(shù)組是 h 交錯(cuò)排序后的子序列。

我們的命題：h-有序的 數(shù)組經(jīng)過 g-排序 后依然是 h-有序的

如下圖：
3-sort[] = {A E L E O P M S X R T} 是數(shù)組 a[] = {S O R T E X A M P L E} 經(jīng)過 7-排序 后，再經(jīng)過 3-排序 后的數(shù)組，
3-sort[] 肯定是 7-有序的 數(shù)組，當(dāng)然也是 3-有序的，對(duì)7,3排序后得的序列 {A E L E O P M S X R T} 進(jìn)行觀察, 每向右移動(dòng)7位：
{A-S},{E-X},{L-R},{E-T}都是升序的，所以 3-sort[] 是 7-有序的 數(shù)組.
這就是那些看起來很顯然但是如果你試著證明它，會(huì)比你想的復(fù)雜一些的命題之一 -_-||, 而大多數(shù)人將這一點(diǎn)認(rèn)定為事實(shí)，這是希爾排序高效之處。

另一個(gè)問題就是對(duì)于希爾排序我們應(yīng)當(dāng)使用哪種步長序列.

首先能想到的想法可能是試試2的冪, 1, 2, 4, 8, 16, 32, ...實(shí)際上這個(gè)行不通，因?yàn)樗谶M(jìn)行1-排序之前不會(huì)將偶數(shù)位置的元素和奇數(shù)位置的元素進(jìn)行比較，這意味著性能就會(huì)很差。

希爾自己的想法是嘗試使用2的冪減1序列，1, 3, 7, 15, 31, 63, …這是行得通的。

Knuth在60年代提出用 3x+1 的增量序列，如 1、4、13、40、121、364等，這也不錯(cuò)

我們使用希爾排序的時(shí)候，我們首先找到小于待排序數(shù)組長度最大的增量值，然后依照遞減的增量值進(jìn)行排序。但是尋找最好的增量序列是一個(gè)困擾了人們相當(dāng)長時(shí)間的研究問題。

這是 Sedgewick 教授(這門課的主講老師之一)經(jīng)過大概一年的研究得出的增量序列，1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, …
(該序列的項(xiàng)來自 9 x 4^i - 9 x 2^i + 1 和 2^{i+2} x (2^{i+2} - 3) + 1 這兩個(gè)算式。這項(xiàng)研究也表明 “ 在希爾排序中是最主要的操作是比較，而不是交換?！?br>用這樣步長序列的希爾排序比插入排序要快，甚至在小數(shù)組中比快速排序和堆排序還快，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢。這個(gè)步長序列性能也不錯(cuò)，但是無法得知是否是最好的

這是用Java實(shí)現(xiàn)的希爾排序，使用 Knuth 的 3x+1 增量序列

import edu.princeton.cs.algs4.StdOut;

public class Shell {

    /**
     * 對(duì)數(shù)組進(jìn)行升序排序
     * @param 需要排序的數(shù)組
     */
    public static > void sort(Key[] 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;// 至于為什么是 h < n/3 請(qǐng)查看附錄

        while (h >= 1) {
            // 對(duì)數(shù)組進(jìn)行 h-排序 (基于插入排序)
            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);
                }
            }
            assert isHsorted(a, h);
            // 計(jì)算下一輪排序使用的增量值
            h /= 3;
        }
        /**
         * assert [boolean 表達(dá)式]
         * 如果[boolean表達(dá)式]為true，則程序繼續(xù)執(zhí)行。
         * 如果為false，則程序拋出AssertionError，并終止執(zhí)行。
         * assert [boolean 表達(dá)式]："expression"
         */
        assert isSorted(a);
    }

    // is v < w ?
    private static > boolean less(Key v, Key w) {
        return v.compareTo(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;
    }


    // 檢查數(shù)組是否已排好序
    private static > boolean isSorted(Key[] a) {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

    // 檢查數(shù)組是否是 h-有序的?
    private static >  boolean isHsorted(Key[] a, int h) {
        for (int i = h; i < a.length; i++)
            if (less(a[i], a[i-h])) return false;
        return true;
    }

    // 打印數(shù)組到標(biāo)準(zhǔn)輸出
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i]);
        }
    }

    // 簡單客戶端
    public static void main(String[] args) {
        String[] a = {"1","5","3","8","4","1","4","5"};
        Shell.sort(a);
        show(a);
    }
}

我們直接計(jì)算小于 n/3 的最大增量, 然后以那個(gè)值開始，比如從 364 開始，需要計(jì)算下一個(gè)增量時(shí)，直接 364 整除 3 等于 121，121 整數(shù)除 3 等于 40 等。這句 h = h / 3 計(jì)算下一輪排序使用的增量值。

實(shí)現(xiàn)就是基于插入排序。進(jìn)行插入時(shí) i 從 h 開始，然后 j 循環(huán)，每次 j 減小 h，不然代碼就和插入排序一模一樣了。所以，只需要給 h-排序 加上額外的循環(huán)計(jì)算插入排序的增量，代碼變得稍微復(fù)雜了一些，但是對(duì)于大數(shù)組運(yùn)行起來，Shell排序的效率要比插入排序高得多。
隨著h值遞減，每次 h-排序 后數(shù)組越來越有序

對(duì)于 3x+1 的增量序列最壞情況下比較的次數(shù)是 O(N^3/2)，實(shí)際應(yīng)用中比這個(gè)小得多。
問題是沒有精確的模型能夠描述使用任何一種有效的增量序列的希爾排序需要進(jìn)行比較的次數(shù)。
下圖是通過 Doubling hypothesis 方法，簡單說就是翻倍輸入的方法對(duì)希爾排序的性能試驗(yàn)得出的結(jié)果 與 推斷的函數(shù)模型計(jì)算值的對(duì)比

N:原始輸入數(shù)據(jù)的大??；compares：對(duì)應(yīng)的輸入需要通過多次比較得到完全有序數(shù)組；
N^1.289: 對(duì)應(yīng)輸入大小的1.289次冪；2.5 N lg N：對(duì)應(yīng)輸入的對(duì)數(shù)計(jì)算值

希爾排序的比較次數(shù)是 n 乘以增量的若干倍，即 n 乘以 logn 的若干倍,但是沒人能夠構(gòu)建精確的模型對(duì)使用有效的增量序列的希爾排序證明這一點(diǎn)。

那我們?yōu)槭裁催€對(duì)這個(gè)算法感興趣呢？因?yàn)檫@個(gè)算法的思想很簡單，而且能獲得巨大的性能提升。它相當(dāng)快，所以在實(shí)際中非常有用除了巨大的數(shù)組會(huì)變得慢，對(duì)于中等大小的數(shù)組，它甚至可以勝過經(jīng)典的復(fù)雜方法。代碼量也不大，通常應(yīng)用于嵌入式系統(tǒng)，或者硬件排序類的系統(tǒng)，因?yàn)閷?shí)現(xiàn)它只需要很少的代碼。

還有就是它引出了很多有趣的問題。這就涉及到了開發(fā)算法的智力挑戰(zhàn)。如果你覺得我們已經(jīng)研究了這么長時(shí)間的東西很平凡，可以去試著找一個(gè)更好的增量序列。嘗試一些方法發(fā)現(xiàn)一個(gè)，并且試著就希爾排序的一般情況的性能得出一些結(jié)論。人們已經(jīng)嘗試了50年，并沒有獲得多少成果。
我們要學(xué)到的是我們不需要很多的代碼就能開發(fā)出很好的算法和實(shí)現(xiàn)，而依然有一些等待被發(fā)現(xiàn)，也許存在某個(gè)增量序列使得希爾排序比其他任何適用于實(shí)際序列大小的排序方法都快，我們并不能否認(rèn)這一點(diǎn)。這就是希爾排序，第一個(gè)不平凡的排序方法。

接下來我們將一起看一個(gè)排序的簡單應(yīng)用, 這個(gè)應(yīng)用叫做洗牌.
假設(shè)你有一副撲克牌, 你可能會(huì)想要做的事之一就是隨機(jī)地進(jìn)行擺放卡牌(目標(biāo)), 這就是洗牌。

我們有一種利用排序來進(jìn)行洗牌的方法，雖然排序似乎正好與洗牌相反。
這種方法的構(gòu)想是為一個(gè)數(shù)組元素產(chǎn)生一個(gè)隨機(jī)實(shí)數(shù)，然后利用這些隨機(jī)數(shù)作為排序依據(jù)。

這是一種很有效的洗牌方法，并且我們可以證明這種方法在輸入中沒有重復(fù)值，并且你在可以產(chǎn)生均勻隨機(jī)實(shí)數(shù)的情況下，就能夠產(chǎn)生一個(gè)均勻的隨機(jī)排列。如果每種可能的撲克牌排列方式都有相同的出現(xiàn)概率，那就說明這種洗牌方法是正確的。

正確固然好，但這種方法需要進(jìn)行一次排序，似乎排序?qū)τ谶@個(gè)問題來說有些累贅?，F(xiàn)在的問題是我們能否做得更好。我們能找到一種更快的洗牌方法嗎? 我們真的需要付出進(jìn)行一次完整排序的代價(jià)嗎? 這些問題的答案是否定的。
實(shí)際上有一種非常簡單的方法，可以產(chǎn)生一副均勻隨機(jī)排列的撲克牌，它只需要線性的時(shí)間來完成工作。這種方法的理念是將序數(shù) i 從左到右地遍歷數(shù)組，i 從 0 到 n 增量。我們從一個(gè)已經(jīng)有序的數(shù)組開始洗牌，實(shí)際上數(shù)組的初始情況并不影響洗牌，每次我們都均勻隨機(jī)地從 0 和 i 之間挑選一個(gè)整數(shù)，然后將 a[i] 與這個(gè)數(shù)代表的元素交換。

洗牌動(dòng)態(tài)演示鏈接

開始時(shí)我們什么也不做，只把第一個(gè)元素和它自己交換位置，

i 變成了2或者說 i 指向了第二張牌，我們隨機(jī)生成一個(gè) r (在 0 和 i 之間的整數(shù)，因?yàn)?r 是隨機(jī)均勻生產(chǎn)的，所以 r 有可能等于 i，i 和 r 的值相同就不用進(jìn)行交換)， 然后我們將這 i 位置和 r 位置的兩張牌

遞增 i 的值，然后生成一個(gè)隨機(jī)整數(shù) r，再交換

一直這樣繼續(xù)進(jìn)行交換位置。對(duì)于每一個(gè) i 的值，我們都正好進(jìn)行一次交換, 可能有些牌經(jīng)歷了不止一次交換, 但這并不存在問題, 重點(diǎn)是在第
i 張牌左邊的牌都是被均勻地洗過去的，在最后我們就會(huì)獲得一副洗好的撲克牌。
這是一個(gè)利用隨機(jī)性的線性時(shí)間洗牌算法，它在很早之前就被證明是正確的，那時(shí)甚至電腦實(shí)現(xiàn)還未被發(fā)明。如果你使用這種方法的話，你會(huì)在線性時(shí)間內(nèi)得到一個(gè)均勻隨機(jī)的排列，所以，這絕對(duì)是一種簡單的洗牌方法。

在每次迭代中，隨機(jī)均勻地選擇 0 和 i 之間的整數(shù) r

交換 a[i] 和 a[r].

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

public class Shuffling {

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

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

    // simple client
    public static void main(String[] args) {

        int[] a = {1,2,3,4,5,6,7,8,9};
        shuffle(a);
        show(a);
    }
}

分別進(jìn)行三次洗牌：

它實(shí)現(xiàn)起來也很簡單，生成的隨機(jī)數(shù)均勻分布在 0 和 i 之間 (至關(guān)重要!)。
你會(huì)經(jīng)?？吹匠绦騿T們自以為他們實(shí)現(xiàn)了一個(gè)洗牌應(yīng)用，實(shí)際上他們經(jīng)常只是為每個(gè)數(shù)組位置選擇了一個(gè)隨機(jī)數(shù)組位置與之交換，這種方法實(shí)際上并不能實(shí)現(xiàn)真正的洗牌。你可以對(duì)編號(hào)為 i 和 n-1 之間的那些你還沒有看到過的牌進(jìn)行操作，但這種方法并不能洗出一副均勻隨機(jī)的卡牌。
下面是一個(gè)關(guān)于軟件安全的例子，在軟件安全領(lǐng)域有很多難度高并且深層次的問題，但是有一件事是我們可以做的那就是確保我們的算法和宣傳中中說的一樣好。
這里有一個(gè)在線撲克游戲的實(shí)現(xiàn)案例在此, 下面就是你可以在網(wǎng)頁上找到的洗牌算法案例的代碼

Bugs：

隨機(jī)數(shù) r 永遠(yuǎn)不會(huì)等于 52 ? 這意味著最后一張牌會(huì)始終在最后一位出現(xiàn)

這樣洗出的牌不是均勻的 應(yīng)該在 1 到 i 或者 i+1 和 52 之間隨機(jī)挑牌交換

另一個(gè)問題是在這種實(shí)現(xiàn)方式中使用一個(gè) 32 位數(shù)字生成隨機(jī)數(shù)。如果你這么做的話并不能涵蓋全部可能的洗牌方式。如果共有52張牌，可能的洗牌方法一共有 52 的階乘那么多種，這可比 2 的 32 次冪大得多，所以這種方法根本無法產(chǎn)生均勻隨機(jī)的牌組

另一個(gè)漏洞則是生成隨機(jī)數(shù)的種子是從午夜到現(xiàn)在這段時(shí)間經(jīng)歷的毫秒數(shù)，這使得可能的洗牌方式變得更少了。事實(shí)上，并不需要多少黑客技巧，一個(gè)人就能從 5 張牌中看出系統(tǒng)時(shí)鐘在干什么。你可以在一個(gè)程序里實(shí)時(shí)計(jì)算出所有將來的牌。

(關(guān)于這個(gè)理解，可以查看edu.princeton.cs.algs4.StdRandom ：

    private static Random random;    // pseudo-random number generator
    private static long seed;        // pseudo-random number generator seed

    // static initializer
    static {
        // this is how the seed was set in Java 1.4
        seed = System.currentTimeMillis();
        random = new Random(seed);
    }

    public static void setSeed(long s) {
        seed   = s;
        random = new Random(seed);
    }

現(xiàn)在的 jdk 已經(jīng)不再使用這種方式去定義seed了，正如之前所說的，這會(huì)是個(gè)bug

)

如果你在做一個(gè)在線撲克應(yīng)用的話 這是一件非常糟糕的事情，因?yàn)槟憧隙ㄏＭ愕某绦蛳磁葡吹孟駨V告里說的那么好。有許多關(guān)于隨機(jī)數(shù)的評(píng)論，其中很有名的一句是 "The generation of random numbers is too important to be left to chance -- Robert R. Coveyou" 隨機(jī)數(shù)的生成太過重要。

人們嘗試了各種洗牌方法來保證其隨機(jī)性, 包括使用硬件隨機(jī)數(shù)生成器，或者用很多測(cè)試來確認(rèn)它們的確實(shí)是隨機(jī)的。所以如果你的業(yè)務(wù)依賴于洗牌, 你最好使用好的隨機(jī)洗牌代碼，洗牌并沒有我想象的那么簡單，一不小心就會(huì)出現(xiàn)很多問題。這是我們的第一個(gè)排序應(yīng)用。

程序員經(jīng)常需要將數(shù)據(jù)進(jìn)行排序,而且很多時(shí)候需要定義不同的排序順序，比如按藝術(shù)家的姓名排序音樂庫，按歌名排序等。

在Java中，我們可以對(duì)任何類型實(shí)現(xiàn)我們想要的任何排序算法。Java 提供了兩種接口：

Comparable (java.lang.Comparable)

Comparator (java.util.Comparator)

使用 Comparable 接口和 compareTo() 方法，我們可以使用字母順序，字符串長度，反向字母順序或數(shù)字進(jìn)行排序。 Comparator 接口允許我們以更靈活的方式執(zhí)行相同操作。

無論我們想做什么，我們只需要知道如何為給定的接口和類型實(shí)現(xiàn)正確的排序邏輯。

在文章的最開始我們就談?wù)撨^，Java 標(biāo)準(zhǔn)庫中會(huì)用到排序的類型通過實(shí)現(xiàn) Comparable 接口，也就是這些數(shù)據(jù)類型實(shí)現(xiàn) compareTo() 方法的實(shí)例方法，來實(shí)現(xiàn)排序功能。實(shí)現(xiàn)此接口的對(duì)象列表（和數(shù)組）可以通過 Collections.sort（和 Arrays.sort）進(jìn)行自動(dòng)排序。

Comparable 接口對(duì)實(shí)現(xiàn)它的每個(gè)類的對(duì)象進(jìn)自然排序，compareTo() 方法被稱為它的自然比較方法。所謂自然排序(natural order)就是實(shí)現(xiàn)Comparable 接口設(shè)定的排序方式。排序時(shí)若不指定 Comparator (專用的比較器), 那么就以自然排序的方式來排序。

考慮一個(gè)具有一些成員變量，如歌曲名，音樂家名，發(fā)行年份的 Musique (法語哈哈哈，同 Music) 類。 假設(shè)我們希望根據(jù)發(fā)行年份對(duì)歌曲列表進(jìn)行排序。 我們可以讓 Musique 類實(shí)現(xiàn)Comparable 接口，并覆蓋 Comparable 接口的 compareTo() 方法。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @program: algo
 * @description: Exemple to implement Comparable interface for a natural order
 * @author: Xiao~
 * @create: 2019-03-28 14:35
 **/

public class Musique implements Comparable {

    private final String song;
    private final String artist;
    private final int year;


    public Musique(String song, String artist, int year) {
        this.song = song;
        this.artist = artist;
        this.year = year;
    }

    /**
     *
     * @param musique
     * @return natural order by year
     * -1 : <
     * +1 : >
     * 0 : ==
     */
    @Override
    public int compareTo(Musique musique) {

        return this.year - musique.year;
    }

    @Override
    public String toString() {
        return "Musique{" +
                "song="" + song + """ +
                ", artist="" + artist + """ +
                ", year=" + year +
                "}";
    }

    // simple client
    public static void main(String[] args){
        List list = new ArrayList<>();
        // 暴露歌單系列
        list.add(new Musique("You"re On My Mind","Tom Misch",2018));
        list.add(new Musique("Pumped Up Kicks","Foster The People",2011));
        list.add(new Musique("Youth","Troye Sivan",2015));
        // 通過 Collections.sort 進(jìn)行自動(dòng)排序
        Collections.sort(list);

        list.forEach(System.out::println);
    }
}

運(yùn)行結(jié)果

現(xiàn)在，假設(shè)我們想要按照歌手和歌名來排序我們的音樂清單。 當(dāng)我們使一個(gè)集合元素具有可比性時(shí)（通過讓它實(shí)現(xiàn)Comparable接口），我們只有一次機(jī)會(huì)來實(shí)現(xiàn)compareTo()方法。解決方案是使用 Comparator 接口

Comparator 接口對(duì)實(shí)現(xiàn)它的每個(gè)類的對(duì)象進(jìn)輪流排序 (alternate order)

實(shí)現(xiàn) Comparator 接口意味著實(shí)現(xiàn) compare() 方法

jdk 8:

public interface Comparator {
  
    int compare(T o1, T o2);
    ...
}

特性要求：必須是全序關(guān)系
寫圖中如果前字母相同就會(huì)比較后一個(gè)字母，以此類推進(jìn)行排序

與 Comparable 接口不同，Comparable 接口將比較操作(代碼)嵌入需要進(jìn)行比較的類的自身中，而 Comparator 接口則在我們正在比較的元素類型之外進(jìn)行比較，即在獨(dú)立的類中實(shí)現(xiàn)比較。
我們創(chuàng)建多個(gè)多帶帶的類（實(shí)現(xiàn) Comparator）以便由不同的成員進(jìn)行比較。
Collections 類有兩個(gè) sort() 方法，其中一個(gè) sort() 使用了Comparator，調(diào)用 compare() 來排序?qū)ο蟆?/p>

如果要使用 Java 系統(tǒng)定義的 Comparator 比較器，則：

創(chuàng)建 Comparator 對(duì)象。

將第二個(gè)參數(shù)傳遞給Arrays.sort() 或者 Collections.sort()

String[] a;
...
// 這般如此使用的是自然排序
Arrays.sort(a);
...
/**
* 以下這般這般這般都是使用Comparator object定義的輪流排序
**/
Arrays.sort(a, String.CASE_INSENSITIVE_ORDER);
...
Arrays.sort(a, Collator.getInstance(new Locale("es")));
...
Arrays.sort(a, new BritishPhoneBookOrder());
...

在我們自定義的排序?qū)崿F(xiàn)中支持 Comparator 比較器：

將 Comparator 傳遞給 sort() 和less()，并在less() 中使用它。

使用 Object 而不是 Comparable

請(qǐng)參考：這個(gè)Insertion 和 這個(gè)InsertionPedantic

import java.util.Comparator;

public class InsertionPedantic {

    // 使用的是 Comparable 接口和自然排序
    public static > void sort(Key[] 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);
    }

    // 使用的是 Comparator 接口實(shí)現(xiàn)的是客戶自定義的排序
    public static  void sort(Key[] a, Comparator comparator) {
        int n = a.length;
        for (int i = 1; i < n; i++)
            for (int j = i; j > 0 && less(comparator, a[j], a[j-1]); j--)
                exch(a, j, j-1);
    }
    
        // is v < w ?
    private static > boolean less(Key v, Key w) {
        return v.compareTo(w) < 0;
    }

    // is v < w?
    private static  boolean less(Comparator comparator, Key v, Key w) {
        return comparator.compare(v, w) < 0;
    }
    ...
}

實(shí)現(xiàn) Comparator ：

定義一個(gè)(嵌套)類實(shí)現(xiàn) Comparator 接口

實(shí)現(xiàn) compare() 方法

為 Comparator 提供客戶端訪問權(quán)限

下邊為我們的音樂列表實(shí)現(xiàn)按歌名排序的比較器：
這里我改了一下，把按歌名排序作為自然排序，然后為按歌手和發(fā)行年份都創(chuàng)建了兩個(gè)多帶帶的，嵌入的，實(shí)現(xiàn) Comparator 接口的類
并且提供客戶端訪問這些內(nèi)部類

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @program: algo
 * @description: Exemple to implement Comparable interface for a natural order
 * @author: Xiao~
 * @create: 2019-03-28 14:35
 **/

public class Musique implements Comparable {

    public static final Comparator ARTIST_ORDER = new ArtistOrder();
    public static final Comparator YEAR_ORDER = new YearOrder();

    private final String song;
    private final String artist;
    private final int year;


    public Musique(String song, String artist, int year) {
        this.song = song;
        this.artist = artist;
        this.year = year;
    }

    /**
     * @param musique
     * @return natural order: order by song name
     */
    @Override
    public int compareTo(Musique musique) {

        return this.song.compareTo(musique.song);
    }

    // comparator to music by artist name
    private static class ArtistOrder implements Comparator {

        @Override
        public int compare(Musique o1, Musique o2) {
            // Sting class has implemented Comparable interface, we use his native compareTo()
            return o1.artist.compareTo(o2.artist);
        }
    }

    // comparator to music by year published
    private static class YearOrder implements Comparator {

        @Override
        public int compare(Musique o1, Musique o2) {
            // this trick works here (since no danger of overflow)
            return o1.year - o2.year;
        }
    }

    /**
     * Returns a comparator for comparing music in lexicographic order by artist name.
     *
     * @return a {@link Comparator} for comparing music in lexicographic order by artist name
     */
    public static Comparator byArtistName() {
        return new ArtistOrder();
    }

    /**
     * Returns a comparator for comparing music order by year published.
     *
     * @return a {@link Comparator} for comparing music by year published.
     */
    public static Comparator byYear() {
        return new YearOrder();
    }


    @Override
    public String toString() {
        return "Musique{" +
                "song="" + song + """ +
                ", artist="" + artist + """ +
                ", year=" + year +
                "}";
    }

    // simple client
    public static void main(String[] args) {
        List list = new ArrayList<>();

        list.add(new Musique("You"re On My Mind", "Tom Misch", 2018));
        list.add(new Musique("Pumped Up Kicks", "Foster The People", 2011));
        list.add(new Musique("Youth", "Troye Sivan", 2015));
        list.add(new Musique("Royals", "Lorde", 2013));
        list.add(new Musique("Atlas", "Coldplay", 2013));
        list.add(new Musique("Sugar Roses", "Elsa Kopf", 2013));

        Collections.sort(list);
        System.out.println("
Order by Song name (natural order):");
        list.forEach(System.out::println);

        System.out.println("
Order by artist name:");
        Collections.sort(list,Musique.byArtistName());
        list.forEach(System.out::println);

        System.out.println("
Order by year published:");
        Collections.sort(list,Musique.byYear());
        list.forEach(System.out::println);
    }
}

典型的應(yīng)用：
首先，簡化下我們的測(cè)試客戶端：先進(jìn)行歌手排序; 然后按年份排序。

    public static void main(String[] args) {
        List list = new ArrayList<>();

        list.add(new Musique("You"re On My Mind", "Tom Misch", 2018));
        list.add(new Musique("Pumped Up Kicks", "Foster The People", 2011));
        list.add(new Musique("Youth", "Troye Sivan", 2015));
        list.add(new Musique("Royals", "Lorde", 2013));
        list.add(new Musique("Atlas", "Coldplay", 2013));
        list.add(new Musique("Sugar Roses", "Elsa Kopf", 2013));

        System.out.println("
Order by artist name:");
        Collections.sort(list,Musique.byArtistName());
        list.forEach(System.out::println);

        System.out.println("
Order by year published:");
        Collections.sort(list,Musique.byYear());
        list.forEach(System.out::println);
    }

運(yùn)行結(jié)果：

進(jìn)行年排序的時(shí)候歌手名排序任然保留，排序是穩(wěn)定的。

一個(gè)穩(wěn)定的排序保留具有相同鍵值的項(xiàng)的相對(duì)順序。也就是說，一旦你按歌手名排列了之后，接著你想按第二項(xiàng)排列，上邊是按照年份，并且對(duì)于所有在第二項(xiàng)具有相同鍵關(guān)鍵字的記錄保持按歌手名排列。實(shí)際上，不是所有的排列都保留那個(gè)性質(zhì)，這就是所謂的穩(wěn)定性。

Q. 那插入排序和選擇排序，他們都是穩(wěn)定的排序嗎？
A. 插入排序是穩(wěn)定的，相同的元素在比較的過程不會(huì)再互相互換位置，但是選擇排序是會(huì)的，所以選擇排序并不穩(wěn)定

下邊是使用選擇排序的運(yùn)行結(jié)果：
首先按名字排序，然后再按 section(第二列) 排序

如圖可以看到進(jìn)行section排序的時(shí)候，上一次的按名字排序的順序不再保留，選擇排序并不穩(wěn)定，shellsort 也不穩(wěn)定。

這里有另一個(gè)典型的例子，人們想買一場(chǎng)搖滾演唱會(huì)的門票，我們有一個(gè)按照時(shí)間排列的序列，然后將這個(gè)序列再按地點(diǎn)排列，我們所希望的是這些按地點(diǎn)排列的序列同時(shí)能保持時(shí)間順序 ，如圖是一個(gè)不穩(wěn)定的排序，按地點(diǎn)排序完了之后它不會(huì)保持按時(shí)間的排序，如果他們想用其中一個(gè)記錄，他們還得重新排列。但如果他們用的是穩(wěn)定的排序，這些記錄還保持著按時(shí)間的排序，所以對(duì)很多的應(yīng)用都希望排序算法有穩(wěn)定性。

值得注意的是，我們?cè)诓榭创a去判斷排序算法是否是穩(wěn)定的時(shí)候要仔細(xì)看下比較邏輯使用的是 "<" 還是 "<=".
這些操作是否穩(wěn)定取決于我們的代碼怎么寫。在我們的代碼中，如果幾個(gè)個(gè)鍵是相等的,比如我們有如下序列：

B1 A1 A2 A3 B2 , 其中 A1 = A2 =A3; B1 = B2

我們要保證排序的時(shí)候結(jié)果是：A1 A2 A3 B1 B2 , 而不會(huì)出現(xiàn)：A3 A1 A3 B1 B2 或者其他情況。
在插入排序中，當(dāng)我們得到 A1，然后排完順序后，在這種情況下，它數(shù)組中就是在起始位置，而當(dāng)我們得到第二個(gè) A，也就是 A2，只要找到不小于 A2 的記錄就停止排列，A1，A2 這倆是相等的，是不小于的，我們就停止排序。所以排序從不越過相同值的記錄。如果這里是小于等于，那么它是不穩(wěn)定的，或者如果我們用另一種方法并據(jù)此運(yùn)行，在代碼中讓相同值的記錄從不越過彼此，那么排序就是穩(wěn)定的。

具體可以查看插入排序和選擇排序的源碼。

至今為止我們看到的排序中插入排序是穩(wěn)定的，后邊的歸并排序也是穩(wěn)定的。

現(xiàn)在我們將通過一個(gè)有趣的計(jì)算幾何領(lǐng)域的例子來了解排序的應(yīng)用

假設(shè)現(xiàn)在平面上有一個(gè) n 個(gè)點(diǎn)構(gòu)