冒泡排序_排序算法番外 冒泡排序

2021伊始，決定攻克一下資料結構與算法。在這裡帶着可愛的小夥伴們一起成長~

你會發現，現在還是在補大學那會逃掉的課程(?，想逃是逃不掉的，我們一起撸起袖子就是淦！)

我們慢慢來，每天進步一點點，最終會達到量變到質變的效果的！

接下來進入正題，先來搞一波這個經久不衰的排序算法。針對于前端，筆者重點關注面試中考察度較深的排序算法有以下 5 個。

• 基礎排序算法

1. 冒泡排序
2. 選擇排序
3. 插入排序

進階排序算法

1. 歸并排序
2. 快速排序

而本文我們先講一個最最基礎的，「冒泡排序」。

來了，來了，列車已進站，請抓緊扶手~

冒泡排序

基本思路分析

冒泡排序的過程，就是從第一個元素開始，「重複比較相鄰的兩個項」，若第一項比第二項更大，則交換兩者的位置；反之不動。每一輪操作，都會将這一輪中最大的元素放置到數組的末尾。假如數組的長度是

n

，那麼當我們重複完

n

輪的時候，整個數組就有序了。

基礎版的冒泡思路實作

基礎版的冒泡思路改進

在上面，你會發現其實我們 第 i 次 都會将最大的數字 排在 第

len - i

上，意味着之後不需要再去比較

len - i

之後的數值， 在這裡就值得我們去改進。

最優解法

在這裡大家想一下，如果是一個已經排好序的數組，那麼我們還需要進行兩層周遊麼，是不是可以達到O(n)的效率。

這裡就針對于這種情況作出最優的解法

标志位可以幫助我們在第一次冒泡的時候就定位到數組是否完全有序，進而節省掉不必要的判斷邏輯，将最好情況下的時間複雜度定向優化為

O(n)

。

「編碼複盤 -- 冒泡排序的時間複雜度」

我們分最好、最壞和平均來看：

• 「最好時間複雜度」：它對應的是數組本身有序這種情況。在這種情況下，我們隻需要作比較(n-1 次)，而不需要做交換。時間複雜度為 「O(n)」
• 「最壞時間複雜度」：它對應的是數組完全逆序這種情況。在這種情況下，每一輪内層循環都要執行，重複的總次數是 n(n-1)/2 次，是以時間複雜度是 「O(n^2)」
• 「平均時間複雜度」：這個東西比較難搞，它涉及到一些機率論的知識。實際面試的時候也不會有面試官摁着你讓你算這個，這裡記住平均時間複雜度是 「O(n^2)」 即可。

行文至此，願耐心的你已經将這個冒泡排序已經吃透，恭喜恭喜~