最經(jīng)典、最常用的排序算法：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、計數(shù)排序、基數(shù)排序、桶排序。
按照時間復(fù)雜度把它們分成了三類：
如何分析一個“排序算法”？
-
一、排序算法的執(zhí)行效率
- 最好情況、最壞情況、平均情況時間復(fù)雜度
- 時間復(fù)雜度的系數(shù)、常數(shù) 、低階(實際開發(fā)中數(shù)據(jù)規(guī)模很小的時候不能忽略)
- 比較次數(shù)和交換（或移動）次數(shù)
二、排序算法的內(nèi)存消耗
針對排序算法的空間復(fù)雜度，引入了一個新的概念：原地排序算法，特指空間復(fù)雜度是
的排序算法。
- 三、排序算法的穩(wěn)定性
僅僅用執(zhí)行效率和內(nèi)存消耗來衡量排序算法的好壞是不夠的。針對排序算法，我們還有一個重要的度量指標(biāo)：穩(wěn)定性。這個概念是說，如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。
冒泡排序（Bubble Sort）
冒泡排序只會操作相鄰的兩個數(shù)據(jù)。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關(guān)系要求。如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應(yīng)該在的位置，重復(fù) n 次，就完成了 n 個數(shù)據(jù)的排序工作。
冒泡過程還可以優(yōu)化。當(dāng)某次冒泡操作已經(jīng)沒有數(shù)據(jù)交換時，說明已經(jīng)達到完全有序，不用再繼續(xù)執(zhí)行后續(xù)的冒泡操作。
三個問題：
- 第一，冒泡排序是原地排序算法嗎？
冒泡的過程只涉及相鄰數(shù)據(jù)的交換操作，只需要常量級的臨時空間，所以它的空間復(fù)雜度為 ，是一個原地排序算法。
- 第二，冒泡排序是穩(wěn)定的排序算法嗎？
冒泡排序中當(dāng)有相鄰的兩個元素大小相等的時候，我們不做交換，相同大小的數(shù)據(jù)在排序前后不會改變順序，所以冒泡排序是穩(wěn)定的排序算法。
- 第三，冒泡排序的時間復(fù)雜度是多少？
最好情況時間復(fù)雜度是 ；最壞情況時間復(fù)雜度為
。
那平均時間復(fù)雜是多少呢？平均時間復(fù)雜度就是加權(quán)平均期望時間復(fù)雜度，分析的時候要結(jié)合概率論的知識。
在這里如果用概率論方法定量分析平均時間復(fù)雜度，涉及的數(shù)學(xué)推理和計算就會很復(fù)雜。我這里還有一種思路，通過“有序度”和“逆序度”這兩個概念來進行分析。如下圖：
例如對于一個完全有序的數(shù)組，比如 1，2，3，4，5，6，有序度就是 ，也就是 15，我們把這種完全有序的數(shù)組的有序度叫作 滿有序度。
逆序度的定義正好跟有序度相反（默認從小到大為有序）。
關(guān)于這三個概念，我們還可以得到一個公式：逆序度 = 滿有序度 - 有序度。
我們排序的過程就是一種增加有序度，減少逆序度的過程，最后達到滿有序度，就說明排序完成了。
對于包含 n 個數(shù)據(jù)的數(shù)組進行冒泡排序，平均交換次數(shù)是多少呢？最壞情況下，初始狀態(tài)的有序度是 0，所以要進行 次交換。最好情況下，初始狀態(tài)的有序度是
，就不需要進行交換。我們可以取個中間值
，來表示初始有序度既不是很高也不是很低的平均情況。
換句話說，平均情況下，需要 次交換操作，比較操作肯定要比交換操作多，而復(fù)雜度的上限是
，所以平均情況下的時間復(fù)雜度就是
。
插入排序（Insertion Sort）
插入排序是如何來實現(xiàn)排序的呢？
首先，我們將數(shù)組中的數(shù)據(jù)分為兩個區(qū)間，已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個元素，就是數(shù)組的第一個元素。插入算法的核心思想是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據(jù)一直有序。重復(fù)這個過程，直到未排序區(qū)間中元素為空，算法結(jié)束。
插入排序也包含兩種操作，一種是元素的比較，一種是元素的移動。
對于不同的查找插入點方法（從頭到尾、從尾到頭），元素的比較次數(shù)是有區(qū)別的。但對于一個給定的初始序列，移動操作的次數(shù)總是固定的，就等于逆序度。
同樣三個問題：
- 第一，插入排序是原地排序算法嗎？
空間復(fù)雜度是 ，也就是說，這是一個原地排序算法。
- 第二，插入排序是穩(wěn)定的排序算法嗎？
在插入排序中，對于值相同的元素，我們可以選擇將后面出現(xiàn)的元素，插入到前面出現(xiàn)元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩(wěn)定的排序算法。
- 第三，插入排序的時間復(fù)雜度是多少？
最好是時間復(fù)雜度為 ；最壞情況時間復(fù)雜度為
；平均時間復(fù)雜度為
。
選擇排序（Selection Sort）
選擇排序算法的實現(xiàn)思路有點類似插入排序，也分已排序區(qū)間和未排序區(qū)間。但是選擇排序每次會從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間的末尾。
選擇排序空間復(fù)雜度為 ，是一種原地排序算法。選擇排序的最好情況時間復(fù)雜度、最壞情況和平均情況時間復(fù)雜度都為
。選擇排序是一種不穩(wěn)定的排序算法。
開篇解答
冒泡排序和插入排序的時間復(fù)雜度都是 ，都是原地排序算法，為什么插入排序要比冒泡排序更受歡迎呢？
不論冒泡排序還是插入排序，對于同一組數(shù)據(jù)，需要的元素交換的次數(shù)是一個固定值，即原始數(shù)據(jù)的逆序度。
但是從代碼實現(xiàn)上來看，冒泡排序的每次數(shù)據(jù)交換需要三個賦值操作，而插入排序只需要一個賦值操作，見下圖：
我們把執(zhí)行一個賦值語句的時間粗略地計為單位時間 （unit_time），然后分別用冒泡排序和插入排序?qū)ν粋€逆序度是 K 的數(shù)組進行排序。用冒泡排序，需要 K 次交換操作，每次需要 3 個賦值語句，所以交換操作總耗時就是 3*K 單位時間。而插入排序中數(shù)據(jù)移動操作只需要 K 個單位時間。
所以，雖然冒泡排序和插入排序在時間復(fù)雜度上是一樣的，都是 ，但是如果我們希望把性能優(yōu)化做到極致，那肯定首選插入排序。
插入排序的算法思路也有很大的優(yōu)化空間，上面只是最基礎(chǔ)的一種，詳細請看希爾排序。
內(nèi)容小結(jié)
要想分析、評價一個排序算法，需要從執(zhí)行效率、內(nèi)存消耗和穩(wěn)定性三個方面來看。
這一節(jié)，分析了三種時間復(fù)雜度是 的排序算法，冒泡排序、插入排序、選擇排序。需要重點掌握的是它們的分析方法。
這三種時間復(fù)雜度為 的排序算法中，冒泡排序、選擇排序，可能就純粹停留在理論的層面了，學(xué)習(xí)的目的也只是為了開拓思維，實際開發(fā)中應(yīng)用并不多，但是插入排序還是挺有用的。后面講排序優(yōu)化的時候，我會講到，有些編程語言中的排序函數(shù)的實現(xiàn)原理會用到插入排序算法。
這三種排序算法，實現(xiàn)代碼都非常簡單，對于小規(guī)模數(shù)據(jù)的排序，用起來非常高效。但是在大規(guī)模數(shù)據(jù)排序的時候，這個時間復(fù)雜度還是稍微有點高，接下來學(xué)習(xí)時間復(fù)雜度為 的排序算法。
課后思考
我們講過，特定算法是依賴特定的數(shù)據(jù)結(jié)構(gòu)的。我們今天講的幾種排序算法，都是基于數(shù)組實現(xiàn)的。如果數(shù)據(jù)存儲在鏈表中，這三種排序算法還能工作嗎？如果能，那相應(yīng)的時間、空間復(fù)雜度又是多少呢？
考慮只能改變節(jié)點位置。冒泡排序相比于數(shù)組實現(xiàn)，比較次數(shù)一致，但交換時操作更復(fù)雜；
插入排序，比較次數(shù)一致，不需要再有后移操作，找到位置后可以直接插入，但排序完畢后可能需要倒置鏈表；
選擇排序比較次數(shù)一致，交換操作同樣比較麻煩。
綜上，時間復(fù)雜度和空間復(fù)雜度并無明顯變化，若追求極致性能，冒泡排序的時間復(fù)雜度系數(shù)會變大，插入排序系數(shù)會減小，選擇排序無明顯變化。
