【JavaScript】实现各类经典排序算法

// 冒泡排序 - Bubble sort
function bubble_sort(arr) {
    arr = arr.slice();
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j + 1 < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    return arr;
}

// 选择排序 - Select sort
function select_sort(arr) {
    arr = arr.slice();
    for (let i = 0; i < arr.length; i++) {
        let index = i;
        for (let j = i; j < arr.length; j++) {
            if (arr[j] < arr[index]) {
                index = j;
            }
        }
        let tmp = arr[i];
        arr[i] = arr[index];
        arr[index] = tmp;
    }
    return arr;
}

// 插入排序 - Insert sort
function insert_sort(arr) {
    arr = arr.slice();
    for (let i = 0; i < arr.length; i++) {
        let num = arr.splice(i, 1)[0];
        for (let j = i - 1; j >= -1; j--) {
            if (j === -1 || arr[j] < num) {
                arr.splice(j + 1, 0, num);
                break;
            }
        }
    }
    return arr;
}

// 归并排序 - Merge sort
function merge_sort(arr) {
    arr = arr.slice();
    function sort(arr) {
        if (arr.length < 2) {
            return arr;
        }
        let i = parseInt(arr.length / 2);
        let a = sort(arr.slice(0, i));
        let b = sort(arr.slice(i));
        return merge(a, b);
    }
    function merge(a, b) {
        let arr = [];
        while (a.length !== 0 && b.length !== 0) {
            if (a[0] < b[0]) {
                arr.push(a.shift());
            } else {
                arr.push(b.shift());
            }
        }
        return arr.concat(a, b);
    }
    arr = sort(arr);
    return arr;
}

// 快速排序 - Quick sort
function quick_sort(arr) {
    arr = arr.slice();
    let count = 0;
    function sort(arr, a, b) {
        if ((b - a) <= 1) {
            return;
        }
        let num = arr[a];
        let index = a;
        for (let i = a; i < b; i++) {
            if (arr[i] < num) {
                index += 1;
                let tmp = arr[i];
                arr[i] = arr[index];
                arr[index] = tmp;
            }
        }
        let tmp = arr[a];
        arr[a] = arr[index];
        arr[index] = tmp;
        sort(arr, a, index);
        sort(arr, index + 1, b)
    }
    sort(arr, 0, arr.length);
    return arr;
}

// 计数排序 - Count sort
function count_sort(arr) {
    arr = arr.slice();
    let max = arr[0];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    let counts = [];
    for (let i = 0; i <= max; i++) {
        counts.push(0);
    }
    while (arr.length !== 0) {
        let index = arr.shift();
        counts[index] += 1;
    }
    for (let i = 0; i < counts.length; i++) {
        for (let j = 0; j < counts[i]; j++) {
            arr.push(i);
        }
    }
    return arr;
}

// 基数排序 - Radix Sort
function radix_sort(arr) {
    arr = arr.slice();
    let boxs = null;
    let digit = 1;
    let isEnd = false;
    while (!isEnd) {
        boxs = [[], [], [], [], [], [], [], [], [], []];
        digit = digit * 10;
        isEnd = true;
        while (arr.length !== 0) {
            let num = arr.shift();
            let index = parseInt((num % digit) / (digit / 10));
            boxs[index].push(num);
            if (index !== 0) {
                isEnd = false;
            }
        }
        for (let i = 0; i < boxs.length; i++) {
            while (boxs[i].length !== 0) {
                let num = boxs[i].shift();
                arr.push(num);
            }
        }
    }
    return arr;
}

// 生成随机数组
function random_array(length) {
    let arr = [];
    for (let i = 0; i < length; i++) {
        let num = Math.floor(Math.random() * length);
        arr.push(num);
    }
    return arr;
}

// 验证排序结果
function check_result(arr) {
    for (let i = 1; i < arr.length; i++) {
        if (arr[i - 1] > arr[i]) {
            return false;
        }
    }
    return true;
}

// 显示排序耗时
function show_sort_time(arr, $func) {
    let ts1 = Date.now();
    arr = $func(arr);
    let ts2 = Date.now();
    if (check_result) {
        console.log("Sorting " + arr.length + " numbers "
            + $func.name + " takes " + (ts2 - ts1) + "ms")
    }
}

let arr = random_array(10_0000);
show_sort_time(arr, bubble_sort); // 32098ms
show_sort_time(arr, select_sort); // 11664ms
show_sort_time(arr, insert_sort); // 15951ms
show_sort_time(arr, merge_sort); // 599ms
show_sort_time(arr, quick_sort); // 35ms
show_sort_time(arr, count_sort); // 668ms
show_sort_time(arr, radix_sort); // 4698ms

VisuAlgo 排序算法可视化
https://visualgo.net/zh/sorting