歡迎光臨
每天分享高質量文章

小鹿講演演算法之三大排序演演算法:冒泡、插入、選擇

(給演演算法愛好者加星標,修煉程式設計內功

作者:小鹿 (本文來自作者投稿,簡介見末尾)

天分享的是三種排序演演算法,在面試、實際程式設計中經常會碰到和使用到的,我會帶領大家從分析排序演演算法技巧上以及程式碼實現上全面理解這一知識點的掌握。



一、如何分析一個「排序演演算法」


1. 執行效率


① 最好、最壞、平均時間複雜度

在分析演演算法的好壞時,要分別說出最好、最壞、平均時間複雜度的同時,也要說出最好、最壞時間複雜度對應排序的原始資料是什麼樣的。


② 複雜度繫數、常數、低階

時間複雜度反應的是資料規模 n 很大的時候的一個增長趨勢,它表示的時候會忽略繫數、常數、低階 ,小規模資料除外。


③ 比較次數和移動次數

基於比較的排序演演算法,在分析演演算法效率時,我們要考慮到元素的比較和元素的移動。


2. 記憶體消耗

演演算法的記憶體消耗可以透過空間複雜度來衡量,排序演演算法也不例外。我們取用一個名詞叫做「原地排序」,就是指特定空間複雜度是 O(1) 的排序演演算法。


3. 穩定性

如果待排序的序列中存在值相等的元素,經過排序之後,相等元素之間原有的先後順序不變,就叫做「穩定排序」。


二、氣泡排序


1、演演算法思想

每次冒泡對相鄰的兩個元素進行比較,看是否滿足大小關係,不滿足就進行互換,一次冒泡會讓至少一個元素移動到它應該在的位置。有 n 個資料,需要重覆 n 次。


2、演演算法最佳化

當某次冒泡過程已經沒有資料交換時,說明已經達到完全有序,不用再執行後續的冒泡操作。


3、程式碼實現

 1// 氣泡排序,a 表示陣列,n 表示陣列大小
2public void bubbleSort(int[] a, int n) {
3  if (n <= 1return;
4
5 for (int i = 0; i  6    // 提前退出冒泡迴圈的標誌位
7    boolean flag = false;
8    for (int j = 0; j 1; ++j) {
9      if (a[j] > a[j+1]) { // 交換
10        int tmp = a[j];
11        a[j] = a[j+1];
12        a[j+1] = tmp;
13        flag = true;  // 表示有資料交換      
14      }
15    }
16    if (!flag) break;  // 沒有資料交換,提前退出
17  }
18}


4、問題思考


①是否為原地排序

冒泡的過程只涉及相鄰資料的交換操作,只需要常量級的臨時空間,所以它的空間複雜度為 O(1),是一個原地排序演演算法。


②是否為穩定排序

在氣泡排序中,只有交換才可以改變兩個元素的前後順序。為了保證氣泡排序演演算法的穩定性,當有相鄰的兩個元素大小相等的時候,我們不做交換,相同大小的資料在排序前後不會改變順序,所以氣泡排序是穩定的排序演演算法。


③最好、最壞以及平均時間複雜度

最好的情況是資料已經排好序,我們只進行一次氣泡排序就可以了,最好時間複雜度為 O(n) 。最壞的情況是,要排序的資料剛好是倒序排列的,我們只進行 n 此冒泡操作,所以最壞的時間複雜度為  O(n²),平均時間複雜度為  O(n²)。


三、插入排序(Insertion Sort)


1、演演算法思想

我們將元素分為兩個區間,未排序區間和已排序區間。我們要做的就是在未排序區間取出元素與已排序區間元素進行比較插入到適當位置,以此類推,直到未排序區間元素為空為止(順序為從後向前比較


2、程式碼實現

 1// 插入排序,a 表示陣列,n 表示陣列大小(從小到大進行排序)
2public void insertionSort(int[] a, int n{
3  //如果陣列大小為 1 直接傳回
4  if (n <= 1return;
5  //否則進行插入排序
6  for (int i = 1; i  7    int value = a[i];
8    int j = i - 1;
9    // 查詢插入的位置
10    for (; j >= 0; --j) {
11      if (a[j] > value) {
12        a[j+1] = a[j];  // 資料移動
13      } else {
14        break;
15      }
16    }
17    a[j+1] = value// 插入資料
18  }
19}


3、問題思考


① 是否為原地排序?

答:插入排序的運算並不需要額外的儲存空間,所以空間複雜度是 O(1),是一個原地排序演演算法。


② 是否為穩定排序?

答:在插入排序中,對於值相同的元素,我們會將後邊出現的元素插入到前邊出現的元素的後邊,所以插入排序是穩定排序。


③ 最好、最壞、平均時間複雜度?

答:

最好的情況就是資料元素已經排好序,最好的時間複雜度為 O(1) ,


如果陣列是倒序的,每次插入都相當於在陣列的第一個位置插入新的資料,需要移動大量的資料,最壞的時間複雜度是 O(n²)。


我們在陣列中插入資料的平均時間複雜度為 O(n),對於插入排序來說我們每次就相當於陣列插入一個新的資料,迴圈執行n次插入資料,所以平均時間複雜度為 O(n²)。


四、選擇排序


1、演演算法思想

和插入排序有點相似,將在未排序期間尋找到最小的資料,並將其放到已排好區間的元素的尾部。


2、問題思考


① 是否為原地排序

因為,陣列中的兩個元素需要相互交換,需要用一個變數來儲存交換值,選擇排序的空間複雜度為O(1),所以,是一種原地排序演演算法。


② 是否為穩定排序

選擇排序每次都要找到剩餘未排序元素的最小值,並和前邊的元素交換位置,這樣破壞了穩定性。所以說,選擇排序是一種不穩定的排序演演算法。


③ 最好、最壞以及平均時間複雜度

選擇排序的最好情況就是已經是一組有序資料,最好的時間複雜度為 O(1),最壞的情況就是 O(n²)。平均時間複雜度就是 O(n²)。


3、程式碼實現

 1// 選擇排序,a表示陣列,n表示陣列大小
2  public static void selectionSort(int[] a, int n) {
3    if (n <= 1return;
4    for (int i = 0; i  5      // 查詢最小值
6      int minIndex = i;
7      int minValue = a[i];
8      for (int j = i; j  9        if (a[j] 10          minValue = a[j];
11    for (int i = 0; i 1; ++i) {
12      // 查詢最小值
13      int minIndex = i;
14      for (int j = i + 1; j 15        if (a[j] 16          minIndex = j;
17        }
18      }
19      if (minIndex == i)
20        continue;
21      // 交換
22      int tmp = a[i];
23      a[i] = a[minIndex];
24      a[minIndex] = tmp;
25    }
26  }


五、實際應用中為什麼插入排序應用最為廣泛


氣泡排序不管怎麼最佳化,元素交換的次數是一個固定值,是原始資料的逆序度。插入排序是同樣的,不管怎麼最佳化,元素移動的次數也等於原始資料的逆序度。


從程式碼實現上來看,氣泡排序的資料交換要比插入排序的資料移動要複雜,氣泡排序需要 3 個賦值操作,而插入排序只需要 1 個。


 1氣泡排序中資料的交換操作:
2if (a[j] > a[j+1]) { // 交換
3   int tmp = a[j];
4   a[j] = a[j+1];
5   a[j+1] = tmp;
6   flag = true;
7}
8
9插入排序中資料的移動操作:
10if (a[j] > value) {
11  a[j+1] = a[j];  // 資料移動
12else {
13  break;
14}


有興趣的小夥伴可以編幾個資料自己測試一下。


雖然氣泡排序和插入排序在在時間複雜度上是一樣的,都是 O(n²),我們希望把效能最佳化做到極致,首選插入排序。


六、重點掌握


今天重點掌握的內容是三種排序的「分析方法」,不必要死記硬背。另一個方面就是實際應用中用到最多就是「插入排序」。


七、擴充套件思考


上述小鹿講到的是用陣列實現的排序,加入我們將陣列換成連結串列,以上的分析方法是否還適合?以及最好、最壞、平均時間複雜度改變了沒有?

【本文作者】

小鹿:從學渣堆裡爬出來的,從此走上了一條「不甘平凡」的自學碼農之路。公眾號以分享程式設計學習方法和學習技巧以及資料結構與演演算法、Android、前端後臺等技術。一直堅信程式設計沒有捷徑可走,有付出才有回報。

推薦閱讀

(點選標題可跳轉閱讀)

漫畫演演算法:以後在有面試官問你 AVL 樹,你就把這篇文章扔給他

漫畫演演算法:什麼是外部排序?

漫畫:什麼是計數排序?

覺得本文有幫助?請分享給更多人

關註「演演算法愛好者」加星標,修煉程式設計內功

贊(0)

分享創造快樂

© 2024 知識星球   網站地圖