排序算法

本篇文章參考《算法(第四版)》以下為文章的整體結(jié)構(gòu)，方便瀏覽，也方便我以后回憶。

排序.png

初級排序算法

游戲規(guī)則

我們以數(shù)組為源數(shù)據(jù)，將他們按照順序排列好。以下為對應算法的模板。
排序算法類的模板

public class Example
{
    public static void sort(Comparable[] a){}
    private static boolean less(Comparable v, Comparable w)
    {return v.compareTo() <0;}
    private static void exch(Comparable[] a, int i, int j)
    {Comparable t = a[i]; a[i] = a[j];a[j]= t;}
    private static void show(Comparable[] a)
    {
        for(int i = 0; i< a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }
    public static boolean isSorted(Comarable[] a)
    {
        for(int i = 1; i< a.length; i++)
            if(less(a[i], a[i-1])) return false;
        return true;
    }
    public static void main(String[] args){
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

在大多數(shù)情況下，排序的代碼智慧通過兩個方法操作數(shù)據(jù)：less() 方法對元素進行比較，exch() 方法將元素交換位置。isSorted()判斷是否完成排序。

額外的內(nèi)存使用 ： 排序算法的額外內(nèi)存和運行時間同等重要。排序算法可以分成兩類，除了函數(shù)調(diào)用所需要的棧和固定數(shù)目的實例變量之外無需額外內(nèi)存的原地排序算法，以及需要額外內(nèi)存空間來存儲另一份數(shù)組副本的其他排序算法。

選擇排序

public class Selection
{
    public static void sort(Comparable[] a)
    {  // 將a[] 按升序排列
        int N = a.length;    // 數(shù)組長度
        for(int i = 0; i< N; i++){  // 將a[i] 和 a[i+1.. N] 中最小元素交換
            int min = i;    // 最小元素的索引
            for(int j = i+1; j< N; j++)
                if(less(a[j], a[min])) min =j;
            exch(a,i, min);
        }
    }
}

總的來說：排序算法是一種很容易理解和實現(xiàn)的簡單排序算法，它有兩個很鮮明的特點。

  • 運行時間和輸入無關
  • 數(shù)據(jù)一定是最少的。

命題A： 對于長度為N 的數(shù)組，選擇排序需要大約 N^2 /2 次比較和 N 次交換。

插入排序

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

下面是幾種典型的部分有序的數(shù)組：

  • 數(shù)組中每個元素距離它的最終位置都不遠
  • 一個有序的數(shù)組接一個小數(shù)組
  • 數(shù)組中有幾個元素的位置不確定
    插入排序?qū)@樣的數(shù)組很有效，而選擇排序則不然。事實上，當?shù)怪玫臄?shù)量很少時，插入排序很可能比本章中的其他任何算法都要快。

命題B 對于隨機排列的長度為N且主鍵不重復的數(shù)組，平均情況下插入排序需要 ~ N^2 /4 次比較以及 ~ N^2 /4 次交換。最壞情況下需要 ~N^2/2 次比較和 ~ N^2/2 最好的情況需要 N-1 次比較和0 次交換。
插入排序需要的交換操作和數(shù)組中倒置的數(shù)量相同，需要的比較次數(shù)大于等于倒置的數(shù)量，小于等于倒置的數(shù)量加上數(shù)組的大小再減一。

比較兩個算法

對于隨機排序的無重復主鍵的數(shù)組，插入排序和選擇排序的運行時間是平方級別的，兩者之比應該是一個較小的常熟。

希爾排序

希爾排序的思想是一個 h 有序數(shù)組就是 h 個互相獨立的有序數(shù)組編織在一起組成一個數(shù)組。

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

歸并排序

要將一個數(shù)組排序，可以先將它分成兩半分別排序，然后將結(jié)果歸并起來。

  • 自頂向下的歸并排序

    public class Merge{
    private staitc Comparable[] aux;              //歸并所需的輔助數(shù)組
    public static void sort(Comparable[] a){
        aux = new Comparable[a.kength];           //一次性分配空間
        sort(a,0,a.length - 1);
    }
    
    private static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int mid = lo +(hi - lo)/2;
        sort(a,lo,mid);               //將左半邊排序
        sort(a, mid+1, hi);           //將右半邊排序
        merge(a,lo,mid,hi);           //歸并結(jié)果
    }
}

    命題F： 對于長度為N的任意數(shù)組，自頂向下的歸并排序需要 1/2N lg(N) 至 Nlg(N)次比較。

    命題G： 對于長度為N的任意數(shù)組，自頂向下的歸并排序最多需要訪問數(shù)組 6NlgN 次。

    • 對小規(guī)模子數(shù)組使用插入排序
    • 測試數(shù)組是否已經(jīng)有序
    • 不將元素復制到輔助數(shù)組

  • 自底向上的歸并排序

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

    命題H： 對于長度為 N 的任意數(shù)組，自底向下的歸并排序需要 1/2 NlgN 至 NlgN 次比較，最多訪問數(shù)組 6NlgN 次。

    命題I： 沒有任何基于比較的算法能夠保證使用少于 lg(N!) ~ NlgN 次比較長度將問 N 的數(shù)組排序。

  • 排序算法的復雜度

快速排序

  • 基本算法

    public class Quick{
    public static void sort(Comparable[] a){
        StdRandom.shuffle(a);         //消除對輸入的依賴
        sort(a,0, a.length -1);
    }
    private static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int j = partition(a, lo, hi);   //切分
        sort(a, lo, j-1);               //將左半部分
        sort(a, j+1, hi);               //將右半部分
    }
}

    // 快速排序的切分
private static int partition(Comparable[] a, int lo, int hi){
    int i = lo, j = hi+1;        //左右掃描指針
    Comparable v = a[lo];        // 切分元素
    while(true){                 // 掃描左右，檢查掃描是否結(jié)束并交換文件
        while(less(a[++i],v)) if(i == hi) break;
        while(less(v,a[--j])) if(j == lo) break;
        if(i>= j) break;
        exch(a,i,j);
    }
    exch(a,lo,j);              //將 v = a[j] 放入正確的位置
    return j;
}
  • 性能特點

命題K： 將長度為 N 的無重復數(shù)組排序，快速排序平均需要 ~2NlnN次比較

命題L： 快速排序最多約 N^2 次比較，但是隨機打亂數(shù)組能夠預防這種情況。

  • 算法改進

    • 切換到插入排序
    • 三取樣切分
    public class Quick2way{
    private static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int lt = lo, i = lo+1, gt = hi;
        Comparable v = a[lo];
        while(i <= gt){
            int cmp = a[i].compareTo(v);
            if(cmp < 0) exch(a, lt++, i++);
            else if(cmp > 0) exch(a,i,gt--);
            else i++;
        }
        sort(a, lo, lt - 1);
        sort(a, gt+1, hi);
    }
}

    命題M： 不存在任何基于比較的排序算法能夠保證在 NH-N 次比較之內(nèi)將 N 個 元素排序，其中H 為由主鍵值出現(xiàn)頻率定義的香農(nóng)信息量。

    命題N： 對于大小為 N 的數(shù)組，三向切分的快速排序需要~(2ln2)NH次比較。其中H 為由主鍵值出現(xiàn)頻率定義的香農(nóng)信息量。

    • 熵最優(yōu)的排序

優(yōu)先隊列

  • API

  • 初級實現(xiàn)

    • 數(shù)組實現(xiàn)（無序）
    • 數(shù)組實現(xiàn)（有序）
    • 鏈表表示法

  • 堆的定義

    定義： 當一棵二叉樹的每個節(jié)點都大于等于它的兩個子結(jié)點時，它被成為堆有序。

  • 堆的算法

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

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

      public class MaxPQ<Key extends Comparable<key>>{
    private Key[] pd;
    private int N = 0;
    public MaxPQ(int maxN){
        pq = (key[]) new Comparable[maxN+1];
    }
    public boolean isEmpty(){
        return N == 0;
    }
    public int size(){
        return N;
    }
    public void insert(Key v){
        pq[++N] = v;
        swim(N);
    }
    public Key delMax(){
        Key max = pq[1];      //從根結(jié)點得到最大元素
        exch(1,N--);          //將其和最后一個結(jié)點交換
        pq[N+1] = null;       // 防止越界
        return max;           // 恢復堆的有序性
    }
}

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

  • 堆排序

        public static void sort(Comparable[] a){
    int N = a.length;
    for(int k = N/2; k >= 1;k--)
        sink(a,k,N);
    while(N>1){
        exch(a,1,N--);
        sink(a,1,N);
    }
}
    • 堆的構(gòu)造
    • 下沉排序

    命題 S： 將N個元素排序，堆排序只需要少于（2NlgN+2N）次比較。

最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容