二、排序

排序算法類的模板

• 大多數(shù)情況下，我們所實(shí)現(xiàn)的排序算法只會(huì)通過(guò)兩個(gè)方法操作數(shù)據(jù)：less()方法對(duì)元素進(jìn)行比較，exch()方法將元素交換位置。exch()方法的實(shí)現(xiàn)很簡(jiǎn)單，通過(guò)Comparable接口實(shí)現(xiàn)less()方法也不困難。sort()方法非常重要，它決定著算法執(zhí)行所需要的時(shí)間，不同的算法對(duì)sort()有不同的實(shí)現(xiàn)，sort()方法將是我們本節(jié)討論的重點(diǎn)。
• 注意:相信Comparable接口對(duì)大部分學(xué)習(xí)Java的讀者并不陌生。如果你從沒(méi)有學(xué)習(xí)過(guò)Java，那么在學(xué)習(xí)這一章之前，你應(yīng)該對(duì)Comparable接口有一定的學(xué)習(xí)與了解并且能使用Comparable接口構(gòu)建類。在排序算法類的模板代碼后面我會(huì)列出一個(gè)Comparable接口的使用示例。

示例代碼:

public class Example {
    public static void sort(Comparable[] a) 
    { /*具體算法具體實(shí)現(xiàn)*/ }
    public static boolean less(Comparable v, Comparable w) 
    { return v.compareTo(w) < 0; }
    public 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) 
    { //在單行中打印數(shù)組
        for(int i=0; i<a.length; i++) 
            System.out.println(a[i] + " ");
        System.out.println();
    }
    public static boolean isSorted(Comparable[] a)
    { //測(cè)試數(shù)組元素是否有序
        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) 
    { //從標(biāo)準(zhǔn)輸入讀取字符串，將他們排序并輸出
        String[] a = {"b","a","hello","world","you"};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

Comparable接口使用示例：

** Comparable: **
// 實(shí)現(xiàn)Comparable接口要覆蓋compareTo方法, 在compareTo方法里面實(shí)現(xiàn)比較：
public class Person implements Comparable {
     private int age;
     public int compareTo(Person that) {
          if(this.age > that.age) return +1;
          if(this.age < that.age) return -1;
          return 0;                     // 返回age的比較結(jié)果.
     }
}
// 這時(shí)我們可以直接用 Collections.sort( personList ) 對(duì)其排序了.

• 我們由示例可以知道實(shí)現(xiàn)Comparable接口必須要覆蓋compareTo方法，對(duì)對(duì)象進(jìn)行排序的工作也基本是調(diào)用compareTo方法來(lái)完成的。我們接下來(lái)用v>w來(lái)表示v.compareTo(w)>0這樣的代碼。一般來(lái)說(shuō)，如果Vv無(wú)法比較或者兩者其中一個(gè)是null，v.compareTo(w)將會(huì)拋出一個(gè)異常。此外，compareTo()必須實(shí)現(xiàn)一個(gè)全序關(guān)系，即: 自反性、反對(duì)稱性、傳遞性。

1.選擇排序

• 選擇排序的原理非常簡(jiǎn)單: 首先找到數(shù)組中那個(gè)最小的元素，其次，將它和數(shù)組第一個(gè)元素交換位置（如果第一個(gè)元素就是最小的元素那么它就和自己交換）。再次，在剩下的元素中找出最小的元素，與數(shù)組第二個(gè)元素交換位置，以此類推，知道將整個(gè)數(shù)組排序。

示例代碼:

public class Selection {
    public static void sort(Comparable[] a) {
        //將a[]按升序排序
        int N = a.length;
        for(int i=0; i<N; i++) {
            //將a[i]和a[i+1]中最小的元素進(jìn)行交換
            int min = i;
            for(int j=i+1; j<N; j++)
                if(less(a[j], a[min])) min = j;
            exch(a, i ,min);
        }
    }
    //less()、exch()、isSorted() 和 main()方法見(jiàn)“排序算法模板”
}

例圖（初始序列：E A S Y Q U E S T I O N）:

官網(wǎng)例圖

• 選擇排序算法將是我們要了解的幾個(gè)排序算法中效率最低的一個(gè)，因?yàn)樗枰牡臅r(shí)間復(fù)雜度總是平方級(jí)別的。
• 選擇排序有兩個(gè)特點(diǎn)：
  1.運(yùn)行時(shí)間與輸入無(wú)關(guān)：因?yàn)闊o(wú)論你輸入的序列是否有序，選擇排序算法都會(huì)使用相同的遍歷路徑，所用的排序時(shí)間也是相同的。
  2.數(shù)據(jù)移動(dòng)是最少的：每次交換都只會(huì)改變兩個(gè)元素的值，不涉及元素移動(dòng)。因此選擇排序用了N次交換——交換次數(shù)和數(shù)組的大小是線性關(guān)系。我們將學(xué)習(xí)的其他算法都不具備這個(gè)特征（大部分的增長(zhǎng)數(shù)量級(jí)都是線性對(duì)數(shù)或平方級(jí)別）

2.插入排序

• 將元素插入到已經(jīng)有序的元素中的適當(dāng)位置。在計(jì)算機(jī)實(shí)現(xiàn)中，為了給要插入的數(shù)據(jù)騰出空間，我們需要將其余所有元素在插入之前都向后移動(dòng)一位，這種算法叫做插入排序

代碼示例:

/* 實(shí)現(xiàn)方法一 */
public class Insertion {    
    public static void sort(Comparable[] a) {
        //將a[]升序排列
        int N = a.length;
        for(int i=1; i<N; i++) {
            //將a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中
            for(int j=i; j>0 && less(a[j],a[j-1]); j--) {
                exch(a, j, j-1);
            }
        }
    }
    //less()、exch()、isSorted() 和 main()方法見(jiàn)“排序算法模板”
}


/* 實(shí)現(xiàn)方法二 */
//實(shí)現(xiàn)較大元素右移一位只需要訪問(wèn)一次數(shù)組
//相當(dāng)于把比它大的右移一位,然后空出來(lái)的那塊就等于它,就是不使用less
    public static void sort(Comparable [] a) {
        for (int i = 1; i < a.length; i++) {
            Comparable temp=a[i];
            int j;
            for (j = i; j>0 && Example.less(temp, a[j-1]) ; j--) 
                a[j]=a[j-1];
            a[j]=temp;
        }
    }

• 對(duì)于1到N-1之間的每一個(gè)i，將a[i]與a[0]到a[i-1]中比它小的所有元素依次有序地交換。在索引i由左向右變化的過(guò)程中，它左側(cè)的元素總是有序的，所以當(dāng)i到達(dá)數(shù)組的右端時(shí)排序就完成了。其中得到的數(shù)組都是部分有序數(shù)組。下面是幾種典型的部分有序的數(shù)組:
  1.數(shù)組中每個(gè)元素距離它的最終位置都不遠(yuǎn)；
  2.一個(gè)有序的大數(shù)組接一個(gè)小數(shù)組；
  3.數(shù)組中只有幾個(gè)元素的位置不正確；
• 插入排序?qū)@樣的數(shù)組很有效，選擇排序則不然。當(dāng)?shù)怪玫臄?shù)量很少時(shí)，插入排序很可能比本章中的其他任何算法都要快。

算法比較

• 可以通過(guò)SortCompare類來(lái)檢測(cè)（在下面給出）。他會(huì)使用由命令行參數(shù)指定的排序算法名稱所對(duì)應(yīng)的sort()方法進(jìn)行指定次數(shù)的實(shí)驗(yàn)（將指定數(shù)組的大小排序），并打印出所觀察到的各種算法的運(yùn)行時(shí)間比例。

import java.util.Random;

public class SortCompare {
    public static double time(String alg, Double[] 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("Help")) Help.sort(a);
        return timer.elapsedTime();
    }
    
    public static double timeRandomInput(String alg, int N, int T) {
        //使用算法alg將T個(gè)長(zhǎng)度為N的數(shù)組排序
        double total = 0.0;
        Double[] a = new Double[N];
        for(int t=0; t<T; t++) {
            //進(jìn)行一次測(cè)試（生成一個(gè)數(shù)組并排序）
            for(int i=0; i<N; i++) 
                a[i] = new Random().nextDouble();
            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);  //算法1的總時(shí)間
        double t2 = timeRandomInput(alg2, N, T);  //算法2的總時(shí)間
        System.out.printf("For %d random Doubles\n     %s is", N, alg1);
        System.out.printf(" %.1f times faster than %s\n", t2/t1, alg2);
    }
}

• 這個(gè)用例會(huì)運(yùn)行由前兩個(gè)命令行參數(shù)指定的排序算法，對(duì)長(zhǎng)度為N（由第三個(gè)參數(shù)指定）的Double型隨機(jī)數(shù)組進(jìn)行排序，重復(fù)T次（由第四個(gè)參數(shù)指定），然后輸出總運(yùn)行時(shí)間的比例。

3.希爾排序

• 希爾排序?yàn)榱思涌焖俣群?jiǎn)單地改進(jìn)了插入排序，交換不相鄰的元素以對(duì)數(shù)組的局部進(jìn)行排序，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。
• 希爾排序的思想是使數(shù)組中任意間隔為h的元素都是有序的。這樣的數(shù)組被稱為h有序數(shù)組。一個(gè)h有序數(shù)組相當(dāng)于h個(gè)互相獨(dú)立的有序數(shù)組交叉編制在一起組成的一個(gè)數(shù)組。
• 想了解更多？由于文本與精力有限，敬請(qǐng)讀者自行百度查找。

實(shí)現(xiàn):

• 實(shí)現(xiàn)希爾排序的一種方法是對(duì)于每個(gè)h，用插入排序?qū)個(gè)子數(shù)組獨(dú)立地排序。但因?yàn)樽訑?shù)組是相互獨(dú)立的，一個(gè)更簡(jiǎn)單的方法是在h個(gè)子數(shù)組中將每個(gè)元素交換到比它大的元素之前去（將比它大的元素向右移動(dòng)一格），這一步其實(shí)很像是插入排序。
• 只需要在插入排序的代碼中將移動(dòng)元素的距離由1改成h即可。這樣希爾排序的實(shí)現(xiàn)就轉(zhuǎn)化為了一個(gè)類似于插入排序但使用不同增量的過(guò)程。

示例代碼:

public class Shell {
    public static void sort(Comparable[] a) {
        //將a[]按升序排序
        int N = a.length;
        int h = 1;
        while(h < N/3) h = 3*h + 1;  //1,4,13,40,121,364,1093,...
        while(h >= 1) {
            //將數(shù)組變?yōu)閔有序
            for(int i=h; i<N; i++) {
                //將a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中
                for(int j=i; j>=h && less(a[j], a[j-h]); j-=h) {
                    exch(a, j, j-h);
                }
                h = h/3;
            }
        }
    }
    //less()、exch()、isSorted() 和 main()方法見(jiàn)“排序算法模板”
}

• 可以看到，我們?cè)诓迦肱判蛑屑尤胍粋€(gè)外循環(huán)來(lái)將h按照遞增序列遞減，我們就能得到這個(gè)簡(jiǎn)潔的希爾排序。

例圖（初始序列：S H E L L S O R T E X A M P L E）:

官網(wǎng)例圖

例題2.1.14

出列排序。說(shuō)說(shuō)你會(huì)如何將一副撲克牌排序，限制條件是只能查看最上面的兩張牌，交換最上面的兩張牌，或是將最上面的一張牌放到這摞牌的最底下。

代碼示例（僅供參考）：

/*
* Author: wss
* Time: 2019/5/29 17:42
* IDE: MyEclipse
*/

public class a2_1_14_Test {
    
    public static void main(String[] args) {
        /*
         * 第一步：執(zhí)行n-1次a[n-1]與a[n-2]的比較之后，數(shù)組中最大的數(shù)就會(huì)保存在a[n-1]中。將a[n-1]放入最底部
         * 第二步：執(zhí)行n-2次a[n-1]與a[n-2]的比較之后，數(shù)組中第二大的數(shù)就會(huì)保存在a[n-1]中，此時(shí)最大的數(shù)保存在a[n-2]中。將頂部的兩個(gè)數(shù)據(jù)依次放入最底部
         * ... ：以此類推，知道執(zhí)行n-1次以上類似操作之后
         */
        
        a2_1_14_Test test = new a2_1_14_Test();
        int[] a = {3,9,1,7,6,4,0,8,2,5};    //假設(shè)下標(biāo)8和9是最上面兩層，0是最下面一層
        a = test.sort(a);
        for(int i=0; i<a.length; i++) {
            System.out.println(a[i]);
        }

    }
    
    // 核心代碼
    public int[] sort(int[] a) {
        int m = 1;              //已經(jīng)有序的元素?cái)?shù)量
        int n = a.length;
        while(m <= n) {
            for(int i=0; i<n-m; i++) {
                if(a[n-1] > a[n-2])
                    exch(a, n-1, n-2);
                topToLast(a);   //頂部數(shù)據(jù)放入底部
            }
            for(int i=0; i<m; i++)
                topToLast(a);   
            m++;
        }
        return a;
    }
    
    public void topToLast(int[] a) {
        int m = a.length;
        for(int i=m-1; i>0; i--) {
            exch(a, i, i-1);
        }
    }
    
    public void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
 //less()、exch()、isSorted() 和 show()方法見(jiàn)“排序算法模板”

4.歸并排序

• 歸并：將兩個(gè)有序的數(shù)組歸并成一個(gè)更大的有序數(shù)組。人們?yōu)檫@個(gè)操作發(fā)明的一種簡(jiǎn)單的遞歸排序算法：歸并排序
• 要將一個(gè)數(shù)組排序，可以先（遞歸地）將它分為兩半分別排序，然后將結(jié)果歸并起來(lái)。
• 優(yōu)點(diǎn)：它能夠保證將任意長(zhǎng)度為N的數(shù)組排序所需的時(shí)間和NlogN成正比。
• 主要缺點(diǎn)：它所需的額外空間和N成正比。

歸并排序示意圖

4.1.原地歸并的抽象方法

    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        //將a[lo..mid]和 a[mid+1..hi]歸并
        int i = lo,j = mid+1;
        
        for(int k=lo; k<=hi; k++)  //將a[lo..hi]復(fù)制到aux[lo..hi]
            aux[k] = a[k];
        
        for(int k=lo; k<=hi; k++)  //歸并回到a[lo..hi]
            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++];
    }

• 該方法先將所有元素復(fù)制到aux[]中，然后再歸并回a[]中，方法在歸并時(shí)（第二個(gè)for循環(huán)）進(jìn)行了四個(gè)判斷：左半邊用盡（取右半邊元素）、右半邊用盡（取左半邊元素）、右半邊當(dāng)前元素小于左半邊的當(dāng)前元素（取右半邊元素）、左半邊當(dāng)前元素小于右半邊的當(dāng)前元素（取左半邊元素）。

4.2.自頂向下的歸并排序

• 這是一個(gè)基于原地歸并的抽象實(shí)現(xiàn)的另一種遞歸歸并，這也是應(yīng)用高效算法設(shè)計(jì)中分治思想的最典型的一個(gè)例子。這段遞歸代碼是歸納證明算法能夠正確地將數(shù)組排序的基礎(chǔ)：如果它能將兩個(gè)子數(shù)組排序，它就能通過(guò)歸并兩個(gè)子數(shù)組來(lái)將整個(gè)數(shù)組排序。

public class Merge {
    
    private static Comparable[] aux;  //歸并所需的輔助數(shù)組
    
    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];  //一次性分配空間
        sort(a, 0, a.length-1);
    }
    
    public static void sort(Comparable[] a, int lo, int hi) {
        //將數(shù)組a[lo..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); //歸并結(jié)果（代碼見(jiàn)“原地歸并的抽象方法”）
    }
}

• 要對(duì)子數(shù)組a[lo..hi]進(jìn)行排序，先將它分為a[lo..mid]和a[mid+1..hi]兩部分，分別通過(guò)遞歸調(diào)用將它們單獨(dú)排序，最后將有序的子數(shù)組歸并為最終的排序結(jié)果。

4.2.自底向上的歸并排序

• 實(shí)現(xiàn)遞歸排序的另一種算法是先歸并那些微型數(shù)組，然后再成對(duì)歸并得到的子數(shù)組。直至我們將整個(gè)數(shù)組歸并在一起。這種實(shí)現(xiàn)方法比標(biāo)準(zhǔn)遞歸方法所需要的代碼量更少。

public class MergeBU {
    private static Comparable[] aux; //歸并所需的輔助數(shù)組 name()
    
    public static void sort(Comparable[] a){
        //進(jìn)行l(wèi)gN次兩兩歸并
        int N = a.length;
        aux = new Comparable[N];       //sz子數(shù)組大小
        for(int sz=1; sz<N; sz=sz+sz)  //lo: 子數(shù)組索引
            for(int lo=0; lo<N-sz; lo+=sz+sz)
                merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
    }
}

• 自底向上的歸并排序會(huì)多次遍歷整個(gè)數(shù)組，根據(jù)子數(shù)組的大小進(jìn)行兩兩歸并。子數(shù)組的大小sz的初始值為1，每次加倍。最后一個(gè)子數(shù)組的大小只有在數(shù)組大小為sz的偶數(shù)倍的時(shí)候才會(huì)等于sz（否則它會(huì)比sz?。?/li>
• 自底向上的歸并排序比較適合用鏈表組織的數(shù)據(jù)。
• 用自頂向下或是自底向上的方式實(shí)現(xiàn)任何分治類的算法都很自然。

習(xí)題2.2.10

• 快速歸并：實(shí)現(xiàn)一個(gè)merge()方法，按降序?qū)[]的后半部分復(fù)制到aux[]，然后將其歸并回a[]中。這樣就可以去掉內(nèi)循環(huán)中檢測(cè)某半邊是否用盡的代碼。注意：這樣的排序產(chǎn)生的結(jié)果是不穩(wěn)定的。

官方解答：

private static void merge(Comparable[] a, int lo, int mid, int hi) { 
   for (int i = lo; i <= mid; i++)
      aux[i] = a[i]; 
   
   for (int j = mid+1; j <= hi; j++)
      aux[j] = a[hi-j+mid+1];
  
   int i = lo, j = hi;        //初始i、j對(duì)應(yīng)的值分別為左半部分和右半部分最小值
   for (int k = lo; k <= hi; k++) 
      if (less(aux[j], aux[i])) a[k] = aux[j--];
      else                      a[k] = aux[i++];
}

習(xí)題2.2.11

• 改進(jìn):
  對(duì)自頂向下的歸并排序進(jìn)行三項(xiàng)改進(jìn)：
  1.加快小數(shù)組的排序速度；
  2.檢測(cè)數(shù)組是否已經(jīng)有序；
  3.通過(guò)在遞歸中交換參數(shù)來(lái)避免數(shù)組復(fù)制；
• 解決方案（僅供參考）:
  1.當(dāng)歸并的兩個(gè)子數(shù)組的總長(zhǎng)度N<=4時(shí)，不使用使用插入排序代替歸并排序。
  2.再一次歸并過(guò)程中，如果a[mid] <= a[mid+1],說(shuō)明左半部分有序隊(duì)列中的值均小于有半部分有序隊(duì)列中的值，即對(duì)左半部分和右半部分來(lái)說(shuō)整體有序，不需要再進(jìn)行排序。
  3.將原來(lái)的類靜態(tài)aux[]數(shù)組改為sort()方法中的局部函數(shù)，在遞歸調(diào)用時(shí)作為參數(shù)傳遞。

示例代碼（僅供參考）:

/**
 * Author: wss
 * Time: 2019/5/31 16:30
 * IDE: MyEclipse
 * Content: 1、加快小數(shù)組排序速度
 *          2、檢測(cè)數(shù)組是否已經(jīng)有序
 *          3、通過(guò)在遞歸中交換參數(shù)來(lái)避免數(shù)組復(fù)制
 * */

public class SuperMerge {
    
    public static void main(String[] args) {
        
        SuperMerge smerge = new SuperMerge();
        String[] s = {"F","B","E","A","G","C","H","D","I"};
        smerge.sort(s);
        smerge.show(s);
        
    }
    
    public static void sort(Comparable[] a) {
        //3.用于在遞歸中傳遞; 歸并所需的輔助數(shù)組
        Comparable[] aux = new Comparable[a.length];  //一次性分配空間
        sort(a, 0, a.length-1, aux);
    }

    //******SuperMerge主要變動(dòng)方法******
    public static void sort(Comparable[] a, int lo, int hi, Comparable[] aux) {
        //將數(shù)組a[lo..hi]排序
        if(hi <= lo) return;
        int mid = lo + (hi - lo)/2;
        sort(a, lo, mid,aux);      //將左半邊排序
        sort(a, mid+1, hi, aux);    //將右半邊排序

        //2.檢測(cè)數(shù)組是否已經(jīng)有序; 如果已經(jīng)有序，就不執(zhí)行歸并操作
        if(less(a[mid], a[mid+1])) return;
        else if(hi - lo < 4) {
            //1.加快小數(shù)組排序速度
            insertSort(a, lo, hi);
        } else {
            merge(a, lo, mid, hi, aux); //歸并結(jié)果（代碼見(jiàn)“原地歸并的抽象方法”）
        }
    }

    // 插入排序
    public static void insertSort(Comparable[] a, int lo, int hi) {
        //將a[]升序排列
        for(int i=lo+1; i<=hi; i++) {
            //將a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中
            for(int j=i; j>0 && less(a[j],a[j-1]); j--) {
                exch(a, j, j-1);
            }
        }
    }
    
    public static void merge(Comparable[] a, int lo, int mid, int hi, Comparable[] aux) {
        //見(jiàn)自頂向下排序算法
    }
 //less()、exch()、isSorted() 和 show()方法見(jiàn)“排序算法模板”

習(xí)題2.2.14

• 歸并有序的隊(duì)列。編寫一個(gè)靜態(tài)方法，將兩個(gè)有序的隊(duì)列作為參數(shù)，返回一個(gè)歸并后的有序隊(duì)列。

示例代碼（僅供參考）:

public static void sort(Comparable[] a, Comparable[] b) {
    int al = a.length, bl = b.length;
    int nl =  al + bl;
    int m = 0, n = 0;
    re = new Comparable[nl];
    for(int i=0; i<nl; i++) {
        if(m >= al) re[m+n] = b[n++];
        else if(n >= bl) re[m+n] = a[m++];
        else if(less(a[m], b[n])) re[m+n] = a[m++];
        else re[m+n] = b[n++];
    }
}

5.快速排序

5.1.快速排序

• 特點(diǎn)：
  1.它是原地排序（只需要一個(gè)很小的輔助棧）；
  2.將長(zhǎng)度為N的數(shù)組排序所需的時(shí)間和NlgN成正比；
  我們已經(jīng)了解過(guò)的排序算法都無(wú)法將這兩個(gè)優(yōu)點(diǎn)結(jié)合起來(lái)
  3.快速排序的內(nèi)循環(huán)比大多數(shù)排序算法都要短小，這意味著它無(wú)論是在理論上還是在實(shí)際中都要更快；
• 主要缺點(diǎn)：
  非常脆弱，在實(shí)現(xiàn)時(shí)要非常小心才能避免低劣的性能；
• 快速排序:
  快速排序是一種分治的排序算法。它將一個(gè)數(shù)組分成兩個(gè)子數(shù)組，將兩部分獨(dú)立地排序。快速排序和歸并排序是互補(bǔ)的：歸并排序?qū)?shù)組分成兩個(gè)子數(shù)組分別排序，并將有序的子數(shù)組歸并以將整個(gè)數(shù)組排序；而快速排序?qū)?shù)組排序的方式則是當(dāng)兩個(gè)子數(shù)組都有序時(shí)整個(gè)數(shù)組也就自然有序了。在第一種情況下，遞歸調(diào)用發(fā)生在處理整個(gè)數(shù)組之前；在第二種情況下，遞歸調(diào)用發(fā)生在處理整個(gè)數(shù)組之后。在歸并排序中，一個(gè)數(shù)組被等分為兩半；在快速排序中，切分(partition)的位置取決于數(shù)組的內(nèi)容。

快速排序示意圖

public class Quick {
    
    public static void sort(Comparable[] a) {
        //StdRandom.shuffle(a);  //打亂輸入隊(duì)列; 消除對(duì)輸入的依賴
        sort(a, 0, a.length - 1);
    }
    
    public static void sort(Comparable[] a, int lo, int hi) {
        if(hi <= lo) return;
        int j = partition(a, lo, hi); //切分(請(qǐng)見(jiàn)快速排序的切分)
        sort(a, lo, j-1);             //將左半部分a[lo .. j-1]排序
        sort(a, j+1, hi);             //將右半部分a[j+1 .. hi]排序
    }
    
}

• 快速排序遞歸地將子數(shù)組a[lo..hi]進(jìn)行排序，先用partition()方法將a[j]放到一個(gè)合適的位置，然后再用遞歸調(diào)用將其他位置的元素排序。
• 該方法的關(guān)鍵在于切分，這個(gè)過(guò)程使得數(shù)組滿足下面三個(gè)條件：
  1.對(duì)于某個(gè)j，a[j]已經(jīng)排定；
  2.a[lo]到a[j-1]中的所有元素都不大于a[j]；
  3.a[j+1]到a[hi]中的所有元素都不小于a[j]；
  我們就是通過(guò)遞歸調(diào)用切分來(lái)排序的。
• 切分策略:
  一般策略是先隨意地取a[lo]作為切分元素，即那個(gè)將會(huì)被排定的元素（每一輪切分總是能排定一個(gè)元素），然后從數(shù)組的左端開(kāi)始向右掃描直到找到一個(gè)小于等于它的元素，再?gòu)臄?shù)組的右端開(kāi)始向左掃描直到找到一個(gè)小于它的元素。這兩個(gè)元素顯然是沒(méi)有排定的，因此我們交換它們的位置。如此繼續(xù)，我們就可以保證左指針i的左側(cè)元素都不大于切分元素，右指針j的右側(cè)元素都不小于切分元素。當(dāng)兩個(gè)指針相遇時(shí)，我們只需要將切分元素a[lo]的左子數(shù)組最右側(cè)的元素（a[j]）交換然后返回j即可

快速排序過(guò)程

    public static int partition(Comparable[] a, int lo, int hi) {
        //將數(shù)組切分為a[lo..i-1], a[i], a[i+1..hi]
        int i = lo, j = hi + 1;       //左右掃描指針
        Comparable v = a[lo];         //切分元素
        while(true) {
            //掃描左右,檢查掃描是否結(jié)束并交換元素
            while(less(a[++i], v)) if(i == hi) break;
            while(less(v, a[--j])) if(i == lo) break;
            if(i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);               //將v = a[j]放入正確的位置    
        return j;                     //a[lo..j-1] <= a[j] <= a[j+1..hi]達(dá)成
    }

• 這段代按照a[lo]的值v進(jìn)行切分（a[lo]自始至終都在數(shù)組下標(biāo)為lo的位置）。當(dāng)指針i和j相遇時(shí)主循環(huán)退出。在循環(huán)中，a[i]小于v時(shí)我們?cè)龃骾，a[j]大于v時(shí)我們減小j，然后交換a[i]和a[j]來(lái)保證i左側(cè)的元素都不大于v，j右側(cè)的元素都不小于v。當(dāng)指針相遇時(shí)交換a[lo]和a[j]，切分結(jié)束（這樣切分值就留在a[j]中了）。
• 幾點(diǎn)需要注意的方面:
  1.原地切分
  2.別越界
  3.保持隨機(jī)性
  4.終止循環(huán)
  5.處理切分元素值有重復(fù)的情況
  6.終止遞歸
  
  切分示意圖
  
  
  切分軌跡
• 缺點(diǎn)一:在切分不平衡時(shí)這個(gè)程序可能會(huì)及其低效。例如，如果第一次從最小的元素切分，第二次從第二小的元素切分，如此這般，每次調(diào)用只會(huì)移除一個(gè)元素。這樣會(huì)導(dǎo)致一個(gè)大子數(shù)組需要切分很多次。
• 方案:快速排序最多需要約N方/2次比較，但隨機(jī)打亂數(shù)組能夠預(yù)防這種情況。

5.2.快速排序算法改進(jìn)

5.2.1.切換到插入排序

• 對(duì)于小數(shù)組，快速排序比插入排序慢；
• 因?yàn)檫f歸，快速排序的sort()方法在小數(shù)組中也會(huì)調(diào)用自己
  因此，在排序小數(shù)組時(shí)應(yīng)該切換到插入排序

改進(jìn)示例:

// 將sort()中的語(yǔ)句：
if(hi <= lo) return;

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

• M: 轉(zhuǎn)換參數(shù)M的最佳值是和系統(tǒng)相關(guān)的，但是5~15之間的任意值在大多數(shù)情況下都能令人滿意。

5.2.2.三取樣切分

• 改進(jìn)快速排序性能的第二個(gè)辦法是使用子數(shù)組的一部分元素的中位數(shù)來(lái)切分?jǐn)?shù)組。這樣做的切分更好，但代價(jià)是需要計(jì)算中位數(shù)。將取樣大小設(shè)為3并用大小居中的元素切分的效果最好。我們還可以將取樣元素放在數(shù)組末尾作為“哨兵”來(lái)去掉partition()中的數(shù)組邊界測(cè)試。
  
  使用了三取樣切分和插入排序轉(zhuǎn)換的快速排序

5.2.3.熵最優(yōu)的排序

• 實(shí)際應(yīng)用中經(jīng)常會(huì)出現(xiàn)含有大量重復(fù)元素的數(shù)組。這些情況下，我們實(shí)現(xiàn)的快速排序性能尚可，但還有巨大的改進(jìn)空間。例如，一個(gè)元素全部重復(fù)的子數(shù)組就不需要繼續(xù)排序了。
• 一個(gè)簡(jiǎn)單的想法是將數(shù)組切分為三部分，分別對(duì)應(yīng)小于、等于和大于切分元素的數(shù)組元素。這種切分實(shí)現(xiàn)起來(lái)比我們目前使用的二分法更復(fù)雜。
• Dijkstra的解法如“三向切分的快速排序”中極為簡(jiǎn)潔的切分代碼所示。它從左到右遍歷數(shù)組一次，維護(hù)一個(gè)指針lt使得a[lo..lt-1]中的元素都小于v，一個(gè)指針gt使得a[gt+1..hi]中的元素都大于v，一個(gè)指針i使得a[lt..i-1]中的元素都等于v，a[i..gt]中的元素都還未確定，如下圖所示。一開(kāi)始i和lo相等，我們使用Comparable接口（而非less()）對(duì)a[i]進(jìn)行三向比較來(lá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加一。
• 這些操作都會(huì)保證數(shù)組元素不變且縮小gt-i的值（這樣循環(huán)才會(huì)結(jié)束）。另外，除非和切分元素相等，其他元素都會(huì)被交換。
  
  三向切分的示意圖

三向切分的快速排序:

public class Quick3way {
    
    public static void sort(Comparable[] a) {
        //StdRandom.shuffle(a);  //打亂輸入隊(duì)列; 消除對(duì)輸入的依賴
        sort(a, 0, a.length - 1);
    }
    
    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++;
        } //現(xiàn)在a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]成立
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
    }
    
}

• 這段排序代碼的切分能夠?qū)⒑颓蟹衷叵嗟鹊脑貧w位，這樣它們就不會(huì)被包含在遞歸調(diào)用處理的子數(shù)組之中了。對(duì)于存在大量重復(fù)元素的數(shù)組，這種方法比標(biāo)準(zhǔn)的快速排序的效率高得多。
• 三向切分的快速排序的可視軌跡:

三向切分的軌跡（每次迭代循環(huán)之后的數(shù)組內(nèi)容）

三向切分的快速排序的可視軌跡

• 對(duì)于標(biāo)準(zhǔn)的快速排序，隨著數(shù)組規(guī)模的增大其運(yùn)行時(shí)間會(huì)趨于平均運(yùn)行時(shí)間，大幅偏離的情況非常罕見(jiàn)，因此可以肯定三向切分的快速排序的運(yùn)行時(shí)間和輸入的信息量的N倍是成正比的。
• 對(duì)于包含大量重復(fù)元素的數(shù)組，它將排序時(shí)間從線性對(duì)數(shù)級(jí)降到了線性級(jí)別。
• 這種對(duì)重復(fù)元素的適應(yīng)性使得三分切向的快速排序成為排序庫(kù)函數(shù)的最佳算法選擇——需要將包含大量重復(fù)元素的數(shù)組排序的用例很常見(jiàn)。
• 但這并不是快速排序發(fā)展的終點(diǎn)，因?yàn)橛腥搜芯砍隽送耆恍枰容^的排序算法！但快速排序的另一個(gè)版本在那個(gè)環(huán)境下仍然是最棒的，和這里一樣。

6.優(yōu)先隊(duì)列

• 許多應(yīng)用程序都需要處理有序的元素，但不一定要求他們?nèi)坑行?，或是不一定要一次就將它們排序。很多情況下我們會(huì)收集一些元素，處理當(dāng)前鍵值最大的元素，然后再收集更多的元素，在處理當(dāng)前鍵值最大的元素。
• 在這種情況下，一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該支持兩種操作：刪除最大元素和插入元素。這種數(shù)據(jù)類型叫做優(yōu)先隊(duì)列。
• 我們會(huì)學(xué)習(xí)基于二叉堆數(shù)據(jù)結(jié)構(gòu)的一種優(yōu)先隊(duì)列的經(jīng)典實(shí)現(xiàn)方法，用數(shù)組保存元素并按照一定條件排序，以實(shí)現(xiàn)高效地（對(duì)數(shù)級(jí)別的）刪除最大元素和插入元素操作。
• 通過(guò)插入一列元素然后一個(gè)個(gè)地刪掉其中最小的元素，我們可以用優(yōu)先隊(duì)列實(shí)現(xiàn)排序算法。一種名為堆排序的重要排序算法也來(lái)自基于堆的優(yōu)先隊(duì)列的實(shí)現(xiàn)。

優(yōu)先隊(duì)列的調(diào)用示例

• 現(xiàn)在我們來(lái)考慮一個(gè)問(wèn)題：輸入N個(gè)字符串，每個(gè)字符串都對(duì)應(yīng)著一個(gè)整數(shù)，你的任務(wù)就是從中找出最大的（或是最小的）M個(gè)整數(shù)（及其關(guān)聯(lián)的字符串）。
• 要處理這個(gè)問(wèn)題，只要我們能夠高效地實(shí)現(xiàn)insert()和delMin()，下面的優(yōu)先隊(duì)列用例中調(diào)用了MinPQ的TopM就能使用優(yōu)先隊(duì)列解決這個(gè)問(wèn)題，這就是我們的目標(biāo)。

一個(gè)優(yōu)先隊(duì)列的示例:

public class TopM {
    
    public static void main(String[] args) {
        //打印輸入流中最大的M行
        int M = Integer.parseInt(args[0]);
        MinPQ<Transaction> pq = new MinPQ<Transaction>(M+1);
        while(StdIn.hasNextLine()) {
            //為下一行輸入創(chuàng)建一個(gè)元素并放入優(yōu)先隊(duì)列中
            pq.insert(new Transection(StdIn.readLine()));
            if(pq.size() > M) 
                pq.delMin();  //如果優(yōu)先隊(duì)列中存在M+1個(gè)元素則刪除其中最小的元素
        } //最大的M個(gè)元素都在優(yōu)先隊(duì)列中
    }
    Stack<Transection> stack = new Stack<Transection>();
    while(!pq.isEmpty()) stack.push(pq.delMin());
    for(Transection t : stack) StdOut.println(t);
}

• 從命令行輸入一個(gè)整數(shù)M，從輸入流中獲得一系列字符串，輸入流的每一行代表一個(gè)交易。這段代碼調(diào)用了MinPQ()并會(huì)打印數(shù)字最大的M行。它用到了Transection類構(gòu)造了一個(gè)用數(shù)字作為鍵的優(yōu)先隊(duì)列。當(dāng)優(yōu)先隊(duì)列的大小超過(guò)M時(shí)就刪掉其中最小的元素。處理完所有交易，優(yōu)先隊(duì)列中存放者以降序排列的最大的M個(gè)交易，然后這段代碼將它們放入到一個(gè)棧中，遍歷這個(gè)棧以顛倒它們的順序，從而將它們按降序打印出來(lái)。

6.1.初級(jí)實(shí)現(xiàn)

• 數(shù)組實(shí)現(xiàn)（無(wú)序）：基于下壓棧實(shí)現(xiàn)。insert()方法和棧的push()方法完全一樣。刪除元素類似于選擇排序的內(nèi)循環(huán)代碼，將最大的元素和邊界元素交換然后刪除它。...
• 數(shù)組實(shí)現(xiàn)（有序）：insert()方法和插入排序一樣，刪除操作與棧的pop()操作一樣。
• 鏈表表示法：后續(xù)實(shí)現(xiàn)...
• 使用無(wú)序序列是解決這個(gè)問(wèn)題的惰性方法，我們僅在必要的時(shí)候才會(huì)采取行動(dòng)（找出最大元素）；使用有序序列則是解決問(wèn)題的積極方法，因?yàn)槲覀儠?huì)盡可能未雨綢繆（在插入元素時(shí)就保持列表有序），使后續(xù)操作更高效。
• 實(shí)現(xiàn)?；蚴顷?duì)列與實(shí)現(xiàn)優(yōu)先隊(duì)列的最大不同在于對(duì)性能的要求。對(duì)于棧和隊(duì)列，我們的實(shí)現(xiàn)能夠在常數(shù)時(shí)間內(nèi)完成操作；而對(duì)于優(yōu)先隊(duì)列，我們剛剛討論的所有初級(jí)實(shí)現(xiàn)中，插入元素和刪除最大元素這兩個(gè)操作之一在最壞的情況下需要線性時(shí)間內(nèi)來(lái)完成。下面我們將討論的是基于數(shù)據(jù)結(jié)構(gòu)堆的實(shí)現(xiàn)能夠保證這兩種操作都能更快地執(zhí)行。

表：優(yōu)先隊(duì)列的各種實(shí)現(xiàn)在最壞情況下運(yùn)行時(shí)間的增長(zhǎng)級(jí)

6.2.堆的定義

• 數(shù)據(jù)結(jié)構(gòu)二叉堆能夠很好地實(shí)現(xiàn)優(yōu)先隊(duì)列的基本操作。在二叉堆的數(shù)組中，每個(gè)元素都要保證大于等于另兩個(gè)特定位置的元素。相應(yīng)的，這些位置的元素又至少要大于等于數(shù)組中的另兩個(gè)元素，以此類推。如果我們將所有元素畫成一棵二叉樹(shù)，將每個(gè)較大元素和兩個(gè)較小的元素用邊連接就可以很容易看出這種結(jié)構(gòu)。
• 當(dāng)一顆二叉樹(shù)的每個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子結(jié)點(diǎn)時(shí)，它被稱為堆有序。
• 根節(jié)點(diǎn)是堆有序的二叉樹(shù)中的最大結(jié)點(diǎn)。

二叉堆表示法:

• 如果我們用指針來(lái)表示堆有序的二叉樹(shù)，那么每個(gè)元素都需要三個(gè)指針來(lái)找到它的上下節(jié)點(diǎn)（父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)各需要一個(gè)）。
• 如果我們使用完全二叉樹(shù)，表達(dá)就會(huì)變得特別方便。要畫出這樣一顆完全二叉樹(shù)，可以先定義下根節(jié)點(diǎn)，然后一層一層地由上向下、由左向右，在每個(gè)結(jié)點(diǎn)的下方連接兩個(gè)更小的結(jié)點(diǎn)，直至將N個(gè)結(jié)點(diǎn)全部連接完畢。
• 完全二叉樹(shù)只用數(shù)組而不需要指針就可以表示。具體方法就是將二叉樹(shù)的結(jié)點(diǎn)按照層級(jí)順序放入數(shù)組中，根結(jié)點(diǎn)的位置1，它的子結(jié)點(diǎn)的位置2和3，而子結(jié)點(diǎn)的子結(jié)點(diǎn)則分別在位置1、5、6和7，以此類推。
• 二叉堆是一組能夠用堆有序的完全二叉樹(shù)排序的元素，并在數(shù)組中按照層級(jí)存儲(chǔ)（不使用數(shù)組的第一個(gè)位置）

一棵堆有序的完全二叉樹(shù)

堆的表示

6.3.堆的算法

• 我們用長(zhǎng)度為N+1的私有數(shù)組pq[]來(lái)表示一個(gè)大小為N的堆，我們不會(huì)使用pq[0]，堆元素放在pq[1]至pq[N]中。在排序算法中，我們只通過(guò)私有輔助函數(shù)less()和exch()來(lái)訪問(wèn)元素，但因?yàn)樗械脑囟荚跀?shù)組pq[]中，我們將會(huì)在后面使用更加緊湊的實(shí)現(xiàn)方式，不再將數(shù)組作為參數(shù)傳遞。
• 堆的操作會(huì)首先進(jìn)行一些簡(jiǎn)單的改動(dòng)，打破堆的狀態(tài)，然后再遍歷堆并按照要求將堆的狀態(tài)恢復(fù)，我們稱這個(gè)過(guò)程叫做堆的有序化。

比較與交換方法:

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

• 當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級(jí)上升（或是在堆底加入一個(gè)新的元素）時(shí)，我們需要由下至上恢復(fù)堆的順序。
• 當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級(jí)下降（例如：將根節(jié)點(diǎn)替換為一個(gè)較小的元素）時(shí)，我們需要由上至下恢復(fù)堆的順序。
• 首先我們會(huì)學(xué)習(xí)如何實(shí)現(xiàn)這兩種輔助操作，然后再用它們實(shí)現(xiàn)插入元素和刪除最大元素的操作。

6.3.1.由下至上的堆有序化（上浮）

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

由下至上的堆有序化（上?。?/div>

6.3.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;
    }
}

由上至下的堆有序化（下沉）

插入元素:

• 我們將新元素加到數(shù)組末尾，增加堆的大小并讓這個(gè)新元素上浮到合適的位置

刪除最大元素:

• 我們從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個(gè)元素放到頂端，減小堆的大小并讓這個(gè)元素下沉到合適的位置。

堆的操作

• 下面的算法解決了我們?cè)诒竟?jié)開(kāi)始時(shí)提出的一個(gè)基本問(wèn)題：它對(duì)優(yōu)先隊(duì)列API的實(shí)現(xiàn)能夠保證插入元素和刪除最大元素這兩個(gè)操作的用時(shí)和隊(duì)列的大小僅成對(duì)數(shù)關(guān)系。

public class MaxPQ {
    private Key[] pq;    //基于堆的完全二叉樹(shù)
    private int N = 0;   //存儲(chǔ)于pq[1..N]中,pq[0]沒(méi)有使用
    
    public MaxPQ(int maxN) 
    { pq = (Key[]) new Comparable[maxN+1]; }
    
    public boolean issEmpty()
    { 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;
    }
    
    //輔助方法的實(shí)現(xiàn)請(qǐng)見(jiàn)本節(jié)前面的代碼框
    private boolean less(int i, int j);
    private void exch(int i, int j);
    private void swim(int k);
    private void sink(int k);
}

• 對(duì)于一個(gè)含有N個(gè)元素的基于堆的優(yōu)先隊(duì)列，插入元素操作只需不超過(guò)（lgN+1）次比較，刪除最大元素的操作需要不超過(guò)2lgN次比較。

6.3.3.多叉堆

6.3.4.調(diào)整數(shù)組大小

6.3.5.元素的不可變性

6.3.6.索引優(yōu)先隊(duì)列

• 在很多應(yīng)用中，允許用例引用已經(jīng)進(jìn)入優(yōu)先隊(duì)列的元素是有必要的。做到這一點(diǎn)的一種簡(jiǎn)單方法是給每一個(gè)元素添加一個(gè)索引。另外，一種常見(jiàn)的情況是用例已經(jīng)有了總量為N的多個(gè)元素，而且可能還同時(shí)使用了多個(gè)（平行）數(shù)組來(lái)存儲(chǔ)這些元素的信息。此時(shí)，其他無(wú)關(guān)的用例代碼可能已經(jīng)在使用一個(gè)整數(shù)索引來(lái)引用這些元素了。

關(guān)聯(lián)索引的泛型優(yōu)先隊(duì)列的API:

返回類型	函數(shù)名稱	功能
	IndexMinPQ(int maxN)	創(chuàng)建一個(gè)最大容量為maxN的優(yōu)先隊(duì)列，索引的取值范圍為0至maxN-1
void	insert(int k, Item item)	插入一個(gè)元素，將它和索引k相關(guān)聯(lián)
void	change(int k, Item item)	將索引k的元素設(shè)為item
boolean	contains(int k)	是否存在索引為k的元素
void	delete(int k)	刪去索引k及其相關(guān)聯(lián)的元素
Item	min()	返回最小元素
int	minIndex()	返回最小元素的索引
int	delMin()	刪除最小元素并返回它的索引
boolean	isEmpty()	優(yōu)先隊(duì)列是否為空
int	size()	優(yōu)先隊(duì)列中元素?cái)?shù)量

• 在一個(gè)大小為N的索引優(yōu)先隊(duì)列中，插入元素（insert）、改變優(yōu)先級(jí)（change）、刪除（delete）和刪除最小元素（remove the minimum）操作所需的比較次數(shù)和logN成正比
• 這段討論中針對(duì)的是找出最小元素的隊(duì)列。

6.3.7.索引優(yōu)先隊(duì)列用例

• 下面調(diào)用了IndexMinPQ的代碼Multiway解決了多向歸并問(wèn)題：它將多個(gè)有序的輸入流歸并成一個(gè)有序的輸入流。如果有足夠的空間，你可以把它們簡(jiǎn)單地讀入一個(gè)數(shù)組并排序，但如果使用了優(yōu)先隊(duì)列，無(wú)論輸入有多長(zhǎng)你都可以把它們?nèi)孔x入并排序。

使用優(yōu)先隊(duì)列的多向歸并:

public class Multiway {
    
    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()) {
            System.out.println(pq.min());
            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);
    }

}

• 每個(gè)輸入流的索引都關(guān)聯(lián)著一個(gè)元素（輸入中的下個(gè)字符串）。
• 初始化之后，代碼進(jìn)入一個(gè)循環(huán)，刪除并打印出隊(duì)列中最小的字符串，然后將該輸入的下一個(gè)字符串添加為一個(gè)元素。

6.4.堆排序

• 我們可以把任意優(yōu)先隊(duì)列變成一種排序方法。將所有元素插入一個(gè)查找最小元素的優(yōu)先隊(duì)列，然后再重復(fù)調(diào)用刪除最小元素的操作來(lái)將它們按順序刪去。
• 堆排序可以分為兩個(gè)階段。在堆的構(gòu)造階段中，我們將原始數(shù)組重新阻止安排進(jìn)一個(gè)堆中，這樣會(huì)得到一個(gè)堆有序的完全二叉樹(shù)；然后再下沉排序階段，我們從堆中按遞減順序取出所有元素并得到排序結(jié)果。我們將使用一個(gè)面向最大元素的優(yōu)先隊(duì)列并重復(fù)刪除最大元素。

6.4.1.堆的構(gòu)造

• 從右至左用sink()函數(shù)構(gòu)造子堆。數(shù)組的每個(gè)位置都已經(jīng)是一個(gè)堆的根節(jié)點(diǎn)了，sink()對(duì)于這些子堆也適用。如果一個(gè)結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)都已經(jīng)是堆了，那么在該結(jié)點(diǎn)上調(diào)用sink()函數(shù)可以將它們變成一個(gè)堆。這個(gè)過(guò)程會(huì)遞歸地建立起堆的秩序。開(kāi)始時(shí)我們只需掃描數(shù)組中的一半元素，因?yàn)槲覀兛梢蕴^(guò)大小為1的子堆（也就是葉子結(jié)點(diǎn)）。最后我們?cè)谖恢?上調(diào)用sink()方法，掃描結(jié)束。
• 用下沉操作由N個(gè)元素構(gòu)造堆只需少于2N次比較以及少于N次交換。

堆排序

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

堆排序的軌跡

堆排序：堆的構(gòu)造（左和下沉排序（右））

6.4.2.下沉排序

• 堆排序的主要工作都是在第二階段完成的。這里我們將堆中最大元素刪除，然后放入堆縮小后數(shù)組空出的位置。
• 將N個(gè)元素排序，堆排序只需少于（2NlgN+2N）次比較（以及一般次數(shù)的交換）。

對(duì)排序的可視軌跡

6.4.3.先下沉后上浮

大多數(shù)在下沉排序期間重新插入堆的元素會(huì)被直接加入到堆底。Floyd在1964年觀察發(fā)現(xiàn)，我們正好可以通過(guò)免去檢查元素是否到達(dá)正確位置來(lái)節(jié)省時(shí)間。在下沉中總是直接提升較大的子結(jié)點(diǎn)直至到達(dá)堆底，然后使元素上浮到正確的位置。這種想法幾乎可以將比較次數(shù)減少一半——接近了歸并排序所需的比較次數(shù)（隨機(jī)數(shù)組），但是這種方法需要額外的空間。

• 堆排序在排序復(fù)雜性的研究中有著重要的地位，因?yàn)樗俏覀兯奈ㄒ荒軌蛲瑫r(shí)最優(yōu)的利用空間和時(shí)間的方法——在最壞的情況下也能保證用~2NlgN次比較和恒定的額外空間。
• 堆排序無(wú)法利用緩存。數(shù)組元素很少和相鄰的其他元素進(jìn)行比較，因此緩存未命中的次數(shù)要遠(yuǎn)遠(yuǎn)高于大多數(shù)比較都在相鄰元素間進(jìn)行的算法，如快速排序、歸并排序，甚至是希爾排序。

至此，算法基礎(chǔ)進(jìn)階就基本結(jié)束了，由于博主精力有限，后續(xù)的查找、圖、字符串章節(jié)就不在做記錄，如果讀者對(duì)這些算法感興趣，可以去書店或網(wǎng)上商城購(gòu)買《算法》這本書，真的很不錯(cuò)。謝謝大家閱讀此文，后續(xù)我有可能會(huì)在學(xué)習(xí)后面的章節(jié)時(shí)做筆記來(lái)紀(jì)錄知識(shí)，看精力吧，畢竟博主不是專門學(xué)習(xí)算法的啊。

聲明：發(fā)表此文是出于傳遞更多信息之目的，并且做一些學(xué)習(xí)筆錄是為了日后學(xué)習(xí)之用。文章大部分代碼示例與文字內(nèi)容均摘自《算法》一書。若有來(lái)源標(biāo)注錯(cuò)誤或侵犯了您的合法權(quán)益，請(qǐng)作者持權(quán)屬證明與本我們(QQ:981086665；郵箱:981086665@qq.com)聯(lián)系聯(lián)系，我們將及時(shí)更正、刪除，謝謝。