sort.md

排序

目录

• 一、冒泡排序
• 二、选择排序
• 三、快速排序

一、冒泡排序

返回目录

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

二、选择排序

返回目录

const selectSort = arr => {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i; j <arr.length; j++) {
            if (arr[i] < arr[j]) {
                [arr[i], arr[j]] = [arr[j], arr[i]]
            }
        }
    }
    return arr;
}

三、快速排序

返回目录

选择一个标尺元素，比标尺元素的大的放一边，小的放另一边，依次递归至结束

const quickSort = arr => {
    const sort = (arr) => {
        const len = arr.length
        if(len < 2) {return arr}

        let flag = arr[0]
        let left = [];
        let right = [];

        for (let i = 1; i < len; i++) {
            if (arr[i]  < flag) {
                left.push(arr[i])
            }else {
                right.push(arr[i])
            }
        }

        return sort(left).concat(flag,sort(right))

    }
    return sort(arr)
}

但是存在占用内存过大的问题，采取in-place(内部直接替换)方式优化

const quickSort = arr => {
    // 找到数组标尺元素下角标
    const findCenter = (arr, left, right) => {
        let flag = arr[left]
        let idx = left + 1;
        for (let i = idx; i <= right; i++) {
            if (arr[i] < flag) {
                [arr[i], arr[idx]] = [arr[idx], arr[i]]
                idx++
            }
        }
        [arr[idx - 1], arr[left]] = [arr[left], arr[idx - 1]]
        return idx
    }
    const sort = (arr, left, right) => {
        if (left < right) {
            const center = findCenter(arr, left, right);
            sort(arr, left, center - 1)
            sort(arr, center, right)
        }
    }
    sort(arr, 0, arr.length - 1)
    return arr;
}