我叫水水，很高興認(rèn)識(shí)大家！

這是專欄的第七篇文章。其實(shí)本專題已經(jīng)在我的公眾號(hào)(公眾號(hào)中不只有學(xué)習(xí)專題，還有很多大學(xué)學(xué)習(xí)資源分享、工具分享等等，文末有相關(guān)指路哦，歡迎關(guān)注撒~【微信搜索“CodingBugott”即可~】)中作為寒假學(xué)習(xí)專題持續(xù)更新了，所以想更新到知乎上，讓更多的小伙伴可以看到啦~

好了，說回正題，本次的主題是排序算法。

那么我們正式開始吧~

排序，可能是對于計(jì)算機(jī)相關(guān)專業(yè)的小伙伴而言，會(huì)學(xué)習(xí)到的第一個(gè)算法了。在平常的編碼中，我們也經(jīng)常會(huì)用到排序。因此排序算法的重要性顯而易見，而以下的篇幅便是簡略展開經(jīng)典的排序算法了。

而在學(xué)習(xí)算法之前，我們首先來看看應(yīng)該從哪幾個(gè)方面去評價(jià)、分析一個(gè)排序算法呢？以下有幾個(gè)方面可供參考。

1、排序算法的執(zhí)行效率：主要從其時(shí)間復(fù)雜度（系數(shù)、常數(shù)、低階還是高階）以及算法中的比較次數(shù)和交換次數(shù)；

2、排序算法的內(nèi)存消耗：粗略而言，也就是空間復(fù)雜度；

3、排序算法的穩(wěn)定性：針對排序算法，還有一個(gè)重要的度量指標(biāo)——穩(wěn)定性。這是指如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。舉個(gè)栗子，比如我們有一組數(shù)據(jù)3，8，4，6，7，3，按照大小排序之后就是3，3，4，6，7，8。這組數(shù)據(jù)里有兩個(gè)3。經(jīng)過某種排序算法排序之后，如果兩個(gè)3的前后順序沒有改變，那我們就把這種排序算法叫作穩(wěn)定的排序算法；如果前后順序發(fā)生變化，那對應(yīng)的排序算法就叫作不穩(wěn)定的排序算法。

以下開始簡單講解各類常用的排序算法。

冒泡排序（Bubble Sort）

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

舉個(gè)栗子，比如要對38，49，65，76，13，27，30，97進(jìn)行排序（見下圖），結(jié)合前面對于冒泡排序的定義，下圖中的“每一趟”代表著每一次冒泡，而每一次冒泡的過程其實(shí)也即是從數(shù)據(jù)首部開始，讓相鄰的兩個(gè)元素進(jìn)行比較，將其中較大的元素放在后面，然后依次進(jìn)行比較直至到達(dá)數(shù)據(jù)末端，即完成“一次冒泡”——將最大的元素放置于最后。然后依次類推，排除開最后的最大元素不參與排序外，其余元素繼續(xù)進(jìn)行新的一輪冒泡，重復(fù)上述操作。在n(n代表需要排序的元素個(gè)數(shù))次冒泡以后，完成排序。

那么我們下面我們看看代碼是如何實(shí)現(xiàn)的。

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

從以上代碼可以分析得出，

冒泡排序的空間復(fù)雜度為O(1)，即是一個(gè)原地排序算法。

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

而對于平均時(shí)間復(fù)雜度而言，下面我們來利用以下兩個(gè)新的概念——“有序度”和“逆序度”來分析一下：有序度是數(shù)組中具有有序關(guān)系的元素對的個(gè)數(shù)。比如 6，5，4，3，2，1，有序度是 0；對于一個(gè)完全有序的數(shù)組，比如 1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15。我們把這種完全有序的數(shù)組的有序度叫作滿有序度。逆序度的定義正好跟有序度相反（默認(rèn)從小到大為有序）。關(guān)于這三個(gè)概念，還可以得到一個(gè)公式：逆序度 = 滿有序度 - 有序度。因此排序的過程就是一種增加有序度，減少逆序度的過程，最后達(dá)到滿有序度，就說明排序完成了。

那我們回到冒泡排序中，它包含兩個(gè)操作原子，比較和交換。每交換一次，有序度就加 1。不管算法怎么改進(jìn)，交換次數(shù)總是確定的，即為逆序度，也就是[n*(n-1)/2–初始有序度]。

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

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

對于上面粗略的分析，學(xué)有余力的同學(xué)可以深入理解一下，實(shí)在理解不了的話，可以直接記憶結(jié)論【冒泡排序的平均時(shí)間復(fù)雜度為O(n2)】即可，就像站在巨人的肩膀上一樣。

插入排序（Insertion Sort）

顧名思義，這個(gè)排序算法是一個(gè)動(dòng)態(tài)排序的過程，即動(dòng)態(tài)地往有序集合中添加數(shù)據(jù)，我們可以通過遍歷數(shù)組，找到數(shù)據(jù)應(yīng)該插入的位置將其插入這種方法保持集合中的數(shù)據(jù)一直有序。而對于一組靜態(tài)數(shù)據(jù)，我們也可以借鑒上面講的插入方法，來進(jìn)行排序，于是就有了插入排序算法。

那該算法實(shí)際上到底是如何實(shí)現(xiàn)的呢？其實(shí)，首先將數(shù)組中的數(shù)據(jù)分為兩個(gè)區(qū)間，已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個(gè)元素，就是數(shù)組的第一個(gè)元素。插入算法的核心思想是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據(jù)一直有序。重復(fù)這個(gè)過程，直到未排序區(qū)間中元素為空，算法結(jié)束。

就拿上圖的排序作為例子，i表示每一輪排序的序號(hào)，括號(hào)內(nèi)的數(shù)據(jù)表示已排序區(qū)間，因此括號(hào)外表示未排序區(qū)間。然后在每一輪的排序中，取一個(gè)未排序區(qū)間中的元素，在已排序區(qū)間中通過遍歷找到合適的插入位置將其插入，以此保證已排序區(qū)間數(shù)據(jù)一直有序。重復(fù)該過程，直到未排序區(qū)間中元素為空，排序結(jié)束。

那么我們下面我們看看代碼是如何實(shí)現(xiàn)的。

1// 插入排序，a 表示數(shù)組，n 表示數(shù)組大小2public void insertionSort(int[] a, int n) {3 if (n <= 1) return; 4 for (int i = 1; i < n; ++i) {5 int value = a[i];6 int j = i - 1;7 // 查找插入的位置8 for (; j >= 0; --j) {9 if (a[j] > value) { 10 a[j+1] = a[j]; // 數(shù)據(jù)移動(dòng) 11 } else { 12 break; 13 } 14 } 15 a[j+1] = value; // 插入數(shù)據(jù) 16 } 17}

同樣的，從以上代碼可以分析得出，

插入排序算法的運(yùn)行并不需要額外的存儲(chǔ)空間，即空間復(fù)雜度是O(1)——原地排序算法。

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

插入排序的每次插入操作(平均時(shí)間復(fù)雜度是O(n))都相當(dāng)于在數(shù)組中插入一個(gè)數(shù)據(jù)，循環(huán)執(zhí)行 n 次插入操作，所以平均時(shí)間復(fù)雜度為O(n2)。

選擇排序（Selection Sort）

選擇排序算法的實(shí)現(xiàn)思路類似插入排序，也分已排序區(qū)間和未排序區(qū)間。但是選擇排序每次會(huì)從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間中的尾部。具體的實(shí)現(xiàn)步驟就不做多解釋了，可以結(jié)合下圖進(jìn)行學(xué)習(xí)理解。

同樣的，選擇排序空間復(fù)雜度為 O(1)，是一種原地排序算法。選擇排序的平均情況時(shí)間復(fù)雜度為O(n2)。但是需要注意的是，選擇排序是一種不穩(wěn)定的排序算法。從圖中可以看出，選擇排序每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩(wěn)定性。

歸并排序（Merge Sort）

對于如何對一個(gè)數(shù)組進(jìn)行排序，其實(shí)我們先把數(shù)組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了。比如下圖的這個(gè)例子：

歸并排序使用的就是分治思想。分治，顧名思義，就是分而治之，將一個(gè)大問題分解成小的子問題來解決。小的子問題解決了，大問題也就解決了。

不難看出，分治思想跟遞歸思想很像，分治是一種解決問題的處理思想，遞歸是一種編程技巧，分治算法一般都是用遞歸來實(shí)現(xiàn)的。

那么我們下面我們看看代碼是如何實(shí)現(xiàn)的。

1//以下為偽代碼展示，僅供參考2merge(A[p...r], A[p...q], A[q+1...r]) {3 var i := p，j := q+1，k := 0 // 初始化變量 i, j, k4 var tmp := new array[0...r-p] // 申請一個(gè)大小跟 A[p...r] 一樣的臨時(shí)數(shù)組5 while i<=q AND j<=r do {6 if A[i] <= A[j] {7 tmp[k++] = A[i++] // i++ 等于 i:=i+18 } else {9 tmp[k++] = A[j++] 10 } 11 } 12 13 // 判斷哪個(gè)子數(shù)組中有剩余的數(shù)據(jù) 14 var start := i，end := q 15 if j<=r then start := j, end:=r 16 17 // 將剩余的數(shù)據(jù)拷貝到臨時(shí)數(shù)組 tmp 18 while start <= end do { 19 tmp[k++] = A[start++] 20 } 21 22 // 將 tmp 中的數(shù)組拷貝回 A[p...r] 23 for i:=0 to r-p do { 24 A[p+i] = tmp[i] 25 } 26}

同樣的，從以上代碼可以分析得出，歸并排序保證了值相同的元素，在合并前后的先后順序不變。所以，歸并排序是一個(gè)穩(wěn)定的排序算法。而歸并排序的時(shí)間復(fù)雜度是 O(nlogn)，在此不作過多推導(dǎo)。

快速排序（Quick Sort）

簡稱“快排”。它利用的也是分治思想。但與歸并排序的思路卻完全不一樣。

快排的思想是這樣的：如果要排序數(shù)組中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)，我們選擇 p 到r 之間的任意一個(gè)數(shù)據(jù)作為 pivot（分區(qū)點(diǎn)）。

我們遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過這一步驟之后，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個(gè)部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的。

根據(jù)分治、遞歸的處理思想，我們可以用遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1 到r 之間的數(shù)據(jù)，直到區(qū)間縮小為 1，就說明所有的數(shù)據(jù)都有序了。就像下圖所示。

那么我們下面我們看看代碼是如何實(shí)現(xiàn)的。

1//以下為偽代碼展示，僅供參考2//快速排序，A 是數(shù)組，n 表示數(shù)組的大小3quick_sort(A, n) {4 quick_sort_c(A, 0, n-1)5}6// 快速排序遞歸函數(shù)，p,r 為下標(biāo)7quick_sort_c(A, p, r) {8 if p >= r then return9 10 q = partition(A, p, r) // 獲取分區(qū)點(diǎn) 11 quick_sort_c(A, p, q-1) 12 quick_sort_c(A, q+1, r) 13} 14partition(A, p, r) { 15 pivot := A[r] 16 i := p 17 for j := p to r-1 do { 18 if A[j] < pivot { 19 swap A[i] with A[j] 20 i := i+1 21 } 22 } 23 swap A[i] with A[r] 24 return i 25}

現(xiàn)在來分析一下快速排序的性能。其實(shí)，從其實(shí)現(xiàn)原理我們不難得出，快排是一種原地、不穩(wěn)定的排序算法。快排也是用遞歸來實(shí)現(xiàn)的，其時(shí)間復(fù)雜度求解較為復(fù)雜在此也不做深究，只需要知道它的時(shí)間復(fù)雜度也是O(nlogn)即可。

桶排序（Bucket Sort）

桶排序，顧名思義，會(huì)用到“桶”，核心思想是將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行排序。桶內(nèi)排完序之后，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了。就像下圖的例子一樣。

如果要排序的數(shù)據(jù)有 n 個(gè)，我們把它們均勻地劃分到 m 個(gè)桶內(nèi)，每個(gè)桶里就有 k=n/m 個(gè)元素。每個(gè)桶內(nèi)部使用快速排序，時(shí)間復(fù)雜度為 O(k * logk)。m 個(gè)桶排序的時(shí)間復(fù)雜度就是 O(m * k * logk)，因?yàn)?k=n/m，所以整個(gè)桶排序的時(shí)間復(fù)雜度就是 O(n*log(n/m))。當(dāng)桶的個(gè)數(shù) m 接近數(shù)據(jù)個(gè)數(shù) n 時(shí)，log(n/m) 就是一個(gè)非常小的常量，這個(gè)時(shí)候桶排序的時(shí)間復(fù)雜度接近 O(n)。

實(shí)際上，桶排序?qū)σ判驍?shù)據(jù)的要求是非常苛刻的，因此使用范圍上并沒有前幾種廣泛。桶排序比較適合用在外部排序中。所謂的外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤中，數(shù)據(jù)量比較大，內(nèi)存有限，無法將數(shù)據(jù)全部加載到內(nèi)存中。

小練習(xí)

Questions：

1//（1） 給出適用于計(jì)數(shù)排序的存儲(chǔ)結(jié)構(gòu)定義;2int[] arr = { 78, 48, 41, 74, 50, 40, 21, 16 }; //整型數(shù)組arr用于存儲(chǔ)待排序數(shù)表3int[] sortedArr = new int[arr.length]; //數(shù)組sortedArr大小與待排序數(shù)組一樣大，用于存儲(chǔ)排序完成了的數(shù)組4//（2） 實(shí)現(xiàn)計(jì)數(shù)排序的算法;5public static int[] countSorting(int[] arr) { //傳入?yún)?shù)為待排序的數(shù)組arr6 int[] sortedArr = new int[arr.length]; //定義與待排序數(shù)組一樣大，用于存儲(chǔ)排序完成的數(shù)組7 for (int i = 0; i < arr.length; i++) { //對參數(shù)數(shù)組每個(gè)元素走一趟8 //定義計(jì)數(shù)器，用于存儲(chǔ)數(shù)組中元素比當(dāng)前元素小的元素個(gè)數(shù)9 int count = 0; 10 //對于當(dāng)前元素尋找找出該數(shù)組中元素比當(dāng)前元素小的元素個(gè)數(shù) 11 for (int j = 0; j < arr.length; j++) 12 if (arr[i] > arr[j]) //通過if語句判斷大小 13 count++; //若符合要求，計(jì)數(shù)器+1 14 //內(nèi)循環(huán)完成后，計(jì)數(shù)器的值即為排序后的數(shù)組元素的下標(biāo) 15 sortedArr[count] = arr[i]; 16 } 17 return sortedArr; 18} 19//（3） 對于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是多少? 20//該問題的本質(zhì)即是詢問本方法的時(shí)間復(fù)雜度，而由該方法體描述可知，對于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是【n2】次。

---

本次排序算法專題

就完整結(jié)束啦

下期的主題將是查找算法

祝學(xué)習(xí)愉快鴨~

總結(jié)

以上是生活随笔為你收集整理的归并排序执行次数_肯定能懂的常见算法讲解(1)——排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。