算法學(xué)習(xí)筆記 - Alogrithm Fourth Edition

排序算法

選擇排序(Selection)

如果有N個(gè)數(shù)組，從第一個(gè)元素開始往后選擇，與后面的每一個(gè)元素做對(duì)比，挑出最小的元素，如果后面元素中有一個(gè)最小的值，則把這個(gè)值放到第一位。然后從第二位數(shù)開始，繼續(xù)往后面的元素做對(duì)比，挑出最小元素，如果后面元素中有一個(gè)最小的值，則把這個(gè)值放到第二位。以此重復(fù)操作到第N位，排序就完成了。

public class Selection {
    Selection() {

    }

    public static void main(String[] args) {
        int[] a = new int[] { 1, 2, 5, 7, 9, 12, 93, 5, 4, 6, 88 };
        show(a);
        Selection.sort(a);
        show(a);
    }

    public static void sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int mini = i;
            for (int j = i + 1; j < a.length; j++) {
                if (less(a[j], a[mini])) {
                    mini = j;
                }
            }
            exch(a, i, mini);
        }
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

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

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

插入排序

假設(shè)有N個(gè)元素的數(shù)組，從第二元素開始，與左邊的第一元素比較，如果第二個(gè)比第一個(gè)元素小則插入第一個(gè)前面。接著從第三個(gè)開始與左邊元素與第二個(gè)比較，如果第三個(gè)小于第二個(gè)，則插入到第二個(gè)前面，接著比較第一個(gè)。以此類推。

package com.srs.test;

public class Insert {
    Insert() {
    }

    public static void main(String[] args) {
        int[] a = new int[] { 1, 2, 5, 7, 9, 12, 93, 5, 4, 6, 88 };
        show(a);
        Selection.sort(a);
        show(a);
    }

    private void sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            for(int j = i;j>0&&less(a,j,j-1);j--){
                exch(a,j,j-1);
            }
        }
    }
    
    private boolean less(int[] a,int i,int j){
        return a[i]<a[j];
    }
    
    private static void exch(int[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = (int) swap;
    }
    
    private static void show(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

希爾排序

插入排序在極端情況下有可能最右端的數(shù)值要經(jīng)過其他全部數(shù)值的比較才到達(dá)第一位。所以當(dāng)數(shù)組長(zhǎng)度很大時(shí)，排序的效率就非常低了，后來便有了希爾排序，希爾排序是插入排序的優(yōu)化，它的基礎(chǔ)原理思想就是，將數(shù)組分成幾個(gè)小隊(duì)列，讓數(shù)組元素跨數(shù)組排列。當(dāng)分組排列完成后，縮小組別的長(zhǎng)度，重復(fù)上面的排序，直至最后做普通的插入排序即完成了希爾排序；

• 例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長(zhǎng)為5開始進(jìn)行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應(yīng)該看起來是這樣：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我們對(duì)每列進(jìn)行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

將上述四行數(shù)字，依序接在一起時(shí)我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時(shí)10已經(jīng)移至正確位置了，然后再以3為步長(zhǎng)進(jìn)行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后變?yōu)椋?/p>

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步長(zhǎng)進(jìn)行排序（此時(shí)就是簡(jiǎn)單的插入排序了）。

代碼如下：

public class Shell extends BaseClass {
    public static void main(String[] args) {
        startTest(new Shell());
    }

    @Override
    public void sort(int[] 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 - h; j >= 0 && less(a, j + h, j); j -= h) {
                    exch(a, j + h, j);
                }
            }
            h /= 3;
        }
    }
}

歸并排序

分治是歸并排序的基本思想，將一數(shù)組通過不斷的分化，直至最小，元素?cái)?shù)量為2的小數(shù)組，小數(shù)組排序后再和其他小數(shù)組合并合并的時(shí)候也做排序，合并完成后再與另外一組同樣有小數(shù)組再繼續(xù)合并，指導(dǎo)最終排序完成

public class Merge extends BaseClass {
    public static void main(String[] args) {
        startTest(new Merge());
    }

    @Override
    public void sort(int[] a) {
        sort(a,0,a.length-1);
    }

    public void sort(int[] 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);
    }

    public void merge(int[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        int[] arr = new int[a.length];
        for (int k = lo; k <= hi; k++) {
            arr[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = arr[j++];
            } else if (j > hi) {
                a[k] = arr[i++];
            } else if (less(arr[j], arr[i])) {
                a[k] = arr[j++];
            } else {
                a[k] = arr[i++];
            }
        }

    }

}

快速排序

快速排序使用分治法（Divide and conquer）策略來把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。選取一個(gè)基準(zhǔn)值，程序同時(shí)從左端和右端向中間靠攏，首先左端和右端同基準(zhǔn)值做比較，左端小于基準(zhǔn)值時(shí)光標(biāo)繼續(xù)移動(dòng)，直至左端大于基準(zhǔn)值，右端的大于基準(zhǔn)值時(shí)光標(biāo)繼續(xù)移動(dòng)，直至右端小于基準(zhǔn)值，這時(shí)候交換左端右端位置。接著繼續(xù)移動(dòng)左右端光標(biāo)重復(fù)以上操作。當(dāng)兩端相遇時(shí)完成左右端大小歸類。然后繼續(xù)分裂左右端歸類后的數(shù)組，數(shù)組不能再繼續(xù)分裂排序就完成了

public class Quick extends BaseClass {
    public static void main(String[] args) {
        startTest(new Quick());
    }
    
    @Override
    public void sort(int[] a) {
        sort(a,0,a.length-1);
    }

    public void sort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j + 1, hi);
    }

    private int partition(int[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        int v = a[lo];
        while (true) {

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

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

堆的定義

當(dāng)一棵二叉樹的每一個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子節(jié)點(diǎn)是，它被稱為有序堆