前端面試不會直接挂掉的題目--冒泡排序

在準備面試的過程中，我們往往容易陷入到很多難度比較高的題目中不能自拔，卻忽略了比較基礎的題目，面試官在不了解我們的情況下，剛開始可能會問我們一道比較基礎的算法題，比如資料結構，請問你能手寫下冒泡排序嗎？如果此時不會的話，可能直接結束面試了。哈哈~，讓我們今天來一起學習下這個比較簡單的排序算法吧~

什麼是冒泡排序？

冒泡排序指的是一種排序的思想，假如我們拿到一個數組，數組中是一堆無序的數字，冒泡排序就可以讓這堆無序的數字變得有序，之是以叫做冒泡排序而不是其他的XX排序，是因為冒泡排序的每一輪排序中都将最大的值置為了最後的位置上，就像冒泡一樣，是以取名為冒泡排序。

冒泡排序的思想

1. 排序的輪數是數組的長度-1.
2. 每一輪排序都将最大的值放在最末尾。
3. 下一輪排序需要比較的次數都要比上一輪少一次。

實作冒泡排序

function mySort(arr) {
    let temp;
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    console.log(arr);
    return arr;
}
mySort([8,9,7,3,2,6])
複制代碼      

時間複雜度和空間複雜度分析

• 空間複雜度

在空間上，我們隻定義了一個臨時變量進行交換使用，是以空間複雜度為O(1)。

• 時間複雜度

我們分析最差情況下的時間複雜度，假如數組是完全逆序排列的，時間複雜度為：3n(n-1)/2，是以平均時間複雜度為O(n^2).

冒泡排序的穩定性

在辨識冒泡排序是否是穩定排序之前，我們首先要知道什麼樣的算法算是一種穩定的算法。穩定的算法通俗的講就是假如兩個值是一樣的，排序前A在B的前面，排序後A還在B的前面，這樣的排序算法我們稱之為穩定的排序算法，反之稱為不穩定的排序算法，是以冒泡排序是穩定的。