排序是科學(xué)計(jì)算和數(shù)據(jù)處理必不可少的一個(gè)環(huán)節(jié)瓦呼，今天起我們就來聊聊排序。

本文將介紹三個(gè)初級(jí)排序算法

1. 冒泡排序
2. 選擇排序
3. 插入排序

先來看下圖這樣的一組初始數(shù)據(jù)测暗，每一個(gè)矩形的高度都與其下方的數(shù)字成比例央串，數(shù)值越大則矩形的高度就越高。

初始數(shù)據(jù)

假設(shè)有如下兩個(gè)問題碗啄，我們?cè)撊绾吻蠼狻?/p>

• 找出最(小/大)值
• 找出第k(小/大)的值

顯然质和，在亂序的數(shù)組中這兩個(gè)問題都不太容易求解，但如果數(shù)據(jù)是有序的就會(huì)容易很多稚字。

冒泡排序

冒泡排序是最容易想到的排序算法饲宿。以對(duì)N個(gè)元素的數(shù)組進(jìn)行升序排序?yàn)槔浠舅悸啡缦拢?/p>

1. 從數(shù)組內(nèi)的前兩個(gè)元素開始胆描，將這兩個(gè)元素進(jìn)行比較瘫想，如果前一個(gè)元素大于后一個(gè)元素，則交換兩者的位置
2. 接著取數(shù)組中的第2-3個(gè)元素進(jìn)行比較昌讲，若第2個(gè)元素大于第3個(gè)元素殿托，則交換兩者的位置
3. 循環(huán)往復(fù)，直到數(shù)組中的最后兩個(gè)元素剧蚣，此時(shí)支竹，若第N-1個(gè)元素大于第N個(gè)元素，則交換它們的位置鸠按。經(jīng)過一輪的比較與交換礼搁，我們已經(jīng)得到了數(shù)組中最大的元素，并將其安置在了數(shù)組的第N位目尖。
4. 經(jīng)過前三個(gè)步驟馒吴，我們將數(shù)組中最大的元素放到了第N位，下邊只用排序數(shù)組中的前N-1個(gè)元素即可。此時(shí)我們將N的值減1饮戳，并判斷新N的值豪治，若新N>0，則循環(huán)1-3步驟扯罐；若新N=0负拟，則代表我們已經(jīng)完成了排序。

冒泡排序的過程(剪輯版)如下圖所示歹河，你也可以點(diǎn)擊這里查看完整的冒泡排序過程掩浙。

冒泡排序剪輯版

我們知道，水杯中出現(xiàn)氣泡時(shí)秸歧，越大的氣泡浮力越大厨姚，上升速度也就越快，最先到達(dá)水面键菱，冒牌排序中每輪遴選較大元素放置末尾的行為與水中氣泡上升的現(xiàn)象十分相似谬墙，因此得名冒泡排序。

冒泡排序代碼

public static void bubbleSort(Integer arr[]) {
        int compareCount = 0;//比較次數(shù)
        int swapCount = 0;//交換次數(shù)
        long before = System.currentTimeMillis();
        for (int i = 0; i < arr.length; i++) { //外層循環(huán)经备，與數(shù)組元素個(gè)數(shù)相關(guān)
            for (int j = 1; j < arr.length - i; j++) { //內(nèi)層循環(huán)拭抬，只需在前 n-1 個(gè)元素內(nèi)進(jìn)行相鄰比較
                compareCount++;
                if (arr[j - 1] > arr[j]) {
                    swapCount++;
                    swap(arr, j - 1, j);
                }
            }
        }
        long after = System.currentTimeMillis();
        System.out.println("冒泡排序耗時(shí)："+(after-before)+"ms,"+"比較次數(shù)："+compareCount+",交換次數(shù)："+swapCount);
}

使用上述代碼對(duì)以下兩組數(shù)據(jù)排序時(shí)，其比較次數(shù)一致弄喘，僅交換次數(shù)不同玖喘。但顯而易見的是甩牺，第二組本身就是有序的蘑志，也就是說上邊的代碼中，存在冗余比較贬派。
3 5 1 6 10 9 11
1 3 5 7 9 10 11

原有數(shù)組 3 5 1 6 10 9 11 
冒泡排序耗時(shí)：0ms 比較次數(shù)：21,交換次數(shù)：3
排序后 1 3 5 6 9 10 11 
---
原有數(shù)組 1 3 5 6 9 10 11 
冒泡排序耗時(shí)：0ms 比較次數(shù)：21,交換次數(shù)：0
排序后 1 3 5 6 9 10 11 

針對(duì)這樣的問題急但，我們可以采用如下思路對(duì)冒泡排序的代碼進(jìn)行優(yōu)化。

• 當(dāng)某輪內(nèi)循環(huán)沒有發(fā)生元素交換時(shí)搞乏，表明數(shù)組已然有序波桩，無需再進(jìn)行后續(xù)的比較，此時(shí)可直接中止循環(huán)

冒泡排序優(yōu)化代碼

public static void bubbleSortOpt(Integer arr[]) {
        int compareCount = 0;//比較次數(shù)
        int swapCount = 0;//交換次數(shù)
        long before = System.currentTimeMillis();
        for (int i = 0; i < arr.length; i++) { //外層循環(huán)请敦，與數(shù)組元素個(gè)數(shù)相關(guān)
            boolean isSwap = false; //交換標(biāo)記镐躲，每輪外循環(huán)開始時(shí)，將其置位false
            for (int j = 1; j < arr.length - i; j++) { //內(nèi)層循環(huán)侍筛，只需在前 n-1 個(gè)元素內(nèi)進(jìn)行相鄰比較
                compareCount++;
                if (arr[j - 1] > arr[j]) {
                    isSwap = true;//若內(nèi)循環(huán)內(nèi)發(fā)生交換萤皂，則將交換標(biāo)志置位true
                    swapCount++;
                    swap(arr, j - 1, j);
                }
            }
            if (!isSwap) {//判斷循環(huán)標(biāo)記，若未發(fā)生交換匣椰，則跳出循環(huán)
                break;
            }
        }
        long after = System.currentTimeMillis();
        System.out.println("冒泡排序耗時(shí)："+(after-before)+"ms,"+"比較次數(shù)："+compareCount+",交換次數(shù)："+swapCount);
}

原有數(shù)組 3 5 1 6 10 9 11 
冒泡排序耗時(shí)：0ms 比較次數(shù)：15,交換次數(shù)：3
排序后 1 3 5 6 9 10 11 
---
原有數(shù)組 1 3 5 6 9 10 11 
冒泡排序耗時(shí)：0ms 比較次數(shù)：5,交換次數(shù)：0
排序后 

選擇排序

選擇排序的思路同樣很簡單裆熙，以對(duì)含有N個(gè)元素的數(shù)組進(jìn)行升序排序?yàn)槔洳襟E如下所示：

1. 假設(shè)首元素是最小的，并記錄其索引值為minIndex入录，遍歷數(shù)組蛤奥，分別與其比較，若數(shù)組中第i個(gè)元素的數(shù)值小于第minIndex個(gè)元素的數(shù)組僚稿，則將i賦值與minIndex凡桥。
2. 遍歷結(jié)束后，我們得到了數(shù)值最小的元素的索引值贫奠，將其與首元素進(jìn)行交換唬血，交換后的首元素即為數(shù)組中數(shù)值最小的元素。
3. 經(jīng)過前邊兩個(gè)步驟唤崭，此時(shí)數(shù)組中可分為首元素和與第2個(gè)元素開始到末尾的N-1個(gè)元素拷恨。判斷N-1，若N-1>0,則將第二個(gè)元素視作首元素谢肾，重復(fù)步驟1-2腕侄；若N-1=0，則表明數(shù)組已然有序芦疏，中止循環(huán)冕杠。

選擇排序的過程(剪輯版)如下圖所示，你也可以點(diǎn)擊這里查看完整的選擇排序過程酸茴。

選擇排序剪輯版

根據(jù)這個(gè)思路分预，不難寫出其代碼

public static void selectSort(Integer arr[]) {
    int compareCount = 0;
    int swapCount = 0;
    long before = System.currentTimeMillis();
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i+1; j < arr.length - i; j++) {
            compareCount++;
            if (arr[j]<arr[minIndex]){
                minIndex = j;
            }
        }
        if (minIndex!=i){
            swapCount++;
            swap(arr,i,minIndex);
        }
    }
    long after = System.currentTimeMillis();
    System.out.println("選擇排序耗時(shí)：" + (after - before) + "ms," + "比較次數(shù)：" + compareCount + ",交換次數(shù)：" + swapCount);
}

插入排序

插入排序是我們需要了解是最后一個(gè)簡單排序算法，其思路與我們打撲克牌時(shí)的起牌手法相似薪捍。

1. 假設(shè)我們用左手持牌笼痹，右手起牌，每次起牌完成后酪穿，左手中的手牌均為有序的凳干。
2. 開始起牌時(shí)，左手手牌為空被济，此時(shí)從牌堆頂取一張牌救赐，直接放入左手
3. 在起后邊的牌時(shí)，我們拿右手中剛起到的那張新牌只磷，與左手中的所有手牌進(jìn)行比較经磅，并放入到合適的位置。
   • 按從大到小的順序分別拿左手中的手牌與新牌進(jìn)行比較
   • 在從大到小的比較過程中钮追，若左手當(dāng)前手牌比新牌大预厌，則取交換著兩張牌的位置，并以左手當(dāng)前手牌作為新牌畏陕，與剩余的左手手牌進(jìn)行比較
   • 若左手的當(dāng)前手牌小于等于新牌配乓，則將新牌插入到當(dāng)前手牌之后，并將此后的手牌依次向后挪動(dòng)

使用插入排序來排序手中撲克牌

需要注意的是，在插入排序時(shí)犹芹，我們將數(shù)組分為了兩部分崎页，一部分是"左手"中的有序子數(shù)組，另一部分是"牌堆"中無序的子數(shù)組腰埂。初始時(shí)飒焦，我們將數(shù)組中的第一個(gè)元素視作已排序子數(shù)組，并將第二個(gè)元素至最后一個(gè)元素視作無序子數(shù)組屿笼。我們每次從無序子數(shù)組中取出首元素p牺荠，從后往前分別與有序子數(shù)組中的元素q進(jìn)行比較，若p小于q的數(shù)值驴一，則將p與q交換休雌，并繼續(xù)用p與子數(shù)組中剩下的元素進(jìn)行比較和交換，直到p不小q時(shí)肝断，完成此輪插入杈曲，此時(shí)有序子數(shù)組的長度+1，無序子數(shù)組的長度-1胸懈。

插入排序的過程(剪輯版)如下圖所示担扑，你也可以點(diǎn)擊這里查看完整的插入排序過程。

插入排序剪輯版

插入排序代碼

public static void insertSort(Integer arr[]) {
    int compareCount = 0;
    int swapCount = 0;
    long before = System.currentTimeMillis();
    //外層循環(huán)趣钱，i表示有序子數(shù)組與無序子數(shù)組間的界限涌献，i之前的元素為有序的，i及i之后的元素為無序的
    for (int i = 1; i < arr.length; i++) {
        //內(nèi)層循環(huán)首有，將i到0之間的元素兩兩比較燕垃，若i<i-1，則交換兩者的位置
        for (int j = i; j > 0; j--) {
            compareCount++;
            if (arr[j] < arr[j - 1]) {
                swapCount++;
                swap(arr, j, j - 1);//兩兩交換
            }
        }
    }
    long after = System.currentTimeMillis();
    System.out.println("選擇排序耗時(shí)：" + (after - before) + "ms," + "比較次數(shù)：" + compareCount + ",交換次數(shù)：" + swapCount);
}

我們知道頻繁的兩兩交換也是有性能損耗的绞灼，對(duì)于插入排序利术，我們通過如下的思路進(jìn)一步優(yōu)化：

• 在新牌插入過程中呈野，先在左手手牌的后方將新牌的空間給預(yù)留出來低矮，從大到小，依次比較當(dāng)前手牌與新牌被冒。
• 若當(dāng)前手牌大于新牌军掂，則將當(dāng)前手牌向后挪動(dòng)一下（注意，此時(shí)并不拿新牌與當(dāng)前手牌交換）昨悼，將左手手牌后方的空間擠壓到當(dāng)前手牌的前方
• 若當(dāng)前手牌小于新牌蝗锥，則將新牌放到這里

有了這個(gè)思路，我們便可以將此前頻繁的兩兩交換率触，換為單個(gè)元素后移终议，從而減少了一定的性能開銷。

優(yōu)化插入排序

public static void insertSortOpt(Integer arr[]) {
    long before = System.currentTimeMillis();
    for (int i = 1; i < arr.length; i++) {
        //使用臨時(shí)變量保存新牌
        int temp  =arr[i];
        int j = i;
        //從大到小，依次取左手中的牌與temp進(jìn)行比較穴张，若左手當(dāng)前手牌大于temp细燎，則將當(dāng)前手牌后移一位
        while(j>0 && temp<arr[j-1]){
            arr[j] = arr[j -1];
            j--;//繼續(xù)下一張較大的牌
        }
        arr[j] = temp;//最終將temp插入左手手牌中合適的位置
    }
    long after = System.currentTimeMillis();
    System.out.println("插入排序耗時(shí)：" + (after - before) + "ms");
}

在規(guī)模較大的問題中，這種方式帶來的好處非常明顯皂甘。

10W條數(shù)據(jù)
   插入排序耗時(shí)：12296ms
優(yōu)化插入排序耗時(shí)：2742ms

測(cè)試

經(jīng)過測(cè)試玻驻，可以看到冒泡排序的耗時(shí)最多。插入排序在規(guī)模較小的數(shù)組中明顯快于選擇排序偿枕，在規(guī)模較大的數(shù)組中與選擇排序相當(dāng)璧瞬，從此也證明了我們此前算法分析環(huán)節(jié)中得到的結(jié)論。

小結(jié)

本文介紹了三個(gè)基礎(chǔ)的排序算法渐夸，在這里先對(duì)它們做一個(gè)總結(jié)嗤锉，希望能讓大家對(duì)排序及算法效率有一個(gè)直觀的感受。

選擇排序和插入排序的異同點(diǎn)：

1. 插入排序與選擇排序一樣伞梯，當(dāng)前索引左邊的所有元素都是有序的玫氢。但在選擇排序中，當(dāng)前索引左邊的元素位置是固定的(與最終位置一致)谜诫；而插入排序當(dāng)前索引左邊的元素位置未必固定漾峡，為了給后邊更小的元素騰出空間，它們可能會(huì)被移動(dòng)喻旷，當(dāng)索引到達(dá)數(shù)組的右端時(shí)生逸，排序完成。
2. 選擇排序的運(yùn)行時(shí)間與原始數(shù)據(jù)無關(guān)（比較次數(shù)恒定）且预；插入排序的運(yùn)行時(shí)間與原始數(shù)據(jù)強(qiáng)相關(guān)槽袄，當(dāng)對(duì)一個(gè)有序或接近有序的數(shù)組排序時(shí)，會(huì)比隨機(jī)順序或逆序的數(shù)組快很多锋谐。

參考書目

《算法導(dǎo)論》 - CLRS
《算法》第四版 - Sedgewick
《數(shù)據(jù)結(jié)構(gòu)與算法分析》 - Weiss

參考博客

關(guān)于插入排序和選擇排序的比較
Java排序算法分析與實(shí)現(xiàn)