排序（上）：為什么插入排序比冒泡排序更受歡迎？

排序?qū)τ谌魏我粋€程序員來說，可能都不會陌生。你學(xué)的第一個算法，可能就是排序。大部分編程語言中，也都提供了排序函數(shù)。在平常的項目中，我們也經(jīng)常會用到排序。排序非常重要，所以我會花多一點時間來詳細(xì)講一講經(jīng)典的排序算法。

排序算法太多了，有很多可能你連名字都沒聽說過，比如猴子排序、睡眠排序、面條排序等。我只講眾多排序算法中的一小撮，也是最經(jīng)典的、最常用的：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、計數(shù)排序、基數(shù)排序、桶排序。我按照時間復(fù)雜度把它們分成了三類，分三節(jié)課來講解。

帶著問題去學(xué)習(xí)，是最有效的學(xué)習(xí)方法。所以按照慣例，我還是先給你出一個思考題：插入排序和冒泡排序的時間復(fù)雜度相同，都是 O(n2)，在實際的軟件開發(fā)里，為什么我們更傾向于使用插入排序算法而不是冒泡排序算法呢？

你可以先思考一兩分鐘，帶著這個問題，我們開始今天的內(nèi)容！

如何分析一個“排序算法”？

學(xué)習(xí)排序算法，我們除了學(xué)習(xí)它的算法原理、代碼實現(xiàn)之外，更重要的是要學(xué)會如何評價、分析一個排序算法。那分析一個排序算法，要從哪幾個方面入手呢？

排序算法的執(zhí)行效率

對于排序算法執(zhí)行效率的分析，我們一般會從這幾個方面來衡量：

1. 最好情況、最壞情況、平均情況時間復(fù)雜度

我們在分析排序算法的時間復(fù)雜度時，要分別給出最好情況、最壞情況、平均情況下的時間復(fù)雜度。除此之外，你還要說出最好、最壞時間復(fù)雜度對應(yīng)的要排序的原始數(shù)據(jù)是什么樣的。

為什么要區(qū)分這三種時間復(fù)雜度呢？第一，有些排序算法會區(qū)分，為了好對比，所以我們最好都做一下區(qū)分。第二，對于要排序的數(shù)據(jù)，有的接近有序，有的完全無序。有序度不同的數(shù)據(jù)，對于排序的執(zhí)行時間肯定是有影響的，我們要知道排序算法在不同數(shù)據(jù)下的性能表現(xiàn)。

2. 時間復(fù)雜度的系數(shù)、常數(shù) 、低階

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

3. 比較次數(shù)和交換（或移動）次數(shù)

這一節(jié)和下一節(jié)講的都是基于比較的排序算法?；诒容^的排序算法的執(zhí)行過程，會涉及兩種操作，一種是元素比較大小，另一種是元素交換或移動。所以，如果我們在分析排序算法的執(zhí)行效率的時候，應(yīng)該把比較次數(shù)和交換（或移動）次數(shù)也考慮進去。

排序算法的內(nèi)存消耗

我們前面講過，算法的內(nèi)存消耗可以通過空間復(fù)雜度來衡量，排序算法也不例外。不過，針對排序算法的空間復(fù)雜度，我們還引入了一個新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空間復(fù)雜度是 O(1) 的排序算法。我們今天講的三種排序算法，都是原地排序算法。

排序算法的穩(wěn)定性

僅僅用執(zhí)行效率和內(nèi)存消耗來衡量排序算法的好壞是不夠的。針對排序算法，我們還有一個重要的度量指標(biāo)，穩(wěn)定性。這個概念是說，如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。

我通過一個例子來解釋一下。比如我們有一組數(shù)據(jù) 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。

這組數(shù)據(jù)里有兩個 3。經(jīng)過某種排序算法排序之后，如果兩個 3 的前后順序沒有改變，那我們就把這種排序算法叫作穩(wěn)定的排序算法；如果前后順序發(fā)生變化，那對應(yīng)的排序算法就叫作不穩(wěn)定的排序算法。

你可能要問了，兩個 3 哪個在前，哪個在后有什么關(guān)系啊，穩(wěn)不穩(wěn)定又有什么關(guān)系呢？為什么要考察排序算法的穩(wěn)定性呢？

很多數(shù)據(jù)結(jié)構(gòu)和算法課程，在講排序的時候，都是用整數(shù)來舉例，但在真正軟件開發(fā)中，我們要排序的往往不是單純的整數(shù)，而是一組對象，我們需要按照對象的某個 key 來排序。

比如說，我們現(xiàn)在要給電商交易系統(tǒng)中的“訂單”排序。訂單有兩個屬性，一個是下單時間，另一個是訂單金額。如果我們現(xiàn)在有 10 萬條訂單數(shù)據(jù)，我們希望按照金額從小到大對訂單數(shù)據(jù)排序。對于金額相同的訂單，我們希望按照下單時間從早到晚有序。對于這樣一個排序需求，我們怎么來做呢？

最先想到的方法是：我們先按照金額對訂單數(shù)據(jù)進行排序，然后，再遍歷排序之后的訂單數(shù)據(jù)，對于每個金額相同的小區(qū)間再按照下單時間排序。這種排序思路理解起來不難，但是實現(xiàn)起來會很復(fù)雜。

借助穩(wěn)定排序算法，這個問題可以非常簡潔地解決。解決思路是這樣的：我們先按照下單時間給訂單排序，注意是按照下單時間，不是金額。排序完成之后，我們用穩(wěn)定排序算法，按照訂單金額重新排序。兩遍排序之后，我們得到的訂單數(shù)據(jù)就是按照金額從小到大排序，金額相同的訂單按照下單時間從早到晚排序的。為什么呢？

穩(wěn)定排序算法可以保持金額相同的兩個對象，在排序之后的前后順序不變。第一次排序之后，所有的訂單按照下單時間從早到晚有序了。在第二次排序中，我們用的是穩(wěn)定的排序算法，所以經(jīng)過第二次排序之后，相同金額的訂單仍然保持下單時間從早到晚有序。

冒泡排序（Bubble Sort）
我們從冒泡排序開始，學(xué)習(xí)今天的三種排序算法。

冒泡排序只會操作相鄰的兩個數(shù)據(jù)。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關(guān)系要求。如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應(yīng)該在的位置，重復(fù) n 次，就完成了 n 個數(shù)據(jù)的排序工作。

我用一個例子，帶你看下冒泡排序的整個過程。我們要對一組數(shù)據(jù) 4，5，6，3，2，1，從小到到大進行排序。第一次冒泡操作的詳細(xì)過程就是這樣：

可以看出，經(jīng)過一次冒泡操作之后，6 這個元素已經(jīng)存儲在正確的位置上。要想完成所有數(shù)據(jù)的排序，我們只要進行 6 次這樣的冒泡操作就行了。

實際上，剛講的冒泡過程還可以優(yōu)化。當(dāng)某次冒泡操作已經(jīng)沒有數(shù)據(jù)交換時，說明已經(jīng)達(dá)到完全有序，不用再繼續(xù)執(zhí)行后續(xù)的冒泡操作。我這里還有另外一個例子，這里面給 6 個元素排序，只需要 4 次冒泡操作就可以了。

冒泡排序算法的原理比較容易理解，具體的代碼我貼到下面，你可以結(jié)合著代碼來看我前面講的原理。

// 冒泡排序，a 表示數(shù)組，n 表示數(shù)組大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循環(huán)的標(biāo)志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交換
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有數(shù)據(jù)交換      
      }
    }
    if (!flag) break;  // 沒有數(shù)據(jù)交換，提前退出
  }
}

現(xiàn)在，結(jié)合剛才我分析排序算法的三個方面，我有三個問題要問你。

第一，冒泡排序是原地排序算法嗎？

冒泡的過程只涉及相鄰數(shù)據(jù)的交換操作，只需要常量級的臨時空間，所以它的空間復(fù)雜度為 O(1)，是一個原地排序算法。

第二，冒泡排序是穩(wěn)定的排序算法嗎？

在冒泡排序中，只有交換才可以改變兩個元素的前后順序。為了保證冒泡排序算法的穩(wěn)定性，當(dāng)有相鄰的兩個元素大小相等的時候，我們不做交換，相同大小的數(shù)據(jù)在排序前后不會改變順序，所以冒泡排序是穩(wěn)定的排序算法。

第三，冒泡排序的時間復(fù)雜度是多少？

最好情況下，要排序的數(shù)據(jù)已經(jīng)是有序的了，我們只需要進行一次冒泡操作，就可以結(jié)束了，所以最好情況時間復(fù)雜度是 O(n)。而最壞的情況是，要排序的數(shù)據(jù)剛好是倒序排列的，我們需要進行 n 次冒泡操作，所以最壞情況時間復(fù)雜度為 $O(n^2)$

最好、最壞情況下的時間復(fù)雜度很容易分析，那平均情況下的時間復(fù)雜是多少呢？我們前面講過，平均時間復(fù)雜度就是加權(quán)平均期望時間復(fù)雜度，分析的時候要結(jié)合概率論的知識。

對于包含 n 個數(shù)據(jù)的數(shù)組，這 n 個數(shù)據(jù)就有 n! 種排列方式。不同的排列方式，冒泡排序執(zhí)行的時間肯定是不同的。比如我們前面舉的那兩個例子，其中一個要進行 6 次冒泡，而另一個只需要 4 次。如果用概率論方法定量分析平均時間復(fù)雜度，涉及的數(shù)學(xué)推理和計算就會很復(fù)雜。我這里還有一種思路，通過“有序度”和“逆序度”這兩個概念來進行分析。

有序度是數(shù)組中具有有序關(guān)系的元素對的個數(shù)。有序元素對用數(shù)學(xué)表達(dá)式表示就是這樣：

有序元素對：a[i] <= a[j],如果 i < j.

同理，對于一個倒序排列的數(shù)組，比如 6，5，4，3，2，1，有序度是 0；對于一個完全有序的數(shù)組，比如 1，2，3，4，5，6，有序度就是，也就是 15。我們把這種完全有序的數(shù)組的有序度叫作滿有序度。

逆序度的定義正好跟有序度相反（默認(rèn)從小到大為有序），我想你應(yīng)該已經(jīng)想到了。關(guān)于逆序度，我就不舉例子講了。你可以對照我講的有序度的例子自己看下。

逆序元素對：a[i] > a[j], if i < j .

關(guān)于這三個概念，我們還可以得到一個公式：逆序度 = 滿有序度 - 有序度。我們排序的過程就是一種增加有序度，減少逆序度的過程，最后達(dá)到滿有序度，就說明排序完成了。

我還是拿前面舉的那個冒泡排序的例子來說明。要排序的數(shù)組的初始狀態(tài)是 4，5，6，3，2，1 ，其中，有序元素對有 (4，5) (4，6)(5，6)，所以有序度是 3。n=6，所以排序完成之后終態(tài)的滿有序度為 n*(n-1)/2=15

冒泡排序包含兩個操作原子，比較和交換。每交換一次，有序度就加 1。不管算法怎么改進，交換次數(shù)總是確定的，即為逆序度，也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12，要進行 12 次交換操作。

對于包含 n 個數(shù)據(jù)的數(shù)組進行冒泡排序，平均交換次數(shù)是多少呢？最壞情況下，初始狀態(tài)的有序度是 0，所以要進行 n(n-1)/2 次交換。最好情況下，初始狀態(tài)的有序度是 n(n-1)/2，就不需要進行交換。我們可以取個中間值 n*(n-1)/4，來表示初始有序度既不是很高也不是很低的平均情況。

換句話說，平均情況下，需要 n*(n-1)/4 次交換操作，比較操作肯定要比交換操作多，而復(fù)雜度的上限是 $O(n^2)$ ，所以平均情況下的時間復(fù)雜度就是 $O(n^2)$ 。

這個平均時間復(fù)雜度推導(dǎo)過程其實并不嚴(yán)格，但是很多時候很實用，畢竟概率論的定量分析太復(fù)雜，不太好用。等我們講到快排的時候，我還會再次用這種“不嚴(yán)格”的方法來分析平均時間復(fù)雜度。

插入排序（Insertion Sort）

我們先來看一個問題。一個有序的數(shù)組，我們往里面添加一個新的數(shù)據(jù)后，如何繼續(xù)保持?jǐn)?shù)據(jù)有序呢？很簡單，我們只要遍歷數(shù)組，找到數(shù)據(jù)應(yīng)該插入的位置將其插入即可。

這是一個動態(tài)排序的過程，即動態(tài)地往有序集合中添加數(shù)據(jù)，我們可以通過這種方法保持集合中的數(shù)據(jù)一直有序。而對于一組靜態(tài)數(shù)據(jù)，我們也可以借鑒上面講的插入方法，來進行排序，于是就有了插入排序算法。

那插入排序具體是如何借助上面的思想來實現(xiàn)排序的呢？

首先，我們將數(shù)組中的數(shù)據(jù)分為兩個區(qū)間，已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個元素，就是數(shù)組的第一個元素。插入算法的核心思想是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據(jù)一直有序。重復(fù)這個過程，直到未排序區(qū)間中元素為空，算法結(jié)束。

如圖所示，要排序的數(shù)據(jù)是 4，5，6，1，3，2，其中左側(cè)為已排序區(qū)間，右側(cè)是未排序區(qū)間。

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

對于不同的查找插入點方法（從頭到尾、從尾到頭），元素的比較次數(shù)是有區(qū)別的。但對于一個給定的初始序列，移動操作的次數(shù)總是固定的，就等于逆序度。

為什么說移動次數(shù)就等于逆序度呢？我拿剛才的例子畫了一個圖表，你一看就明白了。滿有序度是 n*(n-1)/2=15，初始序列的有序度是 5，所以逆序度是 10。插入排序中，數(shù)據(jù)移動的個數(shù)總和也等于 10=3+3+4。

插入排序的原理也很簡單吧？我也將代碼實現(xiàn)貼在這里，你可以結(jié)合著代碼再看下。

// 插入排序，a 表示數(shù)組，n 表示數(shù)組大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;
 
  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 數(shù)據(jù)移動
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入數(shù)據(jù)
  }
}

現(xiàn)在，我們來看點稍微復(fù)雜的東西。我這里還是有三個問題要問你。

第一，插入排序是原地排序算法嗎？

從實現(xiàn)過程可以很明顯地看出，插入排序算法的運行并不需要額外的存儲空間，所以空間復(fù)雜度是 O(1)，也就是說，這是一個原地排序算法。

第二，插入排序是穩(wěn)定的排序算法嗎？

在插入排序中，對于值相同的元素，我們可以選擇將后面出現(xiàn)的元素，插入到前面出現(xiàn)元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩(wěn)定的排序算法。

第三，插入排序的時間復(fù)雜度是多少？

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

如果數(shù)組是倒序的，每次插入都相當(dāng)于在數(shù)組的第一個位置插入新的數(shù)據(jù)，所以需要移動大量的數(shù)據(jù)，所以最壞情況時間復(fù)雜度為 $O(n^2)$ 。

還記得我們在數(shù)組中插入一個數(shù)據(jù)的平均時間復(fù)雜度是多少嗎？沒錯，是 $O(n)$ 。所以，對于插入排序來說，每次插入操作都相當(dāng)于在數(shù)組中插入一個數(shù)據(jù)，循環(huán)執(zhí)行 n 次插入操作，所以平均時間復(fù)雜度為 $O(n^2)$ 。

選擇排序（Selection Sort）

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

照例，也有三個問題需要你思考，不過前面兩種排序算法我已經(jīng)分析得很詳細(xì)了，這里就直接公布答案了。

首先，選擇排序空間復(fù)雜度為 $O(1)$ ，是一種原地排序算法。選擇排序的最好情況時間復(fù)雜度、最壞情況和平均情況時間復(fù)雜度都為 $O(n^2)$ 。你可以自己來分析看看。

那選擇排序是穩(wěn)定的排序算法嗎？這個問題我著重來說一下。

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

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

解答開篇

基本的知識都講完了，我們來看開篇的問題：冒泡排序和插入排序的時間復(fù)雜度都是 O(n2)，都是原地排序算法，為什么插入排序要比冒泡排序更受歡迎呢？

我們前面分析冒泡排序和插入排序的時候講到，冒泡排序不管怎么優(yōu)化，元素交換的次數(shù)是一個固定值，是原始數(shù)據(jù)的逆序度。插入排序是同樣的，不管怎么優(yōu)化，元素移動的次數(shù)也等于原始數(shù)據(jù)的逆序度。

但是，從代碼實現(xiàn)上來看，冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動要復(fù)雜，冒泡排序需要 3 個賦值操作，而插入排序只需要 1 個。我們來看這段操作：

冒泡排序中數(shù)據(jù)的交換操作：
if (a[j] > a[j+1]) { // 交換
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}
 
插入排序中數(shù)據(jù)的移動操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 數(shù)據(jù)移動
} else {
  break;
}

我們把執(zhí)行一個賦值語句的時間粗略地計為單位時間（unit_time），然后分別用冒泡排序和插入排序?qū)ν粋€逆序度是 K 的數(shù)組進行排序。用冒泡排序，需要 K 次交換操作，每次需要 3 個賦值語句，所以交換操作總耗時就是 3*K 單位時間。而插入排序中數(shù)據(jù)移動操作只需要 K 個單位時間。

這個只是我們非常理論的分析，為了實驗，針對上面的冒泡排序和插入排序的 Java 代碼，我寫了一個性能對比測試程序，隨機生成 10000 個數(shù)組，每個數(shù)組中包含 200 個數(shù)據(jù)，然后在我的機器上分別用冒泡和插入排序算法來排序，冒泡排序算法大約 700ms 才能執(zhí)行完成，而插入排序只需要 100ms 左右就能搞定！

所以，雖然冒泡排序和插入排序在時間復(fù)雜度上是一樣的，都是 $O(n^2)$ ，但是如果我們希望把性能優(yōu)化做到極致，那肯定首選插入排序。插入排序的算法思路也有很大的優(yōu)化空間，我們只是講了最基礎(chǔ)的一種。如果你對插入排序的優(yōu)化感興趣，可以自行學(xué)習(xí)一下希爾排序。

內(nèi)容小結(jié)

要想分析、評價一個排序算法，需要從執(zhí)行效率、內(nèi)存消耗和穩(wěn)定性三個方面來看。因此，這一節(jié)，我?guī)惴治隽巳N時間復(fù)雜度是 $O(n^2)$ 的排序算法，冒泡排序、插入排序、選擇排序。你需要重點掌握的是它們的分析方法。

這三種時間復(fù)雜度為 O(n2) 的排序算法中，冒泡排序、選擇排序，可能就純粹停留在理論的層面了，學(xué)習(xí)的目的也只是為了開拓思維，實際開發(fā)中應(yīng)用并不多，但是插入排序還是挺有用的。后面講排序優(yōu)化的時候，我會講到，有些編程語言中的排序函數(shù)的實現(xiàn)原理會用到插入排序算法。

今天講的這三種排序算法，實現(xiàn)代碼都非常簡單，對于小規(guī)模數(shù)據(jù)的排序，用起來非常高效。但是在大規(guī)模數(shù)據(jù)排序的時候，這個時間復(fù)雜度還是稍微有點高，所以我們更傾向于用下一節(jié)要講的時間復(fù)雜度為 O(nlogn) 的排序算法。

課后思考

我們講過，特定算法是依賴特定的數(shù)據(jù)結(jié)構(gòu)的。我們今天講的幾種排序算法，都是基于數(shù)組實現(xiàn)的。如果數(shù)據(jù)存儲在鏈表中，這三種排序算法還能工作嗎？如果能，那相應(yīng)的時間、空間復(fù)雜度又是多少呢？

經(jīng)典評論

對于老師所提課后題，覺得應(yīng)該有個前提，是否允許修改鏈表的節(jié)點value值，還是只能改變節(jié)點的位置。一般而言，考慮只能改變節(jié)點位置，冒泡排序相比于數(shù)組實現(xiàn)，比較次數(shù)一致，但交換時操作更復(fù)雜；插入排序，比較次數(shù)一致，不需要再有后移操作，找到位置后可以直接插入，但排序完畢后可能需要倒置鏈表；選擇排序比較次數(shù)一致，交換操作同樣比較麻煩。綜上，時間復(fù)雜度和空間復(fù)雜度并無明顯變化，若追求極致性能，冒泡排序的時間復(fù)雜度系數(shù)會變大，插入排序系數(shù)會減小，選擇排序無明顯變化。

總結(jié)

一、排序方法與復(fù)雜度歸類
（1）幾種最經(jīng)典、最常用的排序方法：冒泡排序、插入排序、選擇排序、快速排序、歸并排序、計數(shù)排序、基數(shù)排序、桶排序。
（2）復(fù)雜度歸類
冒泡排序、插入排序、選擇排序 O(n^2)
快速排序、歸并排序 O(nlogn)
計數(shù)排序、基數(shù)排序、桶排序 O(n)

二、如何分析一個“排序算法”？
<1>算法的執(zhí)行效率

最好、最壞、平均情況時間復(fù)雜度。
時間復(fù)雜度的系數(shù)、常數(shù)和低階。
比較次數(shù)，交換（或移動）次數(shù)。
<2>排序算法的穩(wěn)定性
穩(wěn)定性概念：如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。
穩(wěn)定性重要性：可針對對象的多種屬性進行有優(yōu)先級的排序。
舉例：給電商交易系統(tǒng)中的“訂單”排序，按照金額大小對訂單數(shù)據(jù)排序，對于相同金額的訂單以下單時間早晚排序。用穩(wěn)定排序算法可簡潔地解決。先按照下單時間給訂單排序，排序完成后用穩(wěn)定排序算法按照訂單金額重新排序。
<3>排序算法的內(nèi)存損耗
原地排序算法：特指空間復(fù)雜度是O(1)的排序算法。

三、冒泡排序
冒泡排序只會操作相鄰的兩個數(shù)據(jù)。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關(guān)系要求，如果不滿足就讓它倆互換。
穩(wěn)定性：冒泡排序是穩(wěn)定的排序算法。
空間復(fù)雜度：冒泡排序是原地排序算法。
時間復(fù)雜度：

最好情況（滿有序度）：O(n)。
最壞情況（滿逆序度）：O(n^2)。
平均情況：
“有序度”和“逆序度”：對于一個不完全有序的數(shù)組，如4，5，6，3，2，1，有序元素對為3個（4，5），（4，6），（5，6），有序度為3，逆序度為12；對于一個完全有序的數(shù)組，如1，2，3，4，5，6，有序度就是n(n-1)/2，也就是15，稱作滿有序度；逆序度=滿有序度-有序度；冒泡排序、插入排序交換（或移動）次數(shù)=逆序度。
最好情況下初始有序度為n(n-1)/2，最壞情況下初始有序度為0，則平均初始有序度為n(n-1)/4，即交換次數(shù)為n(n-1)/4，因交換次數(shù)<比較次數(shù)<最壞情況時間復(fù)雜度，所以平均時間復(fù)雜度為O(n^2)。

四、插入排序
插入排序?qū)?shù)組數(shù)據(jù)分成已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個元素，即數(shù)組第一個元素。在未排序區(qū)間取出一個元素插入到已排序區(qū)間的合適位置，直到未排序區(qū)間為空。
空間復(fù)雜度：插入排序是原地排序算法。
時間復(fù)雜度：

最好情況：O(n)。
最壞情況：O(n^2)。
平均情況：O(n^2)（往數(shù)組中插入一個數(shù)的平均時間復(fù)雜度是O(n)，一共重復(fù)n次）。
穩(wěn)定性：插入排序是穩(wěn)定的排序算法。

五、選擇排序
選擇排序?qū)?shù)組分成已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間為空。每次從未排序區(qū)間中選出最小的元素插入已排序區(qū)間的末尾，直到未排序區(qū)間為空。
空間復(fù)雜度：選擇排序是原地排序算法。
時間復(fù)雜度：（都是O(n^2)）

最好情況：O(n^2)。
最壞情況：O(n^2)。
平均情況：O(n^2)。
穩(wěn)定性：選擇排序不是穩(wěn)定的排序算法。

思考
選擇排序和插入排序的時間復(fù)雜度相同，都是O(n^2)，在實際的軟件開發(fā)中，為什么我們更傾向于使用插入排序而不是冒泡排序算法呢？
答：從代碼實現(xiàn)上來看，冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動要復(fù)雜，冒泡排序需要3個賦值操作，而插入排序只需要1個，所以在對相同數(shù)組進行排序時，冒泡排序的運行時間理論上要長于插入排序。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

11 | 排序（上）：為什么插入排序比冒泡排序更受歡迎？

11 | 排序（上）：為什么插入排序比冒泡排序更受歡迎？

排序（上）：為什么插入排序比冒泡排序更受歡迎？

如何分析一個“排序算法”？

排序算法的執(zhí)行效率

1. 最好情況、最壞情況、平均情況時間復(fù)雜度

2. 時間復(fù)雜度的系數(shù)、常數(shù) 、低階

3. 比較次數(shù)和交換（或移動）次數(shù)

排序算法的內(nèi)存消耗

排序算法的穩(wěn)定性

插入排序（Insertion Sort）

選擇排序（Selection Sort）

解答開篇

內(nèi)容小結(jié)

課后思考

經(jīng)典評論

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

11 | 排序（上）：為什么插入排序比冒泡排序更受歡迎？

排序（上）：為什么插入排序比冒泡排序更受歡迎？

如何分析一個“排序算法”？

排序算法的執(zhí)行效率

1. 最好情況、最壞情況、平均情況時間復(fù)雜度

2. 時間復(fù)雜度的系數(shù)、常數(shù) 、低階

3. 比較次數(shù)和交換（或移動）次數(shù)

排序算法的內(nèi)存消耗

排序算法的穩(wěn)定性

插入排序（Insertion Sort）

選擇排序（Selection Sort）

解答開篇

內(nèi)容小結(jié)

課后思考

經(jīng)典評論

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

排序（上）：為什么插入排序比冒泡排序更受歡迎？

如何分析一個“排序算法”？

1. 最好情況、最壞情況、平均情況時間復(fù)雜度

2. 時間復(fù)雜度的系數(shù)、常數(shù) 、低階