選擇排序

今天給大家介紹另一種算法：選擇排序。選擇排序是非常簡單，但是并不算很快的一種排序。之所以講這個，是為了更好的更快的入門后續(xù)的算法知識。

直接上代碼

// 從小到大排序
function selectionSort(arr){
    let temp, minIndex
    for(let i = 0; i < arr.length - 1; i++){
        minIndex = i
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[minIndex] > arr[j]) {
                minIndex = j
            }
        }
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp

    }
    return arr
}

代碼解釋

所謂選擇，就是每次用當(dāng)前的數(shù)字跟剩下的數(shù)字逐個進(jìn)行對比，挑選出最小或者最大的數(shù)。
i = 0時，跟下標(biāo)為1及后面的逐個進(jìn)行比較，把最小的元素下標(biāo)記錄下來，與a[0]做位置交換，然后進(jìn)行下一輪比較；
i = 1時，跟下標(biāo)為2及后面的逐個進(jìn)行比較，把最小的元素下標(biāo)記錄下來，與a[1]做位置交換，然后進(jìn)行下一輪比較；

選擇排序.jpg

時間復(fù)雜度

對于這種算法，我們需要遍歷數(shù)組中的每一個元素時間復(fù)雜度為O(n)，并且，對于這個遍歷要執(zhí)行n次操作，因此時間復(fù)雜度是O(n²)，如無法理解，請看下圖：

選擇排序時間復(fù)雜度.jpg