前端基礎演演算法題解法

程式碼均為自己手寫，如有錯誤或更優解法，勞煩小夥伴們指教哈~

1、斐波那契數列

// 解法一
function a (n, a1 = 1, a2 = 1) {
    if (n <= 1) return a1
    return a(n - 1, a2, a1 + a2)
}
let res = a(5)
console.log(res)

// 解法二
let a1 = 1, a2 = 1
function b (n) {
    if (n <= 1) return a
    for (let i = 0; i < (n - 2); i++) {
        let t = a2
        a2 = a1 + a2
        a1 = t
    }
    return a2
}
let res = b(5)
console.log(res)

2、氣泡排序

let arr = [2, 53, 32, 21, 432, 54, 76, 45, 654]

let l = arr.length
for (let i = 0; i < arr.length; i++) {
    for (let j = l - 1; j >= i; j--) {
        if (arr[j] > arr[j - 1]) {
            let t = arr[j]
            arr[j] = arr[j - 1]
            arr[j - 1] = t
        }
    }
}

console.log(arr)

3、選擇排序

let arr = [2, 53, 32, 21, 432, 54, 76, 45, 654]

let l = arr.length
for (let i = 0; i < l; i++) {
    let min = arr[i]
    let index = i
    for (let j = i; j < l; j++) {
        if (arr[j] < min) {
            min = arr[j]
            index = j
        }
    }
    if (index !== i) {
        arr[index] = arr[i]
        arr[i] = min
    }
}

console.log(arr)

4、插入排序

let arr = [2, 53, 32, 21, 432, 54, 76, 45, 654]

let l = arr.length
for (let i = 0; i < l; i++) {
    let index = i
    while (index >= 1 && arr[index] < arr[index - 1]) {
        let t = arr[index]
        arr[index] = arr[index - 1]
        arr[index - 1] = t
        index --
    }
}

console.log(arr)

5、希爾排序

let arr = [2, 53, 32, 21, 432, 54, 76, 45, 654]

let l = arr.length
let gap = Math.floor(l / 2)

for (gap; gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < l; i++) {
        let t = arr[i]
        let index = -1
        for (let j = i - gap; j > 0 && arr[j] > t; j -= gap) {
            arr[j + gap] = arr[j]
            index = j
        }
        if (index !== -1) {
            arr[index] = t
        }
    }
}

console.log(arr)

6、歸併排序

let arr = [89, 53, 32, 21, 432, 54, 76, 45, 654]

function mergeSort (arr) {
    if (arr.length <= 1) {
        return arr
    }
    let left = [], right = []
    for (let i = 0; i < arr.length / 2; i++) {
        left.push(arr.shift())
    }
    right = arr
    return merge(mergeSort(left), mergeSort(right))
}

function merge (left, right) {
    console.log(left, right)
    let list = []
    while (left.length > 0 && right.length > 0) {
        if (left[0] > right[0]) {
            list.push(right.shift())
        } else {
            list.push(left.shift())
        }
    } 
    while (left.length > 0) {
        list.push(left.shift())
    } 
    while (right.length > 0) {
        list.push(right.shift())
    }

    return list
}

let res = mergeSort(arr)
console.log(res)

7、快速排序

let arr = [89, 53, 32, 21, 432, 54, 76, 45, 654]

function quickSort (arr, left, right) {
    if (left >= right) {
        return
    }
    let i = left, j = right
    // 記錄當前基準值在左邊還是右邊
    let flag = 'left'
    while (i < j) {
        if (flag === 'left') {
            while (arr[i] < arr[j]) {
                j --
            }
            if (i < j) {
                let tmp = arr[i]
                arr[i] = arr[j]
                arr[j] = tmp
                flag = 'right'
                i ++
            }
        } else if (flag === 'right') {
            while (arr[i] < arr[j]) {
                i ++
            }
            if (i < j) {
                let tmp = arr[i]
                arr[i] = arr[j]
                arr[j] = tmp
                flag = 'left'
                j --
            }
        }
    }
    quickSort(arr, left, i - 1)
    quickSort(arr, i + 1, right)
}

quickSort(arr, 0, arr.length - 1)

console.log(arr)

持續更新中…