排序

冒泡排序

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

选择排序

function selectSort(arr) {
    let len = arr.length;
    let minIndex = 0;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;   
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
}

插入排序

function insertSort(arr) {
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        for (let j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            } else {
                break;
            }
        }
    }
    return arr;
}

快速排序

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let s = Math.floor(arr.length / 2);
    let temp = arr.splice(s, 1);
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < temp) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(temp, quickSort(right));
}

另一种快速排序：

function Partition(arr, p, r) {
    let i = p, j = r + 1;
    let x = arr[p];
    while (true) {
        while (arr[++i] < x && i < r) ;
        while (arr[--j] > x) ;
        if (i >= j) break;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    arr[p] = arr[j];
    arr[j] = x;
    return j;
}
function QuickSort(arr, p, r) {
    if (p < r) {
        let q = Partition(arr, p, r);
        QuickSort(arr, p, q - 1);
        QuickSort(arr, q + 1, r);
    }
    return arr;
}
let arr = [3, 1, 2, 5, 8, 9, 1, 5];
console.log(QuickSort(arr, 0, arr.length - 1));

Donate