05-排序

排序簡介

排序算法的穩(wěn)定性：排序前兩個相等數(shù)的前后位置順序和排序后它們兩個的前后位置順序相同。

內(nèi)部排序：將需要處理的數(shù)據(jù)都加載到內(nèi)存中進行排序瞳浦。

快饭弓、希、選蚯姆、堆不穩(wěn)定("快些選一堆")
插入、選擇洒敏、交換龄恋、歸并、基數(shù)...

外部排序：數(shù)據(jù)量過大凶伙，無法全部加載到內(nèi)存中郭毕，需要借助外部存儲進行排序。

排序方法	平均時間	最壞時間	空間	穩(wěn)定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	穩(wěn)定
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	穩(wěn)定
選擇排序	$O(n^2)$	$O(n^2)$	$O(1)$	不穩(wěn)定
希爾排序	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不穩(wěn)定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不穩(wěn)定
快速排序	$O(nlog_2n)$	$O(n^2)$	$O(nlog_2n)$	不穩(wěn)定
歸并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	穩(wěn)定
基數(shù)排序	$O(n*k)$	$O(n*k)$	$O(n+k)$	穩(wěn)定
計數(shù)排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	穩(wěn)定
桶排序	$O(n+k)$	$O(n^2)$	$O(n+k)$	穩(wěn)定

1. 冒泡排序

冒泡排序：重復地走訪過要排序的元素列函荣，依次比較兩個相鄰的元素显押，如果順序錯誤就把他們交換過來扳肛。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成乘碑。越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端挖息。

// 冒泡排序
public static void bubbleSort(int[] container) {
    // 標識是否發(fā)生交換
    boolean isExchange = false;
    for (int i = 0; i < container.length - 1; i++) {
        // 每一趟從0開始，給右邊確定一個數(shù)
        for (int j = 0; j < container.length - 1 - i; j++) {
            if (container[j] > container[j + 1]) {
                isExchange = true;
                int tmp = container[j];
                container[j] = container[j + 1];
                container[j + 1] = tmp;
            }
        }
        // 如果某趟排序一次交換都沒有發(fā)生兽肤，則說明已經(jīng)有序了
        if (isExchange == false)
            return;
        else
            // 重置isExchange套腹，進行下次判斷
            isExchange = false;
    }
}

2. 插入排序

插入排序：每次從無序區(qū)取一個數(shù)，當該數(shù)比有序區(qū)某個數(shù)大時资铡，將該數(shù)插入到有序區(qū)這個數(shù)的后面电禀。

// 插入排序
public static void insertionSort(int[] container) {
    // 有序區(qū)最初只有容器的第0個元素，因為只有一個元素的序列不用排序就是有序的
    for (int j = 1; j < container.length; j++) {
        // key表示待插入的數(shù)
        int key = container[j];
        // i表示在哪一個元素后插入笤休，初值為有序區(qū)右邊第一個元素的索引
        int i = j - 1;
        /*
        Insert A[j] into the sorted sequence A[1..j-1].
        i >= 0保證數(shù)組不越界
        當待插入數(shù)比有序區(qū)數(shù)大時進行插入
        container[i] > key表示待插入的數(shù)還沒找到插入的位置
         */
        while (i >= 0 && container[i] > key) {
            // 將container[i]后移
            container[i + 1] = container[i];
            i--;
        }
        // 當退出循環(huán)時尖飞，說明插入的位置找到了，是i + 1
        // 若i + 1 == j店雅，則說明不用移動政基；這個if判斷可有可無
        if (i + 1 != j)
            container[i + 1] = key;
    }
}

3. 選擇排序

選擇排序：每一趟在無序區(qū)選出一個最小的，然后與無序區(qū)首元素交換底洗。

// 選擇排序
public static void selectionSort(int[] container) {
    for (int i = 0; i < container.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < container.length; j++) {
            if (container[j] < container[minIndex])
                minIndex = j;
        }
        if (minIndex != i) {
            int tmp = container[minIndex];
            container[minIndex] = container[i];
            container[i] = tmp;
        }
    }
}

4. 希爾排序

希爾排序又稱“縮小增量排序”腋么，是插入排序的一種更高效的改進版本。希爾排序是把記錄按下標的一定增量分組亥揖，對每組使用插入排序算法排序珊擂；隨著增量逐漸減少，每組包含的關鍵詞越來越多费变，當增量減至1時摧扇，整個文件恰被分成一組，算法便終止挚歧。

// 希爾排序
public static void shellSort(int[] container) {
    // 進行分組扛稽，增量初值為容器容量的一半，每次縮小為原來的一半
    for (int increment = container.length / 2; increment > 0; increment /= 2) {
        /**對各個分組進行插入排序：
         * increment之前的元素為各組初始時的有序區(qū)
         * i每次增1表示：
         * 并不是一次性將一個組排序完滑负，再對另一個組排序在张；
         * 而是輪流對各組進行排序，每次只給各組排一個元素
         */
        for (int i = increment; i < container.length; i++) {
            // 將container[i]插入到其所在分組的正確位置
            insertElement(container, i, increment);
        }
    }
}

private static void insertElement(int[] container, int index, int increment) {
    // key表示待插入的數(shù)
    int key = container[index];
    // i表示在哪一個元素后插入矮慕，初值為有序區(qū)右邊第一個元素的索引
    int i = index - increment;
    while (i >= 0 && container[i] > key) {
        // 將container[i]后移到container[i + increment]
        container[i + increment] = container[i];
        i -= increment;
    }
    // 若i + increment == index帮匾，則說明不用移動；這個if判斷可有可無
    if (i + increment != index)
        container[i + increment] = key;
}

5. 堆排序

堆是一棵完全二叉樹痴鳄，堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值瘟斜。

根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

優(yōu)先隊列具有最高級先出的行為特征螺句，分為最大優(yōu)先隊列和最小優(yōu)先隊列虽惭，通常采用堆數(shù)據(jù)結構來實現(xiàn)。

import java.util.Arrays;

/**
 * 最大堆與最大優(yōu)先隊列
 * 與堆排序相關的方法：maxHeapify蛇尚、buildMaxHeap芽唇、heapSort
 * 最大優(yōu)先隊列的方法：maximum、extractMax佣蓉、increaseKey披摄、insert
 */
public class Heap {
    // 有多少個堆元素存儲在數(shù)組中
    private int size;
    private int[] container;

    public Heap(int[] container) {
        this.container = container;
        size = container.length;
        buildMaxHeap();
    }

    // i的父節(jié)點
    private int parent(int i) {
        return (i - 1) / 2;
    }

    // i的左孩子
    private int left(int i) {
        return 2 * i + 1;
    }

    // i的右孩子
    private int right(int i) {
        return 2 * i + 2;
    }

    // 交換a和b
    private void exchange(int[] container, int x, int y) {
        int tmp = container[x];
        container[x] = container[y];
        container[y] = tmp;
    }

    // 最大堆堆化
    private void maxHeapify(int[] container, int i) {
        int left = left(i);
        int right = right(i);
        int largest = i;
        if (left < size && container[left] > container[i])
            largest = left;
        if (right < size && container[right] > container[largest])
            largest = right;
        if (largest != i) {
            exchange(container, i, largest);
            maxHeapify(container, largest);
        }
    }

    // 建立最大堆
    public void buildMaxHeap() {
        size = container.length;
        // container[length/2..length-1]為樹的葉結點
        // 從右到左，從下到上勇凭，堆化每一顆子樹
        for (int i = container.length / 2 - 1; i >= 0; i--)
            maxHeapify(container, i);
    }

    // 堆排序
    public void heapSort() {
        buildMaxHeap();
        for (int i = container.length - 1; i > 0; i--) {
            // 將當前堆中的最大元素與第i個交換
            exchange(container, 0, i);
            // 堆中元素疚膊，從右到左，少一個
            size--;
            // 重新堆化
            maxHeapify(container, 0);
        }
    }

    // 獲取最大堆的最大元素
    public int maximum() {
        return container[0];
    }

    // 去掉并返回container中的最大元素
    public int extractMax() {
        int max = container[0];
        // 將最后一個元素放到根的位置
        container[0] = container[size - 1];
        // 堆中元素減一
        size--;
        container = Arrays.copyOf(container, size);
        // 重新堆化
        maxHeapify(container, 0);
        return max;
    }

    // 將第i個元素的值增加到key
    public void increaseKey(int i, int key) {
        if (key < container[i])
            throw new RuntimeException();
        container[i] = key;
        // 若增加后的值比其父節(jié)點大虾标，則將其與父節(jié)點交換
        while (i > 0 && container[parent(i)] < container[i]) {
            exchange(container, i, parent(i));
            i = parent(i);
        }
    }

    // 將key插入到container
    public void insert(int key) {
        // 堆中元素加一
        size++;
        container = Arrays.copyOf(container, size);
        // 將新增加的空間的值由最小值增加到key
        container[size - 1] = Integer.MIN_VALUE;
        increaseKey(size - 1, key);
        // 以上操作寓盗，相當于將key插入到了container
    }

    @Override
    public String toString() {
        return "Heap{" +
                "size=" + size +
                ", container=" + Arrays.toString(container) +
                '}';
    }

    public static void main(String[] args) {
        int[] A = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
        Heap heap = new Heap(A);
        System.out.println("最大堆：\n" + heap);
        heap.heapSort();
        System.out.println("進行堆排序后：\n" + heap);
        heap.buildMaxHeap();
        System.out.println("重新建立的最大堆：\n" + heap);

        System.out.println("堆中最大值：\n" + heap.maximum());
        int max = heap.extractMax();
        System.out.println("去掉最大值" + max + "后的堆：\n" + heap);
        heap.increaseKey(1, 20);
        System.out.println("將" + 10 + "增加至20后的堆：\n" + heap);
        heap.insert(30);
        System.out.println("插入30后的堆：\n" + heap);
    }
}

6. 快速排序

快速排序使用了分治法，如對一個子數(shù)組A[p..r]進行快速排序的步驟：

分解：數(shù)組A[p..r]被劃分為兩個(可能為空)子數(shù)組A[p..q-1]和A[q+1..r]璧函，
使得A[p..q—1]中的每一個元素都小于等于A[q]傀蚌，而A[q]也小于等于A[q+1..r]中的每個元素。其中蘸吓，計算下標q也是劃分過程的一部分善炫。
解決：通過遞歸調(diào)用快速排序，對子數(shù)組A[p..q—1]和A[q+1..r]進行排序库继。
合并：因為子數(shù)組都是原址排序的箩艺，所以不需要合并操作：數(shù)組A[p..r]已經(jīng)有序。

// 快速排序宪萄，對[p, r]區(qū)間內(nèi)的元素排序
public static void quickSort(int[] A, int p, int r) {
    if (p < r) {
        int q = partition(A, p, r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }
}

// 數(shù)組的劃分艺谆，是快速排序的關鍵部分
private static int partition(int[] A, int p, int r) {
    // 圍繞A[r]來劃分子數(shù)組A[p..r]
    int x = A[r];
    // i是{ <= x區(qū)域}的最右邊元素的索引
    int i = p - 1;
    // j是{ > x區(qū)域}的后面一個元素的索引
    for (int j = p; j < r; j++) {
        // { <= x區(qū)域}和{ > x區(qū)域}相鄰
        // 如果A[j] <= x，則將A[j]和{ > x區(qū)域}最左邊的元素交換
        if (A[j] <= x) {
            i++;
            exchange(A, i, j);
        }
        // 如果A[j] > x拜英，則j++静汤，即將A[j]放入{ > x區(qū)域}的最右邊
    }
    exchange(A, i + 1, r);
    // 返回劃分后x所在的索引
    return i + 1;
}

// 交換a和b
private static void exchange(int[] A, int x, int y) {
    int tmp = A[x];
    A[x] = A[y];
    A[y] = tmp;
}

7. 歸并排序

歸并排序算法完全遵循分治模式。直觀上其操作如下：

分解：分解待排序的n個元素的序列成各具n/2個元素的兩個子序列居凶。
解決：使用歸并排序遞歸地排序兩個子序列虫给。
合并：合并兩個已排序的子序列以產(chǎn)生已排序的答案。

歸并排序算法的關鍵操作是“合并”步驟中兩個已排序序列的合并侠碧。

// 歸并排序狰右，對[p, r]區(qū)間內(nèi)的元素排序
public static void mergeSort(int[] A, int p, int r) {
    if (p < r) {
        // 向下取整
        int q = (p + r) / 2;
        // 排序左邊
        mergeSort(A, p, q);
        // 排序右邊
        mergeSort(A, q + 1, r);
        // 合并
        merge(A, p, q, r);
    }
}

// 合并A[p..q]和A[q+1..r]
private static void merge(int[] A, int p, int q, int r) {
    // A[p..q]的長度
    int leftLength = q - p + 1;
    // A[q+1..r]的長度
    int rightLength = r - q;
    // 多出來的最右邊的一個空間充當哨兵
    int[] left = new int[leftLength + 1];
    int[] right = new int[rightLength + 1];
    // 將A[p..q]復制到left[0..leftLength-1]
    for (int i = 0; i < leftLength; i++) {
        left[i] = A[p + i];
    }
    // 將A[q+1..r]復制到right[0..rightLength-1]
    for (int j = 0; j < rightLength; j++) {
        right[j] = A[q + 1 + j];
    }
    // 哨兵
    left[leftLength] = Integer.MAX_VALUE;
    right[rightLength] = Integer.MAX_VALUE;
    int i = 0;
    int j = 0;
    // 合并
    for (int k = p; k <= r; k++) {
        if (left[i] <= right[j]) {
            A[k] = left[i];
            i++;
        } else {
            A[k] = right[j];
            j++;
        }
    }
}

8. 基數(shù)排序

基數(shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機上的貢獻。它是這樣實現(xiàn)的：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度舆床，數(shù)位較短的數(shù)前面補零。然后，從最低位開始挨队，依次進行一次排序谷暮。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個有序序列盛垦。

基數(shù)排序的方式可以采用最低位優(yōu)先(LSD)或最高位優(yōu)先(MSD)湿弦，LSD的排序方式由鍵值的最右邊開始，而MSD則相反腾夯，由鍵值的最左邊開始颊埃。

基數(shù)排序是以空間換時間

// 基數(shù)排序，對n個d位的正整數(shù)進行排序
public static void radixSort(int[] container) {
    // 創(chuàng)建一個擁有10個桶的容器蝶俱，每個桶是一個線性表
    LinkedList<Integer>[] buckets = new LinkedList[10];
    for (int i = 0; i < 10; i++) {
        buckets[i] = new LinkedList<>();
    }

    // 獲取最大值的位數(shù)
    int d = (Arrays.stream(container).max().getAsInt() + "").length();
    // 采用最低位優(yōu)先班利，根據(jù)每一位進行排序
    for (int i = 0; i < d; i++) {
        // 將容器中的元素根據(jù)第i位，依次放入對應的桶中
        for (int j = 0; j < container.length; j++) {
            // digit表示元素第i位的數(shù)字
            int digit = container[j] / (int) Math.pow(10, i) % 10;
            // 將container[j]放入第digit個桶中
            buckets[digit].add(container[j]);
        }
        // 放完后榨呆，即已經(jīng)按照第i位的順序排好了
        // 將桶中元素依次放入原容器罗标，index代表原容器的索引
        int index = 0;
        for (int j = 0; j < buckets.length; j++) {
            for (int k = 0; k < buckets[j].size(); k++) {
                // 將第j個桶中的第k個元素賦值給原容器
                container[index++] = buckets[j].get(k);
            }
            // 清空第j個桶
            buckets[j].clear();
        }
    }
}

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市积蜻，隨后出現(xiàn)的幾起案子闯割，更是在濱河造成了極大的恐慌，老刑警劉巖竿拆，帶你破解...
沈念sama閱讀 206,482評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件宙拉，死亡現(xiàn)場離奇詭異，居然都是意外死亡丙笋，警方通過查閱死者的電腦和手機谢澈，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,377評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來不见，“玉大人澳化，你說我怎么就攤上這事∥人保” “怎么了缎谷？”我有些...
開封第一講書人閱讀 152,762評論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長灶似。經(jīng)常有香客問我列林，道長，這世上最難降的妖魔是什么酪惭？我笑而不...
開封第一講書人閱讀 55,273評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任希痴，我火速辦了婚禮，結果婚禮上春感，老公的妹妹穿的比我還像新娘砌创。我一直安慰自己虏缸，他們只是感情好，可當我...
茶點故事閱讀 64,289評論 5贊 373
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布嫩实。她就那樣靜靜地躺著刽辙，像睡著了一般。火紅的嫁衣襯著肌膚如雪甲献。梳的紋絲不亂的頭發(fā)上宰缤，一...
開封第一講書人閱讀 49,046評論 1贊 285
城市分裂傳說
那天，我揣著相機與錄音晃洒，去河邊找鬼慨灭。笑死，一個胖子當著我的面吹牛球及，可吹牛的內(nèi)容都是我干的氧骤。我是一名探鬼主播，決...
沈念sama閱讀 38,351評論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼桶略，長吁一口氣：“原來是場噩夢啊……” “哼语淘！你這毒婦竟也來了？” 一聲冷哼從身側響起际歼，我...
開封第一講書人閱讀 36,988評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤惶翻，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后鹅心，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體吕粗，經(jīng)...
沈念sama閱讀 43,476評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 35,948評論 2贊 324
?白月光啟示錄
正文我和宋清朗相戀三年旭愧，在試婚紗的時候發(fā)現(xiàn)自己被綠了颅筋。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 38,064評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡输枯，死狀恐怖议泵，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情桃熄，我是刑警寧澤先口，帶...
沈念sama閱讀 33,712評論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站瞳收，受9級特大地震影響碉京，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜螟深，卻給世界環(huán)境...
茶點故事閱讀 39,261評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一谐宙、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧界弧，春花似錦凡蜻、人聲如沸搭综。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,264評論 0贊 19
一樁弒父案咽瓷，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽设凹。三九已至，卻和暖如春茅姜，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背月匣。一陣腳步聲響...
開封第一講書人閱讀 31,486評論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工钻洒，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人锄开。一個月前我還...
沈念sama閱讀 45,511評論 2贊 354
代替公主和親
正文我出身青樓素标，卻偏偏與公主長得像，于是被迫代替她去往敵國和親萍悴。傳聞我的和親對象是個殘疾皇子头遭，可洞房花燭夜當晚...
茶點故事閱讀 42,802評論 2贊 345