1 冒泡排序

每次循環(huán)都比較前后兩個(gè)元素的大小，如果前者大于后者力惯，則將兩者進(jìn)行交換碗誉。這樣做會(huì)將每次循環(huán)中最大的元素替換到末尾，逐漸形成有序集合父晶。將每次循環(huán)中的最大元素逐漸由隊(duì)首轉(zhuǎn)移到隊(duì)尾的過(guò)程形似“冒泡”過(guò)程哮缺，故因此得名。

O(n)

的由來(lái)）。

public int[] bubbleSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    for (int i = 0; i < array.length - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                //這里交換兩個(gè)數(shù)據(jù)并沒(méi)有使用中間變量俺猿，而是使用異或的方式來(lái)實(shí)現(xiàn)
                array[j] = array[j] ^ array[j + 1];
                array[j + 1] = array[j] ^ array[j + 1];
                array[j] = array[j] ^ array[j + 1];

                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
    return array;
}

2 選擇排序

每次循環(huán)都會(huì)找出當(dāng)前循環(huán)中最小的元素茎匠，然后和此次循環(huán)中的隊(duì)首元素進(jìn)行交換。

public int[] selectSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex > i) {
            array[i] = array[i] ^ array[minIndex];
            array[minIndex] = array[i] ^ array[minIndex];
            array[i] = array[i] ^ array[minIndex];
        }
    }
    return array;
}

3 插入排序

插入排序的精髓在于每次都會(huì)在先前排好序的子集合中插入下一個(gè)待排序的元素押袍，每次都會(huì)判斷待排序元素的上一個(gè)元素是否大于待排序元素，如果大于凯肋，則將元素右移谊惭，然后判斷再上一個(gè)元素與待排序元素...以此類推。直到小于等于比較元素時(shí)就是找到了該元素的插入位置侮东。這里的等于條件放在哪里很重要圈盔，因?yàn)樗菦Q定插入排序穩(wěn)定與否的關(guān)鍵。

public int[] insertSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    for (int i = 1; i < array.length; i++) {
        int temp = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > temp) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }
    return array;
}

4 希爾排序

希爾排序可以認(rèn)為是插入排序的改進(jìn)版本悄雅。首先按照初始增量來(lái)將數(shù)組分成多個(gè)組驱敲，每個(gè)組內(nèi)部使用插入排序。然后縮小增量來(lái)重新分組宽闲，組內(nèi)再次使用插入排序...重復(fù)以上步驟众眨，直到增量變?yōu)?的時(shí)候，這個(gè)時(shí)候整個(gè)數(shù)組就是一個(gè)分組容诬，進(jìn)行最后一次完整的插入排序即可結(jié)束。

在排序開始時(shí)的增量較大，分組也會(huì)較多街氢，但是每個(gè)分組中的數(shù)據(jù)較少漫雷，所以插入排序會(huì)很快。隨著每一輪排序的進(jìn)行，增量和分組數(shù)會(huì)逐漸變小纽什，每個(gè)分組中的數(shù)據(jù)會(huì)逐漸變多措嵌。但因?yàn)橹耙呀?jīng)經(jīng)過(guò)了多輪的分組排序，而此時(shí)的數(shù)組會(huì)趨近于一個(gè)有序的狀態(tài)芦缰，所以這個(gè)時(shí)候的排序也是很快的企巢。而對(duì)于數(shù)據(jù)較多且趨向于無(wú)序的數(shù)據(jù)來(lái)說(shuō)，如果只是使用插入排序的話效率就并不高饺藤。所以總體來(lái)說(shuō)包斑，希爾排序的執(zhí)行效率是要比插入排序高的。

希爾排序執(zhí)行示意圖：

img

具體的實(shí)現(xiàn)代碼如下：

public int[] shellSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    int gap = array.length >>> 1;
    while (gap > 0) {
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];
            int j = i - gap;
            while (j >= 0 && array[j] > temp) {
                array[j + gap] = array[j];
                j = j - gap;
            }
            array[j + gap] = temp;
        }
        gap >>>= 1;
    }
    return array;
}

5 堆排序

堆排序的過(guò)程是首先構(gòu)建一個(gè)大頂堆涕俗，大頂堆首先是一棵完全二叉樹罗丰，其次它保證堆中某個(gè)節(jié)點(diǎn)的值總是不大于其父節(jié)點(diǎn)的值。

因?yàn)榇箜敹阎械淖畲笤乜隙ㄊ歉?jié)點(diǎn)再姑，所以每次取出根節(jié)點(diǎn)即為當(dāng)前大頂堆中的最大元素萌抵，取出后剩下的節(jié)點(diǎn)再重新構(gòu)建大頂堆，再取出根節(jié)點(diǎn)元镀，再重新構(gòu)建…重復(fù)這個(gè)過(guò)程绍填，直到數(shù)據(jù)都被取出，最后取出的結(jié)果即為排好序的結(jié)果栖疑。

public class MaxHeap {

    /**
     * 排序數(shù)組
     */
    private int[] nodeArray;
    /**
     * 數(shù)組的真實(shí)大小
     */
    private int size;

    private int parent(int index) {
        return (index - 1) >>> 1;
    }

    private int leftChild(int index) {
        return (index << 1) + 1;
    }

    private int rightChild(int index) {
        return (index << 1) + 2;
    }

    private void swap(int i, int j) {
        nodeArray[i] = nodeArray[i] ^ nodeArray[j];
        nodeArray[j] = nodeArray[i] ^ nodeArray[j];
        nodeArray[i] = nodeArray[i] ^ nodeArray[j];
    }

    private void siftUp(int index) {
        //如果index處節(jié)點(diǎn)的值大于其父節(jié)點(diǎn)的值讨永，則交換兩個(gè)節(jié)點(diǎn)值，同時(shí)將index指向其父節(jié)點(diǎn)遇革，繼續(xù)向上循環(huán)判斷
        while (index > 0 && nodeArray[index] > nodeArray[parent(index)]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    private void siftDown(int index) {
        //左孩子的索引比size小卿闹，意味著索引index處的節(jié)點(diǎn)有左孩子，證明此時(shí)index節(jié)點(diǎn)不是葉子節(jié)點(diǎn)
        while (leftChild(index) < size) {
            //maxIndex記錄的是index節(jié)點(diǎn)左右孩子中最大值的索引
            int maxIndex = leftChild(index);
            //右孩子的索引小于size意味著index節(jié)點(diǎn)含有右孩子
            if (rightChild(index) < size && nodeArray[rightChild(index)] > nodeArray[maxIndex]) {
                maxIndex = rightChild(index);
            }
            //如果index節(jié)點(diǎn)值比左右孩子值都大萝快，則終止循環(huán)
            if (nodeArray[index] >= nodeArray[maxIndex]) {
                break;
            }
            //否則進(jìn)行交換锻霎，將index指向其交換的左孩子或右孩子，繼續(xù)向下循環(huán)揪漩，直到葉子節(jié)點(diǎn)
            swap(index, maxIndex);
            index = maxIndex;
        }
    }

    private void add(int value) {
        nodeArray[size] = value;
        size++;
        //構(gòu)建大頂堆
        siftUp(size - 1);
    }

    private void extractMax() {
        //將堆頂元素和最后一個(gè)元素進(jìn)行交換
        swap(0, size - 1);
        //此時(shí)并沒(méi)有刪除元素旋恼，而只是將size-1，剩下的元素重新構(gòu)建成大頂堆
        size--;
        //重新構(gòu)建大頂堆
        siftDown(0);
    }

    public int[] heapSort(int[] array) {
        if (array == null || array.length < 2) {
            return array;
        }
        nodeArray = new int[array.length];
        for (int value : array) {
            add(value);
        }
        for (int i = 0; i < array.length; i++) {
            extractMax();
        }
        return nodeArray;
    }
}

上面的經(jīng)典實(shí)現(xiàn)中奄容，如果需要變動(dòng)節(jié)點(diǎn)時(shí)冰更，都會(huì)來(lái)一次父子節(jié)點(diǎn)的互相交換操作（包括刪除節(jié)點(diǎn)時(shí)首先做的要?jiǎng)h除節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)之間的交換操作也是如此）。如果仔細(xì)思考的話嫩海，就會(huì)發(fā)現(xiàn)這其實(shí)是多余的冬殃。在需要交換節(jié)點(diǎn)的時(shí)候，只需要siftUp操作時(shí)的父節(jié)點(diǎn)或siftDown時(shí)的孩子節(jié)點(diǎn)重新移到當(dāng)前需要比較的節(jié)點(diǎn)位置上叁怪，而比較節(jié)點(diǎn)是不需要移動(dòng)到它們的位置上的审葬。此時(shí)直接進(jìn)入到下一次的判斷中，重復(fù)siftUp或siftDown過(guò)程，直到最后找到了比較節(jié)點(diǎn)的插入位置后涣觉，才會(huì)將其插入進(jìn)去痴荐。這樣做的好處是可以省去一半的節(jié)點(diǎn)賦值的操作，提高了執(zhí)行的效率官册。同時(shí)這也就意味著生兆，需要將要比較的節(jié)點(diǎn)作為參數(shù)保存起來(lái)，而在ScheduledThreadPoolExecutor源碼中也正是這么實(shí)現(xiàn)的（《較真兒學(xué)源碼系列-ScheduledThreadPoolExecutor（逐行源碼帶你分析作者思路）》）膝宁。

6 歸并排序

歸并排序使用的是分治的思想鸦难，首先將數(shù)組不斷拆分，直到最后拆分成兩個(gè)元素的子數(shù)組员淫，將這兩個(gè)元素進(jìn)行排序合并合蔽，再向上遞歸。不斷重復(fù)這個(gè)拆分和合并的遞歸過(guò)程介返，最后得到的就是排好序的結(jié)果拴事。

合并的過(guò)程是將兩個(gè)指針指向兩個(gè)子數(shù)組的首位元素，兩個(gè)元素進(jìn)行比較圣蝎，較小的插入到一個(gè)temp數(shù)組中刃宵，同時(shí)將該數(shù)組的指針右移一位，繼續(xù)比較該數(shù)組的第二個(gè)元素和另一個(gè)元素…重復(fù)這個(gè)過(guò)程徘公。這樣temp數(shù)組保存的便是這兩個(gè)子數(shù)組排好序的結(jié)果牲证。最后將temp數(shù)組復(fù)制回原數(shù)組的位置處即可。

public int[] mergeSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    return mergeSort(array, 0, array.length - 1);
}

private int[] mergeSort(int[] array, int left, int right) {
    if (left < right) {
        //這里沒(méi)有選擇“(left + right) / 2”的方式关面，是為了防止數(shù)據(jù)溢出
        int mid = left + ((right - left) >>> 1);
        // 拆分子數(shù)組
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        // 對(duì)子數(shù)組進(jìn)行合并
        merge(array, left, mid, right);
    }
    return array;
}

private void merge(int[] array, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    // p1和p2為需要對(duì)比的兩個(gè)數(shù)組的指針从隆，k為存放temp數(shù)組的指針
    int p1 = left, p2 = mid + 1, k = 0;
    while (p1 <= mid && p2 <= right) {
        if (array[p1] <= array[p2]) {
            temp[k++] = array[p1++];
        } else {
            temp[k++] = array[p2++];
        }
    }
    // 把剩余的數(shù)組直接放到temp數(shù)組中
    while (p1 <= mid) {
        temp[k++] = array[p1++];
    }
    while (p2 <= right) {
        temp[k++] = array[p2++];
    }
    // 復(fù)制回原數(shù)組
    for (int i = 0; i < temp.length; i++) {
        array[i + left] = temp[i];
    }
}

7 快速排序

快速排序的核心是要有一個(gè)基準(zhǔn)數(shù)據(jù)temp，一般取數(shù)組的第一個(gè)位置元素缭裆。然后需要有兩個(gè)指針left和right，分別指向數(shù)組的第一個(gè)和最后一個(gè)元素寿烟。

首先從right開始澈驼，比較right位置元素和基準(zhǔn)數(shù)據(jù)。如果大于等于筛武，則將right指針左移缝其，比較下一位元素；如果小于徘六，就將right指針處數(shù)據(jù)賦給left指針處（此時(shí)left指針處數(shù)據(jù)已保存進(jìn)temp中）内边，left指針+1，之后開始比較left指針處數(shù)據(jù)待锈。

拿left位置元素和基準(zhǔn)數(shù)據(jù)進(jìn)行比較漠其。如果小于等于，則將left指針右移，比較下一位元素和屎；而如果大于就將left指針處數(shù)據(jù)賦給right指針處拴驮，right指針-1，之后開始比較right指針處數(shù)據(jù)…重復(fù)這個(gè)過(guò)程柴信。

直到left和right指針相等時(shí)套啤，說(shuō)明這一次比較過(guò)程完成。此時(shí)將先前存放進(jìn)temp中的基準(zhǔn)數(shù)據(jù)賦值給當(dāng)前l(fā)eft和right指針共同指向的位置處随常，即可完成這一次排序操作潜沦。

之后遞歸排序基礎(chǔ)數(shù)據(jù)的左半部分和右半部分，遞歸的過(guò)程和上面講述的過(guò)程是一樣的绪氛，只不過(guò)數(shù)組范圍不再是原來(lái)的全部數(shù)組了唆鸡，而是現(xiàn)在的左半部分或右半部分。當(dāng)全部的遞歸過(guò)程結(jié)束后钞楼，最終結(jié)果即為排好序的結(jié)果喇闸。

快速排序執(zhí)行示意圖：

img

O(n^2)

O(nlog_2n)

O(n^2)

還有一個(gè)優(yōu)化的方法是：像快速排序、歸并排序這樣的復(fù)雜排序方法在數(shù)據(jù)量大的情況下是比選擇排序昙读、冒泡排序和插入排序的效率要高的召调，但是在數(shù)據(jù)量小的情況下反而要更慢。所以我們可以選定一個(gè)閾值蛮浑，這里選擇為47（和源碼中使用的一樣）唠叛。當(dāng)需要排序的數(shù)據(jù)量小于47時(shí)走插入排序，大于47則走快速排序沮稚。

private static final int THRESHOLD = 47;

public int[] quickSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    return quickSort(array, 0, array.length - 1);
}

private int[] quickSort(int[] array, int start, int end) {
    // 如果當(dāng)前需要排序的數(shù)據(jù)量小于等于THRESHOLD則走插入排序的邏輯艺沼，否則繼續(xù)走快速排序
    if (end - start <= THRESHOLD - 1) {
        return insertSort(array);
    }

    // left和right指針?lè)謩e指向array的第一個(gè)和最后一個(gè)元素
    int left = start, right = end;

    /*
    取最左邊、最右邊和最中間的三個(gè)元素的中間值作為基準(zhǔn)數(shù)據(jù)蕴掏，以此來(lái)盡量避免每次都取第一個(gè)值作為基準(zhǔn)數(shù)據(jù)障般、
    時(shí)間復(fù)雜度可能退化為O(n^2)的情況出現(xiàn)
     */
    int middleOf3Indexs = middleOf3Indexs(array, start, end);
    if (middleOf3Indexs != start) {
        swap(array, middleOf3Indexs, start);
    }

    // temp存放的是array中需要比較的基準(zhǔn)數(shù)據(jù)
    int temp = array[start];

    while (left < right) {
        // 首先從right指針開始比較调鲸，如果right指針位置處數(shù)據(jù)大于temp，則將right指針左移
        while (left < right && array[right] >= temp) {
            right--;
        }
        // 如果找到一個(gè)right指針位置處數(shù)據(jù)小于temp剩拢，則將right指針處數(shù)據(jù)賦給left指針處
        if (left < right) {
            array[left] = array[right];
            left++;
        }
        // 然后從left指針開始比較线得，如果left指針位置處數(shù)據(jù)小于temp，則將left指針右移
        while (left < right && array[left] <= temp) {
            left++;
        }
        // 如果找到一個(gè)left指針位置處數(shù)據(jù)大于temp徐伐，則將left指針處數(shù)據(jù)賦給right指針處
        if (left < right) {
            array[right] = array[left];
            right--;
        }
    }
    // 當(dāng)left和right指針相等時(shí)贯钩，此時(shí)循環(huán)跳出，將之前存放的基準(zhǔn)數(shù)據(jù)賦給當(dāng)前兩個(gè)指針共同指向的數(shù)據(jù)處
    array[left] = temp;
    // 一次替換后办素，遞歸交換基準(zhǔn)數(shù)據(jù)左邊的數(shù)據(jù)
    if (start < left - 1) {
        array = quickSort(array, start, left - 1);
    }
    // 之后遞歸交換基準(zhǔn)數(shù)據(jù)右邊的數(shù)據(jù)
    if (right + 1 < end) {
        array = quickSort(array, right + 1, end);
    }
    return array;
}

private int middleOf3Indexs(int[] array, int start, int end) {
    int mid = start + ((end - start) >>> 1);
    if (array[start] < array[mid]) {
        if (array[mid] < array[end]) {
            return mid;
        } else {
            return array[start] < array[end] ? end : start;
        }
    } else {
        if (array[mid] > array[end]) {
            return mid;
        } else {
            return array[start] < array[end] ? start : end;
        }
    }
}

private void swap(int[] array, int i, int j) {
    array[i] = array[i] ^ array[j];
    array[j] = array[i] ^ array[j];
    array[i] = array[i] ^ array[j];
}

8 計(jì)數(shù)排序

以上的七種排序算法都是比較排序角雷，也就是基于元素之間的比較來(lái)進(jìn)行排序的。而下面將要介紹的三種排序算法是非比較排序性穿，首先是計(jì)數(shù)排序勺三。

計(jì)數(shù)排序會(huì)創(chuàng)建一個(gè)臨時(shí)的數(shù)組，里面存放每個(gè)數(shù)出現(xiàn)的次數(shù)需曾。比如一個(gè)待排序的數(shù)組是[3, 3, 5, 2, 7, 4, 2]吗坚，那么這個(gè)臨時(shí)數(shù)組中記錄的數(shù)據(jù)就是[2, 2, 1, 1, 0, 1]。表示2出現(xiàn)了兩次呆万、3出現(xiàn)了兩次商源、4出現(xiàn)了一次、5出現(xiàn)了一次谋减、6出現(xiàn)了零次牡彻、7出現(xiàn)了一次。那么最后只需要遍歷這個(gè)臨時(shí)數(shù)組中的計(jì)數(shù)值就可以了出爹。

public int[] countingSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    //記錄待排序數(shù)組中的最大值
    int max = array[0];
    //記錄待排序數(shù)組中的最小值
    int min = array[0];
    for (int i : array) {
        if (i > max) {
            max = i;
        }
        if (i < min) {
            min = i;
        }
    }
    int[] temp = new int[max - min + 1];
    //記錄每個(gè)數(shù)出現(xiàn)的次數(shù)
    for (int i : array) {
        temp[i - min]++;
    }
    int index = 0;
    for (int i = 0; i < temp.length; i++) {
        //當(dāng)輸出一個(gè)數(shù)之后庄吼，當(dāng)前位置的計(jì)數(shù)就減一，直到減到0為止
        while (temp[i]-- > 0) {
            array[index++] = i + min;
        }
    }
    return array;
}

從上面的實(shí)現(xiàn)中可以看到严就，計(jì)數(shù)排序僅適合數(shù)據(jù)跨度不大的場(chǎng)景总寻。如果最大值和最小值之間的差距比較大，生成的臨時(shí)數(shù)組就會(huì)比較長(zhǎng)梢为。比如說(shuō)一個(gè)數(shù)組是[2, 1, 3, 1000]废菱，最小值是1，最大值是1000抖誉。那么就會(huì)生成一個(gè)長(zhǎng)度為1000的臨時(shí)數(shù)組，但是其中絕大部分的空間都是沒(méi)有用的衰倦，所以這就會(huì)導(dǎo)致空間復(fù)雜度變得很高袒炉。

計(jì)數(shù)排序是穩(wěn)定的排序算法，但在上面的實(shí)現(xiàn)中并沒(méi)有體現(xiàn)出這一點(diǎn)樊零，上面的實(shí)現(xiàn)沒(méi)有維護(hù)相同元素之間的先后順序我磁。所以需要做些變換：將臨時(shí)數(shù)組中從第二個(gè)元素開始孽文，每個(gè)元素都加上前一個(gè)元素的值。還是拿之前的[3, 3, 5, 2, 7, 4, 2]數(shù)組來(lái)舉例夺艰。計(jì)完數(shù)后的臨時(shí)數(shù)組為[2, 2, 1, 1, 0, 1]芋哭，此時(shí)做上面的變換，每個(gè)數(shù)都累加前面的一個(gè)數(shù)郁副，結(jié)果為[2, 4, 5, 6, 6, 7]减牺。這個(gè)時(shí)候臨時(shí)數(shù)組的含義就不再是每個(gè)數(shù)出現(xiàn)的次數(shù)了，此時(shí)記錄的是每個(gè)數(shù)在最后排好序的數(shù)組中應(yīng)該要存放的位置+1（如果有重復(fù)的就記錄最后一個(gè)）存谎。對(duì)于上面的待排序數(shù)組來(lái)說(shuō)拔疚，最后排好序的數(shù)組應(yīng)該為[2, 2, 3, 3, 4, 5, 7]。也就是說(shuō)既荚，此時(shí)各個(gè)數(shù)最后一次出現(xiàn)的索引位為：1, 3, 4, 5, 6稚失，分別都+1后就是2, 4, 5, 6, 7，這不就是上面做過(guò)變換之后的數(shù)組嗎恰聘？（沒(méi)有出現(xiàn)過(guò)的數(shù)字不管它）所以句各，此時(shí)從后往前遍歷原數(shù)組中的每一個(gè)值，將其減去最小值后晴叨，找到其在變換后的臨時(shí)數(shù)組中的索引凿宾，也就是找到了最后排好序的數(shù)組中的位置了。當(dāng)然篙螟，每次找到臨時(shí)數(shù)組中的索引后菌湃，這個(gè)位置的數(shù)需要-1。這樣如果后續(xù)有重復(fù)的該數(shù)字的話遍略，就會(huì)插入到當(dāng)前位置的前一個(gè)位置了惧所。由此也說(shuō)明了遍歷必須是從后往前遍歷，以此來(lái)維護(hù)相同數(shù)字之間的先后順序绪杏。

public int[] stableCountingSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    //記錄待排序數(shù)組中的最大值
    int max = array[0];
    //記錄待排序數(shù)組中的最小值
    int min = array[0];
    for (int i : array) {
        if (i > max) {
            max = i;
        }
        if (i < min) {
            min = i;
        }
    }
    int[] temp = new int[max - min + 1];
    //記錄每個(gè)數(shù)出現(xiàn)的次數(shù)
    for (int i : array) {
        temp[i - min]++;
    }
    //將temp數(shù)組進(jìn)行轉(zhuǎn)換下愈，記錄每個(gè)數(shù)在最后排好序的數(shù)組中應(yīng)該要存放的位置+1（如果有重復(fù)的就記錄最后一個(gè)）
    for (int j = 1; j < temp.length; j++) {
        temp[j] += temp[j - 1];
    }
    int[] sortedArray = new int[array.length];
    //這里必須是從后往前遍歷，以此來(lái)保證穩(wěn)定性
    for (int i = array.length - 1; i >= 0; i--) {
        sortedArray[temp[array[i] - min] - 1] = array[i];
        temp[array[i] - min]--;
    }
    return sortedArray;
}

9 桶排序

上面的計(jì)數(shù)排序在數(shù)組最大值和最小值之間的差值是多少蕾久，就會(huì)生成一個(gè)多大的臨時(shí)數(shù)組势似，也就是生成了一個(gè)這么多的桶，而每個(gè)桶中就只插入一個(gè)數(shù)據(jù)僧著。如果差值比較大的話履因，會(huì)比較浪費(fèi)空間。那么我能不能在一個(gè)桶中插入多個(gè)數(shù)據(jù)呢盹愚？當(dāng)然可以栅迄，而這就是桶排序的思路。桶排序類似于哈希表皆怕，通過(guò)一定的映射規(guī)則將數(shù)組中的元素映射到不同的桶中毅舆，每個(gè)桶內(nèi)進(jìn)行內(nèi)部排序西篓，最后將每個(gè)桶按順序輸出就行了。桶排序執(zhí)行的高效與否和是否是穩(wěn)定的取決于哈希散列的算法以及內(nèi)部排序的結(jié)果憋活。需要注意的是岂津，這個(gè)映射算法并不是常規(guī)的映射算法，要求是每個(gè)桶中的所有數(shù)都要比前一個(gè)桶中的所有數(shù)都要大悦即。這樣最后輸出的才是一個(gè)排好序的結(jié)果吮成。比如說(shuō)第一個(gè)桶中存1-30的數(shù)字，第二個(gè)桶中存31-60的數(shù)字盐欺，第三個(gè)桶中存61-90的數(shù)字...以此類推赁豆。下面給出一種實(shí)現(xiàn)：

public int[] bucketSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    //記錄待排序數(shù)組中的最大值
    int max = array[0];
    //記錄待排序數(shù)組中的最小值
    int min = array[0];
    for (int i : array) {
        if (i > max) {
            max = i;
        }
        if (i < min) {
            min = i;
        }
    }
    //計(jì)算桶的數(shù)量（可以自定義實(shí)現(xiàn)）
    int bucketNumber = (max - min) / array.length + 1;
    List<Integer>[] buckets = new ArrayList[bucketNumber];
    //計(jì)算每個(gè)桶存數(shù)的范圍（可以自定義實(shí)現(xiàn)或者不用實(shí)現(xiàn)）
    int bucketRange = (max - min + 1) / bucketNumber;

    for (int value : array) {
        //計(jì)算應(yīng)該放到哪個(gè)桶中（可以自定義實(shí)現(xiàn)）
        int bucketIndex = (value - min) / (bucketRange + 1);
        //延遲初始化
        if (buckets[bucketIndex] == null) {
            buckets[bucketIndex] = new ArrayList<>();
        }
        //放入指定的桶
        buckets[bucketIndex].add(value);
    }
    int index = 0;
    for (List<Integer> bucket : buckets) {
        //對(duì)每個(gè)桶進(jìn)行內(nèi)部排序，我這里使用的是快速排序冗美，也可以使用別的排序算法魔种，當(dāng)然也可以繼續(xù)遞歸去做桶排序
        quickSort(bucket);
        if (bucket == null) {
            continue;
        }
        //將不為null的桶中的數(shù)據(jù)按順序?qū)懟氐絘rray數(shù)組中
        for (Integer integer : bucket) {
            array[index++] = integer;
        }
    }
    return array;
}

10 基數(shù)排序

基數(shù)排序不是根據(jù)一個(gè)數(shù)的整體來(lái)進(jìn)行排序的，而是將數(shù)的每一位上的數(shù)字進(jìn)行排序粉洼。比如說(shuō)第一輪排序节预，我拿到待排序數(shù)組中所有數(shù)個(gè)位上的數(shù)字來(lái)進(jìn)行排序；第二輪排序我拿到待排序數(shù)組中所有數(shù)十位上的數(shù)字來(lái)進(jìn)行排序属韧；第三輪排序我拿到待排序數(shù)組中所有數(shù)百位上的數(shù)字來(lái)進(jìn)行排序...以此類推安拟。每一輪的排序都會(huì)累加上一輪所有前幾位上排序的結(jié)果，最終的結(jié)果就會(huì)是一個(gè)有序的數(shù)列宵喂。

基數(shù)排序一般是對(duì)所有非負(fù)整數(shù)進(jìn)行排序的糠赦，但是也可以有別的手段來(lái)去掉這種限制（比如都加一個(gè)固定的數(shù)或者都乘一個(gè)固定的數(shù)，排完序后再恢復(fù)等等）锅棕∽驹螅基數(shù)排序和桶排序很像，桶排序是按數(shù)值的區(qū)間進(jìn)行劃分裸燎，而基數(shù)排序是按數(shù)的位數(shù)進(jìn)行劃分顾瞻。同時(shí)這兩個(gè)排序都是需要依靠其他排序算法來(lái)實(shí)現(xiàn)的（如果不算遞歸調(diào)用桶排序本身的話）〉侣蹋基數(shù)排序每一輪的內(nèi)部排序會(huì)使用到計(jì)數(shù)排序來(lái)實(shí)現(xiàn)荷荤，因?yàn)槊恳晃簧系臄?shù)字無(wú)非就是0-9，是一個(gè)小范圍的數(shù)移稳，所以使用計(jì)數(shù)排序很合適蕴纳。

基數(shù)排序執(zhí)行示意圖：

img

具體的實(shí)現(xiàn)代碼如下：

public int[] radixSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    //記錄待排序數(shù)組中的最大值
    int max = array[0];
    for (int i : array) {
        if (i > max) {
            max = i;
        }
    }
    //獲取最大值的位數(shù)
    int maxDigits = 0;
    while (max != 0) {
        max /= 10;
        maxDigits++;
    }
    //用來(lái)計(jì)數(shù)排序的臨時(shí)數(shù)組
    int[] temp = new int[10];
    //用來(lái)存放每輪排序后的結(jié)果
    int[] sortedArray = new int[array.length];
    for (int d = 1; d <= maxDigits; d++) {
        //每次循環(huán)開始前都要清空temp數(shù)組中的值
        replaceArray(temp, null);
        //記錄每個(gè)數(shù)出現(xiàn)的次數(shù)
        for (int a : array) {
            temp[getNumberFromDigit(a, d)]++;
        }
        //將temp數(shù)組進(jìn)行轉(zhuǎn)換，記錄每個(gè)數(shù)在最后排好序的數(shù)組中應(yīng)該要存放的位置+1（如果有重復(fù)的就記錄最后一個(gè)）
        for (int j = 1; j < temp.length; j++) {
            temp[j] += temp[j - 1];
        }
        //這里必須是從后往前遍歷个粱，以此來(lái)保證穩(wěn)定性
        for (int i = array.length - 1; i >= 0; i--) {
            int index = getNumberFromDigit(array[i], d);
            sortedArray[temp[index] - 1] = array[i];
            temp[index]--;
        }
        //一輪計(jì)數(shù)排序過(guò)后袱蚓，將這次排好序的結(jié)果賦值給原數(shù)組
        replaceArray(array, sortedArray);
    }
    return array;
}

private final static int[] sizeTable = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

/**
 * 獲取指定位數(shù)上的數(shù)字是多少
 */
private int getNumberFromDigit(int number, int digit) {
    if (digit < 0) {
        return -1;
    }
    return (number / sizeTable[digit - 1]) % 10;
}

private void replaceArray(int[] originalArray, int[] replaceArray) {
    if (replaceArray == null) {
        for (int i = 0; i < originalArray.length; i++) {
            originalArray[i] = 0;
        }
    } else {
        for (int i = 0; i < originalArray.length; i++) {
            originalArray[i] = replaceArray[i];
        }
    }
}

11 復(fù)雜度及穩(wěn)定性

排序算法	時(shí)間復(fù)雜度	空間復(fù)雜度	穩(wěn)定性
平均情況	最好情況	最壞情況
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	穩(wěn)定
選擇排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不穩(wěn)定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	穩(wěn)定
希爾排序	取決于增量的選擇	O(1)	不穩(wěn)定
堆排序	O(nlog_2n)	O(nlog_2n)	O(nlog_2n)	O(1)	不穩(wěn)定
歸并排序	O(nlog_2n)	O(nlog_2n)	O(nlog_2n)	O(n)	穩(wěn)定
快速排序	O(nlog_2n)	O(nlog_2n)	O(n^2)	O(log_2n)	不穩(wěn)定
計(jì)數(shù)排序	O(n+k)	O(n+k)	O(n+k)	O(k)	穩(wěn)定
桶排序	取決于桶散列的結(jié)果和內(nèi)部排序算法的時(shí)間復(fù)雜度	O(n+l)	穩(wěn)定
基數(shù)排序	O(d*(n+r))	O(d*(n+r))	O(d*(n+r))	O(n+r)	穩(wěn)定

（其中：

1. k表示計(jì)數(shù)排序中最大值和最小值之間的差值；
2. l表示桶排序中桶的個(gè)數(shù)几蜻；
3. d表示基數(shù)排序中最大值的位數(shù)喇潘，r表示是多少進(jìn)制；
4. 希爾排序的時(shí)間復(fù)雜度很大程度上取決于增量gap sequence的選擇梭稚，不同的增量會(huì)有不同的時(shí)間復(fù)雜度颖低。文中使用的“gap=length/2”和“gap=gap/2”是一種常用的方式，也被稱為希爾增量弧烤，但其并不是最優(yōu)的忱屑。其實(shí)希爾排序增量的選擇與證明一直都是個(gè)數(shù)學(xué)難題，而下圖列出的是迄今為止大部分的gap sequence選擇的方案）

img

12 小彩蛋：猴子排序

在幾十年的計(jì)算機(jī)科學(xué)發(fā)展中暇昂，誕生了很多優(yōu)秀的算法莺戒，大家都在為了能開發(fā)出更高效的算法而努力。但是在這其中也誕生了一些僅供娛樂(lè)的搞笑算法急波，猴子排序就是其中的一種从铲。

猴子排序的實(shí)現(xiàn)很簡(jiǎn)單，隨機(jī)找出兩個(gè)元素進(jìn)行交換澄暮，直到隨機(jī)交換到最后能正確排好序的時(shí)候才會(huì)停止名段。

public int[] bogoSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    Random random = new Random();
    while (!inOrder(array)) {
        for (int i = 0; i < array.length; i++) {
            int swapPosition = random.nextInt(i + 1);
            if (swapPosition == i) {
                continue;
            }
            array[i] = array[i] ^ array[swapPosition];
            array[swapPosition] = array[i] ^ array[swapPosition];
            array[i] = array[i] ^ array[swapPosition];
        }
    }
    return array;
}

private boolean inOrder(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        if (array[i] > array[i + 1]) {
            return false;
        }
    }
    return true;
}

原創(chuàng)不易，未得準(zhǔn)許泣懊，請(qǐng)勿轉(zhuǎn)載伸辟，翻版必究