Sorting Algorithms

排序演算法在程序中是非常重要的以下会先来介绍三个基本的排序演算法

• Bubble sort
• Insertion sort
• Selection sort

Bubble Sort Big(n^2)

BubbleSort.gif

let array = [3,5,1,0,-1]

function bubbleSort(arr){
    let temp = []
    for(let i = 0; i <= arr.length-1; i++){
        for(let j = 0; j <= arr.length-1; j++){
            if(arr[j-1] > arr[j]){ //对比前项若比後项大
                temp = arr[j] //空阵列存小的
                arr[j] = arr[j-1] //把大的丢给正确位置
                arr[j-1] = temp //再把小的传给[j-1]
            }
        }
    }return arr
}
console.log(bubbleSort(array)) //[ -1, 0, 1, 3, 5 ]

Insertion Sort BigO(n^2)

InsertSort.gif

-在排序过程中,Insertion sort must sorted

let array = [3,5,1,0,-1]

function InsertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let key = arr[i] //arr[i-1] sorted 所以要用arr[i] compare
        let j = i - 1 //j == 0
        
        while(j >= 0 && arr[j] > key){  //逐一比对是否前项比後项大
            arr[j + 1] = arr[j] //这边使用了把每项index往前推
            j-- //--再往後比对
        }
        arr[j + 1] = key //最後空出的空间塞入key的数值
        console.log(arr)
    } 
    return arr 
}

console.log(InsertionSort(array))
/*
[ 3, 5, 1, 0, -1 ]
[ 1, 3, 5, 0, -1 ]
[ 0, 1, 3, 5, -1 ]
[ -1, 0, 1, 3, 5 ]
[ -1, 0, 1, 3, 5 ]
*/

Selection Sort BigO(n^2)

SelecionSort

let array = [3,5,1,0,-1]

function SelectionSort(arr){
    for(let i = 0; i < arr.length; i++){
        let minIndex = i
        let temp  = []
        for(let j = i; j < arr.length; j++){
            if(arr[minIndex] > arr[j]){
                minIndex = j
            }
        }
        temp = arr[minIndex] //save minIndex
        arr[minIndex] = arr[i]  //swap
        arr[i] = temp //root index = minIndex
    }
    return arr
}
console.log(SelectionSort(array))//[ -1, 0, 1, 3, 5 ]