[数据结构与算法]十大排序算法(JS版)

十大排序算法

概述：

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

关于时间复杂度

1. 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

2. 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

3. O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

4. 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

• n：数据规模
• k："桶"的个数
• In-place：占用常数内存，不占用额外内存
• Out-place：占用额外内存
• 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

冒泡排序

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        // 注意这里上限是 len - 1 - i
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                var temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

选择排序

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

插入排序

function insertionSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len; i += 1) {
        let index = i - 1;
        let temp = arr[i];
        // 不断向左移动，知道找到这个元素在已排好序的元素的位置
        while(index >= 0 && arr[index] > temp) {
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = temp;
    }
    return arr;
}

归并排序（重要）

// 大问题分解
function mergeSort(arr) {
    if (!Array.isArray(arr)) {
        return "必须是一个数组";
    } else {
        let len = arr.length;
        if (len <= 1) {
            return arr;
        } 

        const middle = Math.floor(len / 2);
        return merge(mergeSort(arr.slice(0,middle)), mergeSort(arr.slice(middle)));
    }
}

// 小问题合并
function merge(arr1, arr2) {
    let res = [];
    while(arr1.length && arr2.length) {
        if(arr1[0] <= arr2[0]) {
            res.push(arr1.shift());
        } else {
            res.push(arr2.shift());
        }
    }
    if (arr1.length) {
        res = [...res, ...arr1]
    }
    if (arr2.length) {
        res  =[...res, ...arr2]
    }
    return res；
}

快速排序（重要）

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const index = partition(arr);
    return quickSort(arr.slice(0, index)).concat(arr[index], quickSort(arr.slice(index+1)));
}

// 找到基准点
function partition(arr) {
    let left = 0;
    let right = arr.length-1;
    while (left < right) {
        while(left < right && arr[right] > arr[left])
            right -= 1;

        let temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        while(left < right && arr[left] <= arr[right])
            left += 1; 
        temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    return left;
}

未完待续… …