11.經典O(n²)比較型排序算法

11.經典O(n²)比較型排序算法

關注公號「碼哥字節」修鍊技術內功心法,完整代碼可跳轉 GitHub:https://github.com/UniqueDong/algorithms.git

摘要:排序算法提多了,很多甚至連名字你都沒聽過,比如猴子排序、睡眠排序等。最常用的:冒泡排序、選擇排序、插入排序、歸併排序、快速排序、計數排序、基數排序、桶排序。根據時間複雜度,我們分三類來學習,今天要講的就是 冒泡、插入、選擇 排序算法。

排序算法 時間複雜度 是否基於比較
冒泡、插入、選擇 O(n²)
快排、歸併 O(nlogn)
桶、計數、基數 O(n)

十種常見的的排序算法可以分兩大類:

  1. 比較類排序:通過比較來決定元素的相對次序,由於其時間複雜度無法突破 O(nlogn),因此也叫做非線性時間排序。
  2. 非比較類排序:不是通過比較元素來決定元素的相對次序,可以突破比較排序的時間下限,線性時間運行,也叫做線性時間非比較類排序。

學會評估一個排序算法

學習算法,除了知道原理以及代碼實現以外,還有更重要的是學會如何評價、分析一個排序算法的 執行效率、內存損耗、穩定性。

執行效率

一般通過如下方面衡量:

1.最好、最壞、平均時間複雜度

為何要區分這三種時間複雜度?第一,通過複雜度可以大致判斷算法的執行次數。第二,對於要排序的數據有的無序、有的接近有序,有序度不同不同對於執行時間是不一樣的,所以我們要只掉不同數據場景下算法的性能。

2. 時間複雜度的係數、常數、低階

我們知道,時間複雜度反應的是數據規模 n 很大的時候的一個增長趨勢,所以它表示的時候會忽略係數、常數、低階。但是實際的軟件開發中,我們排序的可能是 10 個、100 個、1000 個這樣規模很小的數據,所以,在對同一階時間複雜度的排序算法性能對比的時候,我們就要把係數、常數、低階也考慮進來。

3.比較次數移動(交換)數據次數
基於比較排序的算法執行過程都會涉及兩個操作、一個是比較,另一個就是元素交換或者數據移動。所以我們也要把數據交換或者移動次數考慮進來。

內存消耗

算法的內存消耗通過空間複雜度來衡量,不過在這裏針對排序算法的內存算好還有一個新概念,原地排序就是特指空間複雜度為 O(1) 的算法,這次所講的算法都是原地排序算法。

算法的穩定性

如果待排序的序列中存在值相等的元素,經過排序之後,相等元素之間原有的先後順序不變。** 比如 a 原本在 b 前面,而 a=b ,排序之後 a 仍然在 b 的前面。

比如我們有一組數據 2,9,3,4,8,3,按照大小排序之後就是 2,3,3,4,8,9。

這組數據里有兩個 3。經過某種排序算法排序之後,如果兩個 3 的前後順序沒有改變,那我們就把這種排序算法叫作穩定的排序算法;如果前後順序發生變化,那對應的排序算法就叫作不穩定的排序算法

冒泡排序

冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較,看是否滿足大小關係要求。如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應該在的位置,重複 n 次,就完成了 n 個數據的排序工作。

這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

作為最簡單的排序算法之一,冒泡排序給我的感覺就像 Abandon 在單詞書里出現的感覺一樣,每次都在第一頁第一位,所以最熟悉。冒泡排序還有一種優化算法,就是立一個 flag,當在一趟序列遍歷中元素沒有發生交換,則證明該序列已經有序。但這種改進對於提升性能來說並沒有什麼太大作用。

算法步驟

  1. 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。

  2. 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完后,最後的元素會是最大的數。

  3. 針對所有的元素重複以上的步驟,除了最後一個。

  4. 持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對数字需要比較。

/**
 * 冒泡排序: 時間複雜度 O(n²),最壞時間複雜度 O(n²),最好時間複雜度 O(n),平均時間複雜度 O(n²)
 * 空間複雜度 O(1),穩定排序算法
 */
public class BubbleSort implements ComparisonSort {
    @Override
    public int[] sort(int[] sourceArray) {
        // 複製數組,不改變參數內容
        int[] result = Arrays.copyOf(sourceArray, sourceArray.length);
        if (sourceArray.length <= 1) {
            return result;
        }
        int length = result.length;
        for (int i = 0; i < length; i++) {
            // 設定標記,當沒有數據需要交換的時候則說明已經有序,提前退出外部循環
            boolean hasChange = false;
            for (int j = 0; j < (length - 1) - i ; j++) {
                if (result[j] > result[j + 1]) {
                    // 數據交換
                    int temp = result[j];
                    result[j] = result[j + 1];
                    result[j + 1] = temp;
                    hasChange = true;
                }
            }
            if (!hasChange) {
                // 沒有數據交換,已經有序,提前退出
                break;
            }
        }
        return result;
    }
}

那麼問題來了,我們來分析下這個算法的效率如何,教大家學會如何評估一個算法:

1.冒泡是原地排序算法么?

因為冒泡的過程只有相鄰數據的交換操作,屬於常量級別的臨時空間,所以空間複雜度是 O(1),屬於原地排序算法。

2.是穩定排序算法?

只有交換才改變兩個元素的前後順序,當相鄰數據相等,不做交換,所以相同大小的數據在排序前後都不會改變順序,屬於穩定排序算法。

3.時間複雜度

最好時間複雜度:當數據已經有序,只需要一次冒泡,所以是 O(1)。(ps:都已經是正序了,還要你冒泡何用)

最壞時間複雜度: 數據是倒序的,我們需要進行 n 次冒泡操作,所以最壞情況時間複雜度為 O(n2)。(ps:寫一個 for 循環反序輸出數據不就行了,幹嘛要用你冒泡排序呢,我是閑的嗎)

插入排序

我們先來看一個問題。一個有序的數組,我們往裡面添加一個新的數據后,如何繼續保持數據有序呢?很簡單,我們只要遍曆數組,找到數據應該插入的位置將其插入即可。

插入排序是一種最簡單直觀的排序算法,它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。

插入排序也包含兩種操作,一種是元素的比較,一種是元素的移動。當我們需要將一個數據 a 插入到已排序區間時,需要拿 a 與已排序區間的元素依次比較大小,找到合適的插入位置。找到插入點之後,我們還需要將插入點之後的元素順序往後移動一位,這樣才能騰出位置給元素 a 插入。

代碼如下所示:

/**
 * 插入排序:時間複雜度 O(n²),平均時間複雜度 O(n²),最好時間複雜度 O(n),
 * 最壞時間複雜度 O(n²),空間時間複雜度 O(1).穩定排序算法。
 */
public class InsertionSort implements ComparisonSort {

    @Override
    public int[] sort(int[] sourceArray) {
        int[] result = Arrays.copyOf(sourceArray, sourceArray.length);
        if (sourceArray.length <= 1) {
            return result;
        }
        // 從下標為 1 開始比較選擇合適位置插入,因為下標 0 只有一個元素,默認是有序
        int length = result.length;
        for (int i = 1; i < length; i++) {
            // 待插入數據
            int insertValue = result[i];
            // 從已排序的序列最右邊元素開始比較,找到比待插入樹更小的數位置
            int j = i - 1;
            for (; j >= 0; j--){
                if (result[j] > insertValue) {
                    // 向後移動數據,騰出待插入位置
                    result[j + 1] = result[j];
                } else {
                    // 找到待插入位置,跳出循環
                    break;
                }
            }
            // 插入數據,因為前面多執行了 j--,
            result[j + 1] = insertValue;
        }
        return result;
    }
}

依然繼續分析該算法的性能。

1.是否是原地排序算法

從實現過程就知道,插入排序不需要額外的存儲空間,所以空間複雜度是 O(1),屬於原地排序。

2.是否是穩定排序算法

對於值相等的元素,我們選擇將數據插入到前面元素的侯娜,這樣就保證原有的前後順序不變,屬於穩定排序算法。

3.時間複雜度

如果要排序的數據已經是有序的,我們並不需要搬移任何數據。如果我們從尾到頭在有序數據組裡面查找插入位置,每次只需要比較一個數據就能確定插入的位置。所以這種情況下,最好是時間複雜度為 O(n)。注意,這裡是從尾到頭遍歷已經有序的數據

如果數組是倒序的,每次插入都相當於在數組的第一個位置插入新的數據,所以需要移動大量的數據,所以最壞情況時間複雜度為 O(n²)。

還記得我們在數組中插入一個數據的平均時間複雜度是多少嗎?沒錯,是 O(n)。所以,對於插入排序來說,每次插入操作都相當於在數組中插入一個數據,循環執行 n 次插入操作,所以平均時間複雜度為 O(n²)。

選擇排序

選擇排序是一種簡單直觀的排序算法,無論什麼數據進去都是 O(n²) 的時間複雜度。所以用到它的時候,數據規模越小越好。

選擇排序算法的實現思路有點類似插入排序,也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間中找到最小的元素,將其放到已排序區間的末尾。

算法步驟

  1. 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
  2. 再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。
  3. 重複第二步,直到所有元素均排序完畢。

代碼如下:

public class SelectionSort implements ComparisonSort {

    @Override
    public int[] sort(int[] sourceArray) {
        int length = sourceArray.length;
        int[] result = Arrays.copyOf(sourceArray, length);
        if (length <= 0) {
            return result;
        }
        // 一共需要 length - 1 輪比較
        for (int i = 0; i < length - 1; i++) {
            // 每輪需要比較的次數 length - i,找出最小元素下標
            int minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (result[j] < result[minIndex]) {
                    // 查出每次最小遠元素下標
                    minIndex = j;
                }
            }
            // 將當前 i 位置的數據與最小值交換數據
            if (i != minIndex) {
                int temp = result[i];
                result[i] = result[minIndex];
                result[minIndex] = temp;
            }
        }
        return result;
    }
}

首先,選擇排序空間複雜度為 O(1),是一種原地排序算法。選擇排序的最好情況時間複雜度、最壞情況和平均情況時間複雜度都為 O(n²)。

那選擇排序是穩定的排序算法嗎?

答案是否定的,選擇排序是一種不穩定的排序算法。從我前面畫的那張圖中,你可以看出來,選擇排序每次都要找剩餘未排序元素中的最小值,並和前面的元素交換位置,這樣破壞了穩定性

比如 5,8,5,2,9 這樣一組數據,使用選擇排序算法來排序的話,第一次找到最小元素 2,與第一個 5 交換位置,那第一個 5 和中間的 5 順序就變了,所以就不穩定了。正是因此,相對於冒泡排序和插入排序,選擇排序就稍微遜色了。

總結

這三種時間複雜度為 O(n²) 的排序算法中,冒泡排序、選擇排序,可能就純粹停留在理論的層面了,學習的目的也只是為了開拓思維,實際開發中應用並不多,但是插入排序還是挺有用的。後面講排序優化的時候,我會講到,有些編程語言中的排序函數的實現原理會用到插入排序算法。(希爾排序就是插入排序的一種優化)

今天講的這三種排序算法,實現代碼都非常簡單,對於小規模數據的排序,用起來非常高效。但是在大規模數據排序的時候,這個時間複雜度還是稍微有點高,所以我們更傾向於用下一節要講的時間複雜度為 O(nlogn) 的排序算法。

課後思考

最後給大家一個問題,答案可在後台發送 「插入」獲取答案,也可以加群跟我們一起討論。

問題是:插入排序和冒泡排序時間複雜度相同,都是 O(n²),實際開發中更傾向於插入排序而不是冒泡排序

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※超省錢租車方案

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

※推薦台中搬家公司優質服務,可到府估價