JS 中常见的几种排序算法

# 前言

很多同学在前端面试中，手写代码已经是家常便饭。要求写一些常见的排序算法也是常常遇到，接下来将把几种常见的算法用 JavaScript 的方法实现。

# 快速排序

分治法的思想，寻找中间点，并对其左右的序列递归进行排序，直到左右都排序完成。

function quickSort(arr){
    if(arr.length == 0) return arr;

    let pirotIndex = Math.floor(arr.length/2),
        pirot = arr.splice(pirotIndex, 1)[0],
        left= [], right = [];

    for(let i = 0; i < arr.length; i++){
        arr[i] > pirot ? right.push(arr[i]) : left.push(arr[i]);
    }

    return quickSort(left).concat(pirot, quickSort(right))
}

# 插入排序

将数组分为 无序区 和 有序区 两个区，然后不断 将无序区 的第一个元素按大小顺序插入到 有序区 中去，最终将所有 无序区 元素都移动到 有序区完 成排序

function insertionSort(arr) {
    var preIndex, current;
    for (let i = 1; i < arr.length; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

# 冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

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

# 选择排序

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

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

# 归并排序

把数组分半，不断递归排序，最后进行已排序的数字进行合并。

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

function merge(left, right) {
    let 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
}