冒泡，选择，插入，快排，归排，堆排

1、JavaScript的sort()方法

var array = [1,4,-8,-3,6,12,9,8];
function compare(a, b){
    return a - b;
};
array.sort(compare);
console.log(array);

sort()方法按照升序排列数组项，会调用每个数组项的toString()转型方法，然后比较得到的字符串。
toString()方法是把布尔值或BooleanObject转换为字符串，并返回结果。
compare()函数方法是一个比较函数，作为sort()方法的参数。

2、冒泡排序（从后向前）

const array = [1, 4, -8, -3, 6, 12, 9, 8];
function sort(arr) {
    for (let j = 0; j < arr.length - 1; j++) {
        //两两比较，如果前一个比后一个大，则交换位置。
        for (let i = 0; i < arr.length - 1 - j; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
            }
        }
    }
}
sort(array);
console.log(array);

（1）比较相邻的元素。如果第一个比第二个大，就交换他们两个位置，这样一轮走完最大的元素就在最后边了。
（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
（3）针对所有的元素重复以上的步骤，除了最后一个。
（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3、选择排序（从前往后）

let array = [1, 4, -8, -3, 6, 12, 9, 8];
function selectSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        //设置当前范围最小值和索引
        let min = arr[i];
        let minIndex = i;
        //在该范围选出最小值
        for (let j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j;
            }
        }
        //将最小值插入,并将原来位置的最小值删除
        arr.splice(i, 0, min);
        arr.splice(minIndex + 1, 1);
    }
}
selectSort(array);
console.log(array);

（1）在未排序序列中找到最小（大）元素
（2）并存放到排序序列的起始位置，这样前边的元素都是先排好了的。
（3）然后，再从剩余未排序元素中继续寻找最小（大）元素
（4）然后放到已排序序列的末尾。
（5）以此类推

4、插入排序（从前向后，在已排序的序列中找位置插入）

const array = [1, 4, -8, -3, 6, 12, 9, 8];
function insertSort(arr) {
    //假设第0元素是有序序列，第1元素之后是无序的序列。从第1元素开始依次将无序序列的元素插入到有序序列中
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            //取出无序序列中需要插入的第i个元素
            let temp = arr[i];
            //定义有序中的最后一个位置
            let j = i - 1;
            arr[i] = arr[j];
            //比较大小，找到插入的位置
            while (j >= 0 && temp < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            };
            //插入
            arr[j + 1] = temp;
        }
    }
}
insertSort(array)
console.log(array);

（1）从第一个元素开始，该元素可以认为已经被排序
（2）取出下一个元素，在已经排序的元素序列中扫描
（3）如果该元素（已排序）大于新元素，将该元素移到下一位置
（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到下一位置中
（6）重复步骤2

5、快速排序

const array = [1, 4, -8, -3, 6, 12, 9, 8];
function quickSort(arr) {
    //如果数组长度小于等于1，则返回数组本身
    if (arr.length <= 1) return arr;
    //定义中间值的索引
    const mid = Math.floor(arr.length / 2);
    //取到中间值
    const temp = arr.splice(mid, 1)[0];
    //定义左右部分数组
    const left = [];
    const 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));
}
const res = quickSort(array)
console.log(res)

6、归并排序

//判断 合并两个有序数组
function merge(left, right) {
    const result = [];
    while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return result.concat(left).concat(right);
}

//拆分
function mergeSort(arr) {
    if (arr.length == 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}

var arr = [2, 5, 3, 4];
console.log(mergeSort(arr))

归排和快排区别

虽然在于算法的区别主要在于递归实现的时机不同，在一些细节上也有着一些区别：
快速排序：
进行选择排序的时候，如果一轮还没有排序结束，会暂时将比中心值小的数放在紧挨着中心值的右边，并设置一个游标来控制这些数的下标，每找到一个小于的数就将游标的值加一换到下一个，直到一轮排序结束后，再将中心值和此时的游标交换位置，以达到左边的数字小于游标的值，此时再用递归的方法排序左边的值或者右边的值。
归并排序：
对于归并排序来说 会将数组先划分再排序，先会划分一小段将一小段排序，当有序后会排序下一小段，两个都为有序的时候，会将这两个归并，就是将两个有序的数组合并为一个有序的数组（注意，这种是自顶向下的排序方法）
而自底向上的方法则是分组后将每小组都排为有序的，再两两一排序，得到最后的整体有序