目錄

?

排序算法執(zhí)行效率的分析，從這幾個方面來衡量

冒泡排序（Bubble Sort）

性能分析：

插入排序（Insertion Sort）

性能分析：

選擇排序（Selection Sort）

性能分析：

冒泡排序、插入排序、選擇排序三者比較

歸并排序

性能分析：

快速排序

性能分析：

快排和歸并的對比

桶排序（Bucket sort）

計數(shù)排序（Counting sort）

約束條件：

基數(shù)排序（Radix sort）

約束條件

---

排序算法執(zhí)行效率的分析，從這幾個方面來衡量

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

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

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

?

原地排序（Sorted in place）。原地排序算法，就是特指空間復(fù)雜度是 O(1) 的排序算法

排序算法的穩(wěn)定性：如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變，如果兩個 3 的前后順序沒有改變，那我們就把這種排序算法叫作穩(wěn)定的排序算法

?

冒泡排序（Bubble Sort）

?

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

// 冒泡排序，a表示數(shù)組，n表示數(shù)組大小 public void bubbleSort(int[] a, int n) {if (n <= 1) return;for (int i = 0; i < n; ++i) {// 提前退出冒泡循環(huán)的標志位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ù)交換，提前退出} }

性能分析：

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

2、冒泡排序中，只有交換才可以改變兩個元素的前后順序，所以冒泡排序是穩(wěn)定的排序算法

3、時間復(fù)雜度：最好情況下，要排序的數(shù)據(jù)已經(jīng)是有序的了，只需要進行一次冒泡操作，就可以結(jié)束了，所以最好情況時間復(fù)雜度是 O(n)。

而最壞的情況是，要排序的數(shù)據(jù)剛好是倒序排列的，需要進行 n 次冒泡操作，所以最壞情況時間復(fù)雜度為 O(n^2)。

?

插入排序（Insertion Sort）

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

插入排序也包含兩種操作，一種是元素的比較，一種是元素的移動。

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

代碼如下

// 插入排序，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ù)} }

性能分析：

1、插入排序算法的運行并不需要額外的存儲空間，所以空間復(fù)雜度是 O(1)，也就是說，這是一個原地排序算法

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

3、如果從尾到頭在有序數(shù)據(jù)組里面查找插入位置，這種情況下，最好是時間復(fù)雜度為 O(n)

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

?

選擇排序（Selection Sort）

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

性能分析：

1、選擇排序空間復(fù)雜度為 O(1)，是一種原地排序算法

2、選擇排序的最好情況時間復(fù)雜度、最壞情況和平均情況時間復(fù)雜度都為 O(n^2)

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

?

冒泡排序、插入排序、選擇排序三者比較

?

歸并排序

歸并排序的核心思想：如果要排序一個數(shù)組，先把數(shù)組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個數(shù)組就都有序了。

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

如圖所示，申請一個臨時數(shù)組 tmp，大小與 A[p...r]相同。用兩個游標 i 和 j，分別指向 A[p...q]和 A[q+1...r]的第一個元素。比較這兩個元素 A[i]和 A[j]，如果 A[i]<=A[j]，就把 A[i]放入到臨時數(shù)組 tmp，并且 i 后移一位，否則將 A[j]放入到數(shù)組 tmp，j 后移一位。繼續(xù)上述比較過程，直到其中一個子數(shù)組中的所有數(shù)據(jù)都放入臨時數(shù)組中，再把另一個數(shù)組中的數(shù)據(jù)依次加入到臨時數(shù)組的末尾，這個時候，臨時數(shù)組中存儲的就是兩個子數(shù)組合并之后的結(jié)果了。最后再把臨時數(shù)組 tmp 中的數(shù)據(jù)拷貝到原數(shù)組 A[p...r]中。

性能分析：

1、歸并排序是一個穩(wěn)定的排序算法，在合并前后的先后順序不變

2、歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序程度無關(guān)，所以其時間復(fù)雜度是非常穩(wěn)定的，不管是最好情況、最壞情況，還是平均情況，時間復(fù)雜度都是 O(nlogn)。

3、歸并排序不是原地排序算法?？臻g復(fù)雜度為O(n)

盡管每次合并操作都需要申請額外的內(nèi)存空間，但在合并完成之后，臨時開辟的內(nèi)存空間就被釋放掉了。在任意時刻，CPU 只會有一個函數(shù)在執(zhí)行，也就只會有一個臨時的內(nèi)存空間在使用。臨時內(nèi)存空間最大也不會超過 n 個數(shù)據(jù)的大小，所以空間復(fù)雜度是 O(n)。

?

快速排序

快排的思想：如果要排序數(shù)組中下標從 p 到 r 之間的一組數(shù)據(jù)，選擇 p 到 r 之間的任意一個數(shù)據(jù)作為 pivot（分區(qū)點）。遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過這一步驟之后，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的。

性能分析：

1、原地排序算法

2、不穩(wěn)定的排序算法

3、T(n) 在大部分情況下的時間復(fù)雜度都可以做到 O(nlogn)，只有在極端情況下，才會退化到 O(n2)

?

快排和歸并的對比

1、處理方式：歸并排序的處理過程是由下到上的，先處理子問題，然后再合并。而快排正好相反，它的處理過程是由上到下的，先分區(qū)，然后再處理子問題

2、歸并排序雖然是穩(wěn)定的、時間復(fù)雜度為 O(nlogn) 的排序算法，但是它是非原地排序算法，主要原因是合并函數(shù)無法在原地執(zhí)行

快速排序通過設(shè)計巧妙的原地分區(qū)函數(shù)，可以實現(xiàn)原地排序，解決了歸并排序占用太多內(nèi)存的問題。

3、歸并排序算法是一種在任何情況下時間復(fù)雜度都比較穩(wěn)定的排序算法，這也使它存在致命的缺點，即歸并排序不是原地排序算法，空間復(fù)雜度比較高，是 O(n)。正因為此，它也沒有快排應(yīng)用廣泛。

快速排序算法雖然最壞情況下的時間復(fù)雜度是 O(n2)，但是平均情況下時間復(fù)雜度都是 O(nlogn)。不僅如此，快速排序算法時間復(fù)雜度退化到 O(n2) 的概率非常小，可以通過合理地選擇 pivot 來避免這種情況。

?

桶排序（Bucket sort）

核心思想：將要排序的數(shù)據(jù)分到幾個有序的桶里，每個桶里的數(shù)據(jù)再單獨進行排序。桶內(nèi)排完序之后，再把每個桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了。

約束條件：

1、要排序的數(shù)據(jù)需要很容易就能劃分成 m 個桶，并且，桶與桶之間有著天然的大小順序。這樣每個桶內(nèi)的數(shù)據(jù)都排序完之后，桶與桶之間的數(shù)據(jù)不需要再進行排序

2、數(shù)據(jù)在各個桶之間的分布是比較均勻的，如果數(shù)據(jù)經(jīng)過桶的劃分之后，有些桶里的數(shù)據(jù)非常多，有些非常少，很不平均，那桶內(nèi)數(shù)據(jù)排序的時間復(fù)雜度就不是常量級了

3、桶排序比較適合用在外部排序中，所謂的外部排序就是數(shù)據(jù)存儲在外部磁盤中，數(shù)據(jù)量比較大，內(nèi)存有限，無法將數(shù)據(jù)全部加載到內(nèi)存中。

時間復(fù)雜度：O(n)

?

計數(shù)排序（Counting sort）

計數(shù)排序其實是桶排序的一種特殊情況。當要排序的 n 個數(shù)據(jù)，所處的范圍并不大的時候，比如最大值是 k，就可以把數(shù)據(jù)劃分成 k 個桶。每個桶內(nèi)的數(shù)據(jù)值都是相同的，省掉了桶內(nèi)排序的時間。

比如給50萬考生排名，考生的滿分是 900 分，最小是 0 分，這個數(shù)據(jù)的范圍很小，所以我們可以分成 901 個桶，實現(xiàn)計數(shù)排序，桶排序的粒度就不一定那么細了，可以分為0-10分為一桶，11-20為一桶

// 計數(shù)排序，a是數(shù)組，n是數(shù)組大小。假設(shè)數(shù)組中存儲的都是非負整數(shù)。 public void countingSort(int[] a, int n) {if (n <= 1) return;// 查找數(shù)組中數(shù)據(jù)的范圍int max = a[0];for (int i = 1; i < n; ++i) {if (max < a[i]) {max = a[i];}}int[] c = new int[max + 1]; // 申請一個計數(shù)數(shù)組c，下標大小[0,max]for (int i = 0; i <= max; ++i) {c[i] = 0;}// 計算每個元素的個數(shù)，放入c中for (int i = 0; i < n; ++i) {c[a[i]]++;}// 依次累加for (int i = 1; i <= max; ++i) {c[i] = c[i-1] + c[i];}// 臨時數(shù)組r，存儲排序之后的結(jié)果int[] r = new int[n];// 計算排序的關(guān)鍵步驟，有點難理解for (int i = n - 1; i >= 0; --i) {int index = c[a[i]]-1;r[index] = a[i];c[a[i]]--;}// 將結(jié)果拷貝給a數(shù)組for (int i = 0; i < n; ++i) {a[i] = r[i];} }

約束條件：

計數(shù)排序只能用在數(shù)據(jù)范圍不大的場景中，如果數(shù)據(jù)范圍 k 比要排序的數(shù)據(jù) n 大很多，就不適合用計數(shù)排序了。而且，計數(shù)排序只能給非負整數(shù)排序，如果要排序的數(shù)據(jù)是其他類型的，要將其在不改變相對大小的情況下，轉(zhuǎn)化為非負整數(shù)。

?

基數(shù)排序（Radix sort）

給上面數(shù)據(jù)排序，先按照最后一位來排序字符，然后，再按照倒數(shù)第二位重新排序，以此類推，最后按照第一位重新排序。經(jīng)過 3次排序之后，字符就都有序了

約束條件

基數(shù)排序?qū)σ判虻臄?shù)據(jù)是有要求的，需要可以分割出獨立的“位”來比較，而且位之間有遞進的關(guān)系，如果 a 數(shù)據(jù)的高位比 b 數(shù)據(jù)大，那剩下的低位就不用比較了。除此之外，每一位的數(shù)據(jù)范圍不能太大，要可以用線性排序算法來排序，否則，基數(shù)排序的時間復(fù)雜度就無法做到 O(n) 了。

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的数据结构排序学习总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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