排序算法

冒泡排序

基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
每一趟遍历，将一个最大的数移到序列末尾（比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换）。

function bubbleSort(arr) {
    if (!arr || !arr.length) {
        return []
    }
    // 外部的循环控制所有回合
    for (let i = 0; i < arr.length - 1; i++) {
        // 内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                const temp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp
            }
        }
    }
}

优化版本：

/*
 * 如果有 100 个数的数组，仅前面 10 个无序，后面 90 个都已排好序且都大于前面 10 个数字，那么在第一趟遍历后，
 * 最后发生交换的位置必定小于 10，且这个位置之后的数据必定已经有序了，
 * 记录下这个位置，第二次只要从数组头部遍历到这个位置就可以了
 */
function bubbleSort(arr) {
    if (!arr || !arr.length) {
        return []
    }
    let flag = arr.length
    while(flag) {
        let n = flag
        flag = 0
        for (let i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                let temp = arr[i]
                arr[i] = arr[i - 1]
                arr[i - 1] = temp
                flag = i
            }
        }
    }
}

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

function insertSort(arr) {
    // let len = arr.length;
    for (let i = 1; i < arr.length; i++) {
        // 将 arr[i] 插入到有序队列（arr[0] —— arr[i-1]）中
        for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            let temp = arr[j + 1]
            arr[j + 1] = arr[j]
            arr[j] = temp
        }
    }
    return arr;
}

快速排序

快速排序每一趟排序，都会寻找一个基准元素，有的采用第一个元素，有的会随机生成一个，但是基本思想是不变的，一趟排序结束，会形成以基准元素为分界点的两部分，其中左边比基准元素小（假设从小到大排序），右边比基准元素大。然后再以相同的方法处理左边和右边两部分，即递归。

function quickSort(arr, left, right) {
    left = typeof left === 'number' ? left : 0
    right = typeof right === 'number' ? right : arr.length - 1

    if (left < right) {
        const partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex - 1)
        quickSort(arr, partitionIndex + 1, right)
    }

    return arr
}
// 分区操作，设定基准值（pivot）
function partition(arr, left, right) {
    let pivot = left
    let index = pivot + 1
    for (let i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            [ arr[i], arr[index] ] = [ arr[index], arr[i] ]
            index++
        }
    }
    [ arr[pivot], arr[index - 1] ] = [ arr[index - 1], arr[pivot] ]
    return index - 1
}

归并排序（Merge Sort）

分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

function mergeSort(arr) {
    const len = arr.length;
    if (len < 2) {
        return arr;
    }
    const middle = Math.floor(len / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);
    return mergeArr(mergeSort(left), mergeSort(right));
}

function mergeArr(left, right) {
    var result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length) {
        result.push(left.shift());
    }

    while (right.length) {
        result.push(right.shift());
    }    return result;
}

其他排序见1

其他排序见2