Sorting Algorithms

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

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 ]