數(shù)據(jù)結(jié)構(gòu)與算法--排序之冒泡、選擇、插入、希爾

我們關(guān)注的主要對(duì)象是重新排列數(shù)組元素的算法，每個(gè)元素都有一個(gè)主鍵，排序算法的目的是將所有元素按照某種方式排列，排列后索引大的元素的主鍵大于等于索引小的元素的主鍵。元素和主鍵在不同的應(yīng)用中可能各不相同，在Java中元素通常都是對(duì)象，而且一般都是可相互比較的對(duì)象——即實(shí)現(xiàn)了Comparale接口。

1、Comparable和compareTo方法

實(shí)現(xiàn)了Comparable接口，因此必須實(shí)現(xiàn)compareTo，一般來說，習(xí)慣于當(dāng)v < w、v = w和v > w時(shí)，v.compareTo(v)分別返回-1、0、1。如果v和w兩者之一是null或者兩者無法比較將會(huì)拋出異常。而且需要滿足下面幾個(gè)條件。

• 自反性。對(duì)于所有的v，有v = v；
• 反對(duì)稱性。對(duì)于所有的v > w都有w < v，且當(dāng)v = w時(shí)有w = v；
• 傳遞性。對(duì)于所有的v、w、x，如果v <= w且w <= x，則v <= x.

2、排序的穩(wěn)定性

如果待排序的序列中存在多個(gè)元素相同，在排序前后它們的相對(duì)位置沒有發(fā)生改變，就稱該排序算法是穩(wěn)定的。舉個(gè)例子，比如待排序序列如下

[3, 5, 4, 2, (5), 6]

最后一個(gè)元素5和第二個(gè)元素5是相同的，特別用括號(hào)標(biāo)明它。此時(shí)5在(5)的前面。如果排序后的序列是

[2, 3, 4, (5), 5, 6]

此時(shí)5在 (5)的后面了，它們的相對(duì)位置發(fā)生了改變，所以該排序算法是不穩(wěn)定的。

如果排序后變成下面的樣子，它們的相對(duì)位置和排序前一樣，則該排序算法是穩(wěn)定的。

[2, 3, 4, 5, (5), 6]

現(xiàn)在來看幾個(gè)簡(jiǎn)單的排序算法。

最容易想到的排序法

有種排序是最容易想到的，當(dāng)然性能肯定不咋滴。數(shù)組中第一個(gè)位置的元素和它后面的每個(gè)元素相比，如果后面的更小，兩個(gè)元素交換，于是更小的元素被換到了數(shù)組第一個(gè)位置，接著用這第一個(gè)位置的元素和后續(xù)元素比較，直到和數(shù)組中每個(gè)元素都比較過一次，期間可能發(fā)生了多次交換，最后數(shù)組第一個(gè)位置肯定是最小元素了；第一個(gè)位置確定了，接下來同樣的辦法確定第二個(gè)位置....直到最后一個(gè)位置確定，排序完成。根據(jù)描述，寫出如下代碼。

package Chap9;

public class SimpleSort {
    public static void sort(Comparable[] a) {
        // 倒數(shù)第二個(gè)元素確定了，那最后一個(gè)元素自然而然就確定了，其實(shí)i < a.length - 1就好
        // 但是i < length也是可以的，進(jìn)入第二層循環(huán)后j = a.length直接跳出循環(huán)
        for (int i = 0; i < a.length; i++) {
            for (int j = i +1; j < a.length; j++) {
                // 如果后面的比當(dāng)前元素小，就交換
                if (less(a[j], a[i])) {
                    swap(a, i, j);
                }
            }
        }
    }

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

    private static void swap(Comparable[] a, int p, int q) {
        Comparable temp = a[p];
        a[p] = a[q];
        a[q] = temp;
    }


    public static boolean isSorted(Comparable[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (less(a[i+1], a[i])) {
                return false;
            }
        }
        return true;
    }

    public static String toString(Comparable[] a) {
        if (a.length == 0) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < a.length; i++) {
            sb.append(a[i]);
            if (i == a.length - 1) {
                return sb.append("]").toString();
            } else {
                sb.append(", ");
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Integer[] a = {9, 1, 5, 8, 3, 7, 4, 6, 2};
        SimpleSort.sort(a);
        System.out.println(SimpleSort.toString(a));
        System.out.println(isSorted(a)); // true
    }

}

算法的軌跡如下，9和1比較，1被換到了數(shù)組第一個(gè)位置。之后1再和后續(xù)元素相比，都沒有1小，因此不交換；然后第二個(gè)位置，5比9小所以交換，5和3比又交換，3和2比又交換，最后2最小確定在數(shù)組第二個(gè)位置......剩下的元素就不一一敘述了。

可以發(fā)現(xiàn)在確定第二小元素的時(shí)候，進(jìn)行了三次交換?？?strong>真正有用的交換是最后把2換過來的那一次，前面的若干次交換都是多余的，其實(shí)直接將最小元素交換過來就可以了?；诖藢?duì)上面的算法的改進(jìn)就是簡(jiǎn)單選擇排序了。

這種算法有缺陷，不僅無效的交換操作很多，而且還會(huì)把本來較小的元素交換到后面去，比如，上例中3本來在數(shù)組中間，經(jīng)過兩輪循環(huán)的排序后，它竟然到了數(shù)組的末端。

簡(jiǎn)單選擇排序

具體來說：選擇數(shù)組中最小的元素，將它與數(shù)組中第一個(gè)元素交換，如果第一個(gè)元素就是最小值，那就和自己交換或者不交換；在剩下的元素中找到最小元素，和數(shù)組中第二個(gè)元素進(jìn)行交換....

交換發(fā)生在每次循環(huán)中選擇出最小元素之后，而不是盲目地看見一個(gè)比當(dāng)前元素小的就馬上交換，因此簡(jiǎn)單選擇排序比起上面的排序算法，元素交換的操作大大減少，性能得到一定提升。

public class SelectSort {
    public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            // min保存目前最小元素的下標(biāo)，剛開始假設(shè)位置i的元素最小，然后和之后每個(gè)元素比較，
            int minIndex = i;
            // 只要后面更小就更新min，因此一輪循環(huán)下來min肯定是最小元素下標(biāo)
            for (int j = i + 1; j < a.length; j++) {
                if (less(a[j], a[minIndex])) {
                    minIndex = j;
                }
            }
            // 如果第一個(gè)元素就是最小值，無需交換
            if (i != minIndex) {
            // 最小元素?fù)Q到位置i
                swap(a,i, minIndex);
            }
        }
    }
}

實(shí)現(xiàn)中用一個(gè)minIndex的int型值記錄在每輪循環(huán)中數(shù)組最小元素的下標(biāo)。一開始假設(shè)數(shù)組中第一個(gè)元素是最小的，然后和后面所有元素比較，如果后面的元素更小，就更新minIndex為后面元素的下標(biāo)（第一種算法直接交換，看出用下標(biāo)記錄最小值的好處了吧），當(dāng)和所有元素比較后，minIndex自然是數(shù)組中最小元素的下標(biāo)，因此將minIndex處的元素和數(shù)組第一個(gè)位置的元素交換（如果第一個(gè)元素的下標(biāo)就是minIndex，無需交換）；接著假設(shè)數(shù)組第二個(gè)位置的元素是最小的，按照相同的方法選擇出剩下元素中的最小者，其下標(biāo)是minIndex，因此將數(shù)組第二個(gè)位置的元素和minIndex處的元素交換，這樣就確定了第一二個(gè)位置...后面都不會(huì)再訪問到這些已經(jīng)有序的元素，之后的元素也是同樣的操作，直到數(shù)組最后一個(gè)位置的元素也確定了，排序也就完成了。

下圖是某字符數(shù)組的選擇排序軌跡，紅色圓圈內(nèi)的是每輪循環(huán)中的最小元素。第一輪選出最小元素A和數(shù)組第一個(gè)位置S交換；第二輪選出最小元素E和數(shù)組第二個(gè)元素O交換....

簡(jiǎn)單選擇排序有如下兩個(gè)特點(diǎn)：

• 運(yùn)行時(shí)間和輸入狀態(tài)無關(guān)，已經(jīng)有序的數(shù)組或者主鍵全部一樣的數(shù)組以及隨機(jī)排列的數(shù)組所用的排序時(shí)間是一樣的！都需要比較N * (N - 1) / 2次
• 數(shù)據(jù)交換的次數(shù)很少，最好情況下交換0次，最壞情況下交換N - 1次。

簡(jiǎn)單選擇排序是不穩(wěn)定的排序算法，舉個(gè)例子[5, 4, 5, 3, 2]，第一輪會(huì)將最下的2與數(shù)組第一個(gè)位置的5交換，兩個(gè)等值的5相對(duì)位置發(fā)生了改變。

冒泡排序

冒泡排序的思路：相鄰元素之間兩兩比較，不斷將較大的元素往后推（或者不斷將較小元素往前推）。以后者為例，從后往前遍歷數(shù)組，數(shù)組中最后一位和倒數(shù)第二位元素比較，較小者被交換到前面；然后用較小者和左邊相鄰的元素比較，繼續(xù)將較小者換到前面，最后最小元素就在數(shù)組的第一個(gè)位置確定下來。第二輪同樣的操作，將剩下元素中的最小元素在數(shù)組的第二個(gè)位置確定下來...如此反復(fù)。

public class BubbleSort {
    public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            // 從最后一個(gè)元素開始，不斷將較小的往前推，被推到數(shù)組左端就是最小元素
            for (int j = a.length - 1; j > i; j--) {
                // 后面的比前面的小就交換
                if (less(a[j], a[j - 1])) {
                    swap(a, j - 1, j);
                }
            }
        }
    }
}

下面的圖演示了前兩個(gè)最小元素是怎么被“冒泡”到數(shù)組的前端的。

冒泡算法的優(yōu)化

試想一種比較特殊的情況，如果待排序的序列基本有序如[2, 1, 3, 4, 5, 6, 7 ,8, 9]，只要在第一輪冒泡中將2和1交換后，其實(shí)整個(gè)序列就已經(jīng)有序了，但是算法依然在進(jìn)行比較，因此這些比較都是無意義的，直接跳出循環(huán)就好。

所以設(shè)置一個(gè)標(biāo)志位isSorted，如果在某輪循環(huán)中沒有發(fā)生元素交換，說明序列已經(jīng)有序，直接break跳出循環(huán)，結(jié)束沒有必要的比較。

public static void sort2(Comparable[] a) {
    boolean isSorted;
    for (int i = 0; i < a.length; i++) {
        // 每輪循環(huán)都先假設(shè)已經(jīng)有序，若之后有元素交換了說明可能還沒有達(dá)到有序，變成false。
        isSorted = true;
        // 從最后一個(gè)元素開始，不斷將較小的往前推，被推到到數(shù)組左端就是最小元素
        for (int j = a.length - 1; j > i; j--) {
        // 后面的比前面的小就交換
            if (less(a[j], a[j - 1])) {
                swap(a, j - 1, j);
                isSorted = false;
            }
        }
        // 如某輪循環(huán)沒有發(fā)生交換，說明已經(jīng)有序了，直接跳出循環(huán)
        if (isSorted) {
            break;
        }
    }
}

冒泡排序的比較和元素交換都發(fā)生在兩個(gè)相鄰元素之間，相鄰的等值元素不會(huì)進(jìn)行交換，就算等值元素不相鄰，在交換后也會(huì)相鄰，依然不會(huì)交換它們的位置，因此冒泡排序是穩(wěn)定排序算法。

插入排序

想象生活中打撲克，從牌堆摸起一張牌，將它插到其他已經(jīng)有序的牌中的合適位置。在數(shù)組中對(duì)應(yīng)著插入操作，為了給插入的元素騰出空間，需要將其他比它大的元素都向右移動(dòng)一位。和選擇排序、冒泡排序一樣，當(dāng)前索引之前的元素已經(jīng)有序，但有區(qū)別。對(duì)于冒泡、選擇排序，當(dāng)前索引之前的元素不僅有序而且最終位置也確定了，在之后的循環(huán)中不會(huì)被訪問到；而對(duì)于選擇排序，當(dāng)前索引之前的元素雖然是有序的，但是最終位置還不確定，后來的元素如果更小將插入其中，每次插入后都使得當(dāng)前數(shù)組是有序的，所以當(dāng)最后一個(gè)元素插入到數(shù)組中合適的位置時(shí)，整個(gè)數(shù)組排序就完成了。

插入排序所需的時(shí)間取決于待排序數(shù)組的初始順序，對(duì)一個(gè)接近有序的數(shù)組進(jìn)行排序比隨機(jī)順序的數(shù)組要快得多。

public class InsertSort {

    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            // 當(dāng)前索引如果比它前一個(gè)元素要大，不用插入，否則需要插入
            if (less(a[i], a[i-1])) {
                // 待插入的元素先保存
                Comparable temp = a[i];
                // 元素右移
                int j;
                for (j = i; j > 0 && less(temp, a[j-1]); j--) {
                    a[j] = a[j -1];
                }
                // 插入
                a[j] = temp;
            }
        }
    }
}

因?yàn)橛玫搅藬?shù)組下標(biāo)i - 1，所以最外層循環(huán)從1開始。當(dāng)前索引i之前的元素已經(jīng)有序，所以如果當(dāng)前索引的元素比它前面一個(gè)元素大（自然就比前面的所有元素都大），則無需進(jìn)行插入操作；否則需要插入，插入之前先將要插入的元素用temp保存下來，然后內(nèi)層for循環(huán)就是右移元素，直到某個(gè)j-1處的元素是小于temp為止，然后temp插入到位置j處。

下圖反映了插入排序的軌跡，被紅色圓圈包住的元素就是被插入到合適位置的元素了，灰色的元素都沒有移動(dòng)，其余黑色的元素都往右移動(dòng)了一格。

從代碼可以推測(cè)插入排序通常比選擇排序比較次數(shù)更少，特別是對(duì)于接近有序的數(shù)組。下圖可以反映這一趨勢(shì)。

用條形圖的高矮表示元素的大小，那些黑色條形圖參與了比較，可以看出插入排序的比較次數(shù)比選擇排序的要少。

插入排序?qū)τ?strong>部分有序的數(shù)組更有優(yōu)勢(shì)，以下是幾種典型的部分有序數(shù)組：

• 數(shù)組中的每個(gè)元素離它們的最終位置都不遠(yuǎn)；
• 一個(gè)有序的大數(shù)組接一個(gè)小數(shù)組；
• 數(shù)組中只有幾個(gè)元素的位置不正確

對(duì)于上述幾種類型的數(shù)組，插入排序通常比其他算法要快些。

插入排序的元素移動(dòng)是依據(jù)插入元素與前面元素的大小來決定的，當(dāng)插入元素遇到和它等值的元素時(shí)就停止移動(dòng)了，因此很好的保持了它們?cè)瓉淼南鄬?duì)位置，因此插入排序是穩(wěn)定的排序算法。

希爾排序

希爾排序基于插入排序。對(duì)于大規(guī)模亂序數(shù)組插入排序很慢（因此更適合于小規(guī)模的部分有序數(shù)組），元素移動(dòng)只是每次移動(dòng)一格，因此如果最小元素在數(shù)組的末端，要將它插入到合適的位置需要N - 1次移動(dòng)。希爾排序正是基于這一點(diǎn)，使得元素可以一次移動(dòng)多格。

具體來說，希爾排序按照增量h將原數(shù)組分成了h個(gè)子數(shù)組（插入排序可以看做是增量為1），然后分別對(duì)這h個(gè)子數(shù)組進(jìn)行插入排序；之后按照一定的關(guān)系減小增量h，再對(duì)h個(gè)子數(shù)組插入排序，每次排序后的數(shù)組越來越接近部分有序，最后保證增量h會(huì)減小到1，對(duì)這個(gè)數(shù)組最后進(jìn)行一次插入排序，整個(gè)數(shù)組排序完成。

增量h和子數(shù)組的關(guān)系如下圖所示

增量為4，因此下標(biāo)為0、4、8、12的組成一個(gè)子數(shù)組，1、5、9、13也組成一個(gè)子數(shù)組。總共4個(gè)，可以看到一個(gè)h有序數(shù)組就是由h個(gè)有序子數(shù)組組成的。

在代碼中只需要將插入排序中的增量1換成h即可。另外為了使得最后的增量能減小到1，使用了一個(gè)1 / 2(3^k - 1)序列，滿足遞推關(guān)系為h = 3h + 1，這是基于數(shù)學(xué)分析上的考慮，在大量實(shí)驗(yàn)中證明該序列可以保證較好的性能。

public class ShellSort {

    public static void sort(Comparable[] a) {
        int h = 1;
        while (h < a.length / 3) {
            h = 3 * h + 1; // 1, 4, 13...
        }
        // 上面的代碼是將初始增量設(shè)置為 小于N/3且滿足序列3h + 1的最大值

        // 最后一次增量h = 1，之后h = 0退出while
        while (h >= 1) {
            // 和插入排序比將i = 1換成了i = h；i還是自增1，表示處理下一個(gè)子數(shù)組（交替處理各個(gè)子數(shù)組）
            for (int i = h; i < a.length; i++) {
                // a[i - 1]換成了a[i - h]
                if (less(a[i], a[i - h])) {
                    // 待插入的元素先保存
                    Comparable temp = a[i];
                    // 元素右移
                    int j;
                    // j > 0（即j >= 1）換成了j >= h;less(temp, a[j - 1])中1換成了h；j--換成了j = j - h
                    for (j = i; j >= h && less(temp, a[j - h]); j = j - h) {
                        // a[j - 1]換成了a[j - h]
                        a[j] = a[j - h];
                    }
                    // 插入
                    a[j] = temp;
                }
            }
            // 縮小增量h，最終肯定能縮小到1
            h = h / 3; // ...13, 4, 1
        }
    }
}

注釋中加入了和插入排序的對(duì)比，的確是將增量1改成了增量h就可以了！第一個(gè)while循環(huán)是設(shè)置初始增量，基于數(shù)學(xué)上的分析，一個(gè)較優(yōu)值是取增量h為小于數(shù)組長(zhǎng)度N / 3且滿足序列1 / 2(3^k - 1)的最大值。在對(duì)所有子數(shù)組都進(jìn)行過插入排序后，縮小增量h。由于縮小的方法和增長(zhǎng)的方法一致，所以最后h一定能被縮小到1，從而保證了最后一次是增量為1的插入排序**。之后h = 1 / 3 = 0會(huì)退出while循環(huán)（注意，這個(gè)除法當(dāng)然是Java中的除法操作）。

我們看上面的實(shí)現(xiàn)是怎么對(duì)每個(gè)子數(shù)組進(jìn)插入排序的，你可能覺得它是在完成一個(gè)子數(shù)組的排序后再對(duì)下一個(gè)子數(shù)組的進(jìn)行插入排序的，按上面h = 4的圖來說就是，先對(duì)下標(biāo)0、4、8、12的子數(shù)組完成排序后，再進(jìn)行下標(biāo)1、5、9、13的子數(shù)組排序，但以這樣的順序處理各個(gè)子數(shù)組，代碼應(yīng)該會(huì)更復(fù)雜。實(shí)際上我們采用了更簡(jiǎn)單的方法，如下

for (int i = h; i < a.length; i++)

結(jié)合上圖，i++表明我們是交替對(duì)每個(gè)子數(shù)組進(jìn)行插入排序的，比如開始i = h = 4，表示對(duì)下標(biāo)0、4、8、12的子數(shù)組LMPT進(jìn)行插入排序，然后i自增后等于5，轉(zhuǎn)而對(duì)下標(biāo)1、5、9、13的子數(shù)組EHSS進(jìn)行插入排序...當(dāng)i自增到8時(shí)，又回來對(duì)下標(biāo)0、4、8、12的子數(shù)組LMPT排序，這樣最后也達(dá)到了對(duì)每個(gè)子數(shù)組進(jìn)行插入排序的目的。硬要打個(gè)比方的話，h個(gè)子數(shù)組可以看成h個(gè)線程，單核處理器并發(fā)處理這h個(gè)任務(wù)，即在這h個(gè)線程中切換（因此會(huì)中斷當(dāng)前線程去處理其他線程），交替執(zhí)行h個(gè)線程。

看希爾排序的軌跡圖，被紅色圓圈包住的元素是當(dāng)前索引元素，它要么原地不動(dòng)要么被插入到合適的位置。黑色元素是移動(dòng)過的，灰色元素則沒有移動(dòng)。

通常，希爾排序比選擇排序和插入排序都要快，并且數(shù)組規(guī)模越大，優(yōu)勢(shì)體現(xiàn)得越明顯。另外，增量h的序列如何選擇才能達(dá)到最好的性能，到現(xiàn)在依然是個(gè)數(shù)學(xué)難題。因此無需糾結(jié)為什么非得取1/2 (3^k - 1)這樣的序列，只要記住采用這個(gè)序列可以取得不錯(cuò)的性能就好了。

希爾排序由于增量一般較大，元素的移動(dòng)跨度很大，是跳躍性的，而且各個(gè)子數(shù)組的元素移動(dòng)交替進(jìn)行，因此很有可能就不能保證等值元素的相對(duì)位置。因此希爾排序不是穩(wěn)定排序算法。

by @sunhaiyu

2017.10.27