野生前端的數據結構練習（9）冒泡排序，選擇排序，插入排序

[TOC]

一.冒泡排序

bubble sort的是最基本的算法，被譽為永遠會被考從來不被用的算法，基本原則是大數右移，每輪遍歷后最右側的數是最大的，所以下一輪循環時可不予考慮，時間復雜度為O（n^2）。

function bubbleSort(arr) {
    let length = arr.length;
    for(let i = length - 1; i > 1; i--){
        for(let j = 0; j < i ;j++){
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
            }
        }
    }
}

function swap(arr, a, b) {
    let temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

二.選擇排序

selection sort的基本原則是把數放在對的位置上，外層遍歷依次指向每個位置，內層遍歷從剩余的元素中尋找最小值放在該位置，時間復雜度O(n^2)。

/**
 * 選擇排序示例代碼
 */
function selectionSort(arr) {
    let length = arr.length;
    for(let pos = 0 ; pos < length ; pos++){
        let tempMin = pos;//用于記錄當前內層循環找到的最小值的下標
        for(let j = pos+1 ; j < length ;j++){
            if (arr[j] < arr[tempMin]) {
                tempMin = j;
            }
        }
        swap(arr, pos, tempMin);
    }
}

function swap(arr, a, b) {
    let temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

三.插入排序

insertion sort的基本原則是小數左移，即每輪循環結束后，外層循環指向位置左側的片段都是已經完成排序的，時間復雜度也為O(n^2)。

/**
 * 插入排序示例代碼
 */
function insertionSort(arr) {
    let length = arr.length;
    for(let pos = 1 ; pos < length ; pos++){
        for(let j = pos ; j > 0 ; j--){
            if (arr[j] < arr[j-1]) {
                swap(arr, j, j-1);
            }
        }
    }
}

function swap(arr, a, b) {
    let temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

四. 一些需要注意的點

1.運行時間

時間復雜度僅僅代表算法本身隨計算規模的增長時其自身運算量的增長速度，是一種抽象數學符號表達，并不代表程序的運行時間，在程序中對比測試3種算法時，其運行時間可能出現較大差異，這并不影響其在算法分析層面的時間復雜度定義。

2.基本優化

基于時間復雜度與程序運行效率并不絕對一致這樣的前提，上面的三種基本算法在不改變算法思想的前提下仍然存在優化空間，例如基礎插入排序中，內層循環所做的工作可以描述為為當前元素在左側已排序列中找到正確的位置，換句話說，找到正確位置之前，通過swap( )方法交換相鄰元素的位置的動作是可以不必執行的。

當針對更大的問題規模時，從基本算法出發，融入其他諸如“分治”，“減治”的思想，就可以得到更高級的算法，時間復雜度也更低。

3. 如何區分三種基礎排序算法

對于三種基本排序算法還不是很清楚的讀者，可以自行搜索“圖解算法”相關的博文進行查看，這三種算法的時間復雜度是一樣的（都是兩層循環），只需要區分其主要排序思想的原則差異，并不難記憶。

• 冒泡排序——大數右移
• 選擇排序——按位入坑
• 選擇排序——小數左移