摘要：我們討論比較排序算法的理論基礎，并結合本章應用排序和優先級隊列算法。基本排序引入了選擇排序，插入排序和。描述了，一種保證在線性時間內運行的排序算法。當我們后續實現排序算法時，我們實際上將這個機制隱藏在我們的實現下面。

上一篇：棧和隊列
下一篇：歸并排序

排序是重新排列一系列對象以便按照某種邏輯順序排列的過程。排序在商業數據處理和現代科學計算中起著重要作用。在交易處理，組合優化，天體物理學，分子動力學，語言學，基因組學，天氣預報和許多其他領域中的應用比比皆是。
在本章中，我們考慮了幾種經典的排序方法和一種稱為優先級隊列的基本數據類型的有效實現。我們討論比較排序算法的理論基礎，并結合本章應用排序和優先級隊列算法。

2.1 基本排序引入了選擇排序，插入排序和 shellort。
2.2 Mergesort 描述了megesort，一種保證在線性時間內運行的排序算法。
2.3 Quicksort 描述了quicksort，它比任何其他排序算法使用得更廣泛。
2.4 優先級隊列引入優先級隊列數據類型和使用二進制堆的有效實現。它還引入了 heapsort。
2.5 應用程序描述了排序的應用程序，包括使用備用排序，選擇，系統排序和穩定性

進行排列我們應該遵循哪些規則呢？讓我們先看看典型基本排序問題。
比如，大學有很多學生檔案，對于每個學生有一些信息，可能是姓名、班級編號、成績、電話號碼、地址。

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

下圖將數組中的 n 個元素根據元素中的定義的關鍵字 (此為姓) 升序排列

排序的應用：
排序的應用很多，比如快遞的包裹，紙牌游戲，手機聯系人，圖書館的圖書編號等等。我們的目標是能夠對任何類型的數據進行排序。
來看幾個客戶端程序。

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]);
     }
}

這個例子中：

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

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

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

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

% 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();
         //調用插入排序方法
         Insertion.sort(a);
         for (int i = 0; i < n; i++)
         StdOut.println(a[i]);
     }
}

這個客戶端程序調用插入排序方法。它從標準輸入中讀取數字，放進數組，然后調用 Insertion.sort（插入排序），最后打印輸出。
下邊的打印輸出的數字是從小到大排好序的。這看起來有點像人為設計的輸入，也有很多應用中可以用隨機輸入作為好的輸入模型。

% 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

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

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

Insertion.sort() 使用這個數組作為第一實參。

同樣，程序對這些文件名進行了排序，然后依次將文件名以字母表的順序打印輸出

這是三個不同的客戶端，對應三種完全不同類型的數據。
任務的第一條規則：我們要考慮如何才能完成實現一個排序程序，可以被三個不同的客戶端用來對三種不同數據類型排序。
這里采取的方式是一種叫做回調的機制。

我們的基本問題是：在沒有元素關鍵字類型的任何信息的情況下如何比較所有這些數據。
答案是我們建立了一個叫做回調的機制

Callback = 對可執行代碼的引用

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

sort() 方法根據需要調用 object 的比較函數 compareTo()

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

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

Java中，有一種隱含的機制，只要任何這種對象數組具有 compareTo() 方法。排序函數就會在需要比較兩個元素時，回調數組中的對象對應的compareTo()方法。

對于Java，因為要在編譯時檢查類型，使用了叫做接口的特殊方法。
接口 interfaces：一種類型，里頭定義了類可以提供的一組方法

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

實現接口的類：必須實現所有接口方法

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

"簽署合同后的影響"：

可以將任何 String 對象視為 Comparable 類型的對象

在Comparable對象上，可以調用（僅調用）compareTo() 方法。

啟用回調。

后面我們會詳細介紹如何用Java接口實現回調。這個比較偏向編程語言的細節，但是確實值得學習，因為它使我們能夠以類型安全的方式使用為任何類型數據開發的排序算法。

注：key point: no dependence on type of data to be sorted 關鍵點：不依賴于要排序的數據類型

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

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

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

Comparable 接口規范要求實現 Comparable 的數據類型要有一個compareTo()方法。這個方法是泛化的，會對特定類型的元素進行比較
public interface Comparable{public int compareTo(Item that);}

當我們實現要排序的對象（這里為String ）時我們就實現 Comparable 接口
public class String implements Comparable

因為排序是在很多情形中要使用的操作，Java標準庫中會用到排序的類型很多都實現了Comparable接口，意味著，這些數據類型具有實現 compareTo()方法的實例方法。它將當前對象 (a[j]) 與參數表示的對象 (a[j-1]) 相比較，根據具體的一些測試返回比較的結果，比如
返回 -1 表示小于；返回 +1 表示大于；返回0表示相等，排序算法的實現就只需要這么一個compareTo()方法。
在函數聲明的時候，它要求參數必須是 Comparable 類型數組 (Comparable[] a)，這意味著數組中的對象需要實現 Comparable 接口，或者說對象必須有compareTo() 方法，然后排序代碼直接使用 compareTo() 對一個對象實例 (a[j]) 調用這個方法, 以另一個對象實例 (a[j-1]) 作為實參。
在這個例子中測試第一個是否小于第二個。關鍵在于排序實現與數據類型無關，具體的比較由 Comparable 接口處理，不同類型的 Comparable 數組最終會以相同的方式排序，依賴于接口機制，回調到實際的被排序對象類型 (String) 的 compareTo() 代碼。

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

全序關系是一種二元關系 ≤ 滿足：

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

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

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

有幾條很自然的規則，有三個性質：

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

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

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

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

如果是小于，返回負整數

如果相等返回0

如果當前對象大于作為參數傳入的對象則返回正整數。

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

Java 內置的可比類型：Java中很多數字、日期和文件等等標準類型按照規定都實現了 compareTo() 方法
自定義可比類型：如果我們自己實現的類型要用于比較，就要根據這些規則，自己去實現 Comparable 接口

實現一般是直截了當的。這里有個例子，這是Java中實現的 Date 日期數據類型的簡化版，我們用來演示實現Comparable接口

//在類聲明之后，我們寫implements Comparable 然后在泛型類型填上類名，因為我們后面只允許日期類型與其他日期類型比較
public class Date implements Comparable
{
     //Date類有三個實例變量: month,day,year
     private final int month, day, year;
     //構造函數通過參數設置這些變量
     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;
     }
}

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

Java語言為我們提供了Comparable接口的機制，使我們能夠對任何類型數據排序。當我們后續實現排序算法時，我們實際上將這個機制隱藏在我們的實現下面。

我們采用的方式是將引用數據的兩個基本操作：比較和交換，封裝為靜態方法

Less. Is item v < w ?

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

方法 less() 以兩個 Comparable 對象作為參數，返回 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;
}

當我們對數組中的元素進行排序時另一個操作是 swap，將給定索引 i 的對象與索引 j 的對象交換.
這個操作是每個程序員學習賦值語句的入門語句，將 a[i] 保存在變量 swap 中，a[j] 放進 a[i]，然后 swap 放回到 a[j]

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

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

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

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

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

選擇排序的完整動態演示點此

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

箭頭左邊的項不會再變了，它們已經是升序了

箭頭右邊的項都比箭頭左邊的項大，這是我們確立的機制

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

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

向右移動指針 i 加 1

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

交換最小索引與當前指針的值

向右移動指針 i 加1后，不變式有可能被破壞，因為有可能在指針右邊有一個元素比指針所指的元素小導致不變式被破壞，我們要做的是找到最小項的索引，然后交換，一旦我們完成了交換，我們又一次保留了不變式。這時指針左邊元素不會再變了，右邊也沒有更小的元素，這也就給出了實現選擇排序的代碼。

實現不變性的代碼如下：

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++) {
        //在指針右邊找到最小項
            int min = i;
            for (int j = i + 1; j < n; j++)
                if (less(a[j], a[min]))
                    min = j;
            //交換最小索引與當前指針的值
            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]);
        }
    }
    
    //寫一個超簡單的客戶端
    public static void main(String[] args) {
        String[] a = {"1","5","3","8","4","1","4","5"};
        Selection.sort(a);
        show(a);
    }
}

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

值得注意的是當我們嘗試編譯的時候會出現如下警告：

發生的原因：

實質上，此警告表示 Comparable 對象無法與任意對象進行比較。 Comparable 是一個泛型接口，其中類型參數 T 指定可以與此對象進行比較的對象的類型。

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

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

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

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

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

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

黑色的項是每次為了尋找最小項檢查的項

最小項是紅色的

灰色的項是未檢查的項，已經在最終位置了

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

關于選擇排序的這個命題說明了很有意思的一點，就是它和輸入的序列本身的順序無關。

選擇排序需要平方時間因為它總要查看所有的項尋找最小項

另一個性質就是要完成排序這已經是移動開銷最小的了，選擇排序只需要線性次數的交換
每一項都是僅僅一次交換就放在了最終位置。

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

Q. 如果數組已經排好序，那么插入排序比較需要多少次？

對數級

線性級

平方級

立方級別

A. 查看附錄

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

下邊是一個插入排序的演示。對于插入排序，我們要做的和之前一樣，從左到右移動索引 i，但現在，在第 i 個迭代中 我們將會把 a[ i ] 移動到其左側的位置，讓我們用牌的示例來看看這是怎么工作的。
現在我們從初始化 i 為第一張牌開始，我們的想法是 i 的左邊的所有紙牌將會被排序，右邊的紙牌，我們全部先都不去看
所以，i 左側所有的紙牌是升序，右側所有的紙牌我們現在還沒檢查過，第二步我們增加 i ，在這種情況下指針左邊已經排好序了，我們什么也不用做。
當 i 是數組中的第三項時，此時我們從索引 j 開始，然后，j 從 i 開始向左邊移動，我們要做的是將5與它左邊更大的元素交換，那么，首先與10交換，依然沒有到最終位置，所以再和7交換，現在已經到數組最前面了，一旦我們檢查完左側所有項或者找到一個更小的元素，i 左邊所有項就排好序了

插入排序完整演示在此

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

我們再從不變式的角度來看插入排序

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

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

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

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

將指針向右側移動，增加 1，因為指針指向的元素沒排過序，所以破壞了不變式，那么為了維持不變式， 要將它排序，需要將它和左邊每個更大的元素交換。下面的代碼完成的就是這個, 索引 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);
    }
}

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

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

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

因為 1/4 n^2 和 1/2 n^2 相比小一半, 插入排序的速度大約是選擇排序的兩倍, 所以相同時間內演示中我們能夠對大約兩倍的元素進行排序

插入排序運行時間取決于數據開始的順序。
我們來看看最好與最壞的情況，當然這些都是異常的情況：

Best case：
如果數組恰好已經排好序了，插入排序實際上只需要驗證每個元素比它左邊的元素大，所以不用進行交換，只需要 n-1 次比較就能完成排序工作。

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

所以第一種情況下，插入排序比選擇排序快得多, 是線性時間的而不是平方時間的, 而第二種情形中，比選擇排序慢，因為需要一樣的比較次數，但是多得多的交換次數。元素降序排列的情況，每次得到一個新元素，都必須一直交換到最開頭。這是實際應用中我們不想見到的最壞的情況。

但也有好的情況，在很多實際應用中我們都在利用這一點，就是數組已經部分有序的情況，用定量的方法考慮問題。

我們定義：一個“逆序對”(inversion)是數組中亂序的關鍵值對

例如：
A E E L M O T R X P S
其中有6個逆序對：T-R T-P T-S R-P X-P X-S

T和R是亂序的，因為R應該在T的前面 T和P是亂序的，等等

我們定義：如果一個數組的逆序對數量是線性的(或者說逆序對的數量 ≤ cn， 其中 c 代表一個常數），那么這個數組是部分有序的。

部分有序的數組在實際應用中經常遇到，例如有一個大數組是有序的，只有最后加上的幾個元素是無序的，那么這個數組就是部分有序的；
或者另外的情況，只有幾個項不在最終位置，這個數組也是部分有序的。
實際應用中經常出現這樣的情況，插入排序有意思的地方在于對于部分有序的數組。

我們定義：插入排序在部分有序數組上的運行時間是線性的
證明：

就是交換的次數與逆序對的個數相等 (沒交換一次，逆序對就減少一個)

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

Binary insertion sort
使用二分查找來找出插入點

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

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

但是訪問數組的次數依舊是平方級的

這就是插入排序 我們學習的第二個基本排序方法。

Q. 如果數組已經是升序排好的，那么插入排序將進行多少次比較？

常數次

對數次

線性次

平方級次

A. 見附錄

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

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

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

又一例子：

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

Q. 那么首先我們怎樣對序列進行 h-排序呢？
A. 實際上很簡單, 直接用插入排序，但是之前是每次獲取新的項往回走一個，現在往回走 h 個，所以代碼和插入排序是一樣的，只不過順著數組往回查看的時候之前每次只退1個，現在跳 h 個。這就是對數組進行h-排序的方法。

這里我們使用插入排序的原因基于我們對插入排序原理的理解有兩點：

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

另一點是如果增量小，因為我們之前已經用更大的h值進行了 h-排序，數組是部分有序的，插入排序就會很快

用選擇排序作為 h-排序 的基礎就不行，因為無論序列是什么順序，它總需要平方時間，數組是否有序對選擇排序沒有任何影響。

我們看一個希爾排序的例子，增量是7、3、1
下圖每一行的標注了紅色的項就是本次迭代中發生過移動的項

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

然后進行3-排序。因為已經進行過7-排序，進行 3-排序 的元素要么已經在最終位置，要么只需要移動幾步。這個例子中，只有 A 移動了兩步。

然后進行 1-排序，因為數組已經經過 7-排序 和 3-排序，需要進行 1-排序 時，數組已經基本有序了，大多數的項只移動一兩個位置。

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

對希爾排序更直觀的理解可以通過數學證明。如果序列經過 h-排序的，用另一個值 g 進行 g-排序，序列仍然是 h-有序的。
一個 h-有序的 數組是 h 交錯排序后的子序列。

我們的命題：h-有序的 數組經過 g-排序 后依然是 h-有序的

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

另一個問題就是對于希爾排序我們應當使用哪種步長序列.

首先能想到的想法可能是試試2的冪, 1, 2, 4, 8, 16, 32, ...實際上這個行不通，因為它在進行1-排序之前不會將偶數位置的元素和奇數位置的元素進行比較，這意味著性能就會很差。

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

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

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

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

這是用Java實現的希爾排序，使用 Knuth 的 3x+1 增量序列

import edu.princeton.cs.algs4.StdOut;

public class Shell {

    /**
     * 對數組進行升序排序
     * @param 需要排序的數組
     */
    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 請查看附錄

        while (h >= 1) {
            // 對數組進行 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);
            // 計算下一輪排序使用的增量值
            h /= 3;
        }
        /**
         * assert [boolean 表達式]
         * 如果[boolean表達式]為true，則程序繼續執行。
         * 如果為false，則程序拋出AssertionError，并終止執行。
         * assert [boolean 表達式]："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;
    }


    // 檢查數組是否已排好序
    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;
    }

    // 檢查數組是否是 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;
    }

    // 打印數組到標準輸出
    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);
    }
}

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

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

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

N:原始輸入數據的大小；compares：對應的輸入需要通過多次比較得到完全有序數組；
N^1.289: 對應輸入大小的1.289次冪；2.5 N lg N：對應輸入的對數計算值

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

那我們為什么還對這個算法感興趣呢？因為這個算法的思想很簡單，而且能獲得巨大的性能提升。它相當快，所以在實際中非常有用除了巨大的數組會變得慢，對于中等大小的數組，它甚至可以勝過經典的復雜方法。代碼量也不大，通常應用于嵌入式系統，或者硬件排序類的系統，因為實現它只需要很少的代碼。

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

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

我們有一種利用排序來進行洗牌的方法，雖然排序似乎正好與洗牌相反。
這種方法的構想是為一個數組元素產生一個隨機實數，然后利用這些隨機數作為排序依據。

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

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

洗牌動態演示鏈接

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

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

遞增 i 的值，然后生成一個隨機整數 r，再交換

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

在每次迭代中，隨機均勻地選擇 0 和 i 之間的整數 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);
    }
}

分別進行三次洗牌：

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

Bugs：

隨機數 r 永遠不會等于 52 ? 這意味著最后一張牌會始終在最后一位出現

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

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

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

(關于這個理解，可以查看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);
    }

現在的 jdk 已經不再使用這種方式去定義seed了，正如之前所說的，這會是個bug

)

如果你在做一個在線撲克應用的話 這是一件非常糟糕的事情，因為你肯定希望你的程序洗牌洗得像廣告里說的那么好。有許多關于隨機數的評論，其中很有名的一句是 "The generation of random numbers is too important to be left to chance -- Robert R. Coveyou" 隨機數的生成太過重要。

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

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

在Java中，我們可以對任何類型實現我們想要的任何排序算法。Java 提供了兩種接口：

Comparable (java.lang.Comparable)

Comparator (java.util.Comparator)

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

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

在文章的最開始我們就談論過，Java 標準庫中會用到排序的類型通過實現 Comparable 接口，也就是這些數據類型實現 compareTo() 方法的實例方法，來實現排序功能。實現此接口的對象列表（和數組）可以通過 Collections.sort（和 Arrays.sort）進行自動排序。

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

考慮一個具有一些成員變量，如歌曲名，音樂家名，發行年份的 Musique (法語哈哈哈，同 Music) 類。 假設我們希望根據發行年份對歌曲列表進行排序。 我們可以讓 Musique 類實現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 進行自動排序
        Collections.sort(list);

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

運行結果

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

Comparator 接口對實現它的每個類的對象進輪流排序 (alternate order)

實現 Comparator 接口意味著實現 compare() 方法

jdk 8:

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

特性要求：必須是全序關系
寫圖中如果前字母相同就會比較后一個字母，以此類推進行排序

與 Comparable 接口不同，Comparable 接口將比較操作(代碼)嵌入需要進行比較的類的自身中，而 Comparator 接口則在我們正在比較的元素類型之外進行比較，即在獨立的類中實現比較。
我們創建多個多帶帶的類（實現 Comparator）以便由不同的成員進行比較。
Collections 類有兩個 sort() 方法，其中一個 sort() 使用了Comparator，調用 compare() 來排序對象。

如果要使用 Java 系統定義的 Comparator 比較器，則：

創建 Comparator 對象。

將第二個參數傳遞給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());
...

在我們自定義的排序實現中支持 Comparator 比較器：

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

使用 Object 而不是 Comparable

請參考：這個Insertion 和 這個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 接口實現的是客戶自定義的排序
    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;
    }
    ...
}

實現 Comparator ：

定義一個(嵌套)類實現 Comparator 接口

實現 compare() 方法

為 Comparator 提供客戶端訪問權限

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

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);
    }
}

典型的應用：
首先，簡化下我們的測試客戶端：先進行歌手排序; 然后按年份排序。

    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);
    }

運行結果：

進行年排序的時候歌手名排序任然保留，排序是穩定的。

一個穩定的排序保留具有相同鍵值的項的相對順序。也就是說，一旦你按歌手名排列了之后，接著你想按第二項排列，上邊是按照年份，并且對于所有在第二項具有相同鍵關鍵字的記錄保持按歌手名排列。實際上，不是所有的排列都保留那個性質，這就是所謂的穩定性。

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

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

如圖可以看到進行section排序的時候，上一次的按名字排序的順序不再保留，選擇排序并不穩定，shellsort 也不穩定。

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

值得注意的是，我們在查看代碼去判斷排序算法是否是穩定的時候要仔細看下比較邏輯使用的是 "<" 還是 "<=".
這些操作是否穩定取決于我們的代碼怎么寫。在我們的代碼中，如果幾個個鍵是相等的,比如我們有如下序列：

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

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

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

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

現在我們將通過一個有趣的計算幾何領域的例子來了解排序的應用

假設現在平面上有一個 n 個點構