sort排序

<script>
    // 写这个学习笔记纯粹是因为我想解答下这道题，然后发现我啥都不知道？所以自己学习了下并记录了下来。
    var arr = [-1, 1, 3, 4, 6, 10];
    arr.sort((a, b) => Math.abs(a - 3) - Math.abs(b - 3));
    console.log(arr);  //  [3, 4, 1, 6, -1, 10]
</script>
复制代码

首先来看下w3c上对于**sort()**方法的解释（原理类似冒泡排序）。

<script>
    // pre next 瞎搞解答一下
    var arr = [-1, 1, 3, 4, 6, 10];
    var arr1 = [];
    arr.forEach((item, index) => {
        arr1.push({
            oldIndex: index,
            newVal: Math.abs(item - 3)
        })
    })
    // arr1 = [{oldIndex:0,newVal:4},{oldIndex:1,newVal:2},{oldIndex:2,newVal:0},{oldIndex:3,newVal:1},{oldIndex:4,newVal:3},{oldIndex:5,newVal:7}]
    arr1.sort((pre, next) => pre.newVal - next.newVal); // 按newVal升序
    var indexArr = [];
    arr1.forEach(item => {
        indexArr.push(item.oldIndex)
    })
    var newArr = []; // 最新的数组
    indexArr.forEach(item => {
        newArr.push(arr[item])
    })
    console.log(newArr);  //  [3, 4, 1, 6, -1, 10]
    // 如果是ab加减不同的数值又咋搞？
</script>
复制代码

冒泡排序

思路：

升序-将数组中的相邻两个元素进行比较，大的往后排，一轮过后，最大的值放在数组最后。降序反之。
即：进行 arr.length – 1 轮对比，每轮对比减少一次
eg：[3, 4, 1, 6, -1, 10] 该数组对比5轮，第一轮对比5次，第二轮对比4次…

ps: 图片来源：星空之火@田兴

// sort 默认asc升序 desc 降序
Array.prototype.bubbleSort = function (sort = 'asc') {
    let arr = this; // 不要用箭头函数，否则this会指向window
    let len = arr.length;
    // 比较的轮数
    for (var i = 0; i < len - 1; i++) {
        // 每轮比较的次数，次数 = 长度 - 此时的轮数 - 1
        for (var j = 0; j < len - i - 1; j++) {
            if (sort === 'asc' ? (arr[j] > arr[j + 1]) : (arr[j] < arr[j + 1])) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}
cosnt arrTemp = [3, 4, 1, 6, -1, 10]
console.log(arrTemp.bubbleSort()) // [-1, 1, 3, 4, 6, 10]
console.log(arrTemp.bubbleSort('desc')) // [10, 6, 4, 3, 1, -1]
复制代码

快速排序（对冒泡排序的一种改进）

思路

升序-将原数组分解成以中间数为基准的两个左右数组，比中间数小的放到左数组，比中间数大的放到右数组，依次递归，直到数组长度为1，最后拼接下左中右三个数组即可。降序反之。

图片来源：星空之火@田兴

// sort 默认asc升序，desc降序
Array.prototype.fastSort = function (sort = 'asc') {
    let arr = JSON.parse(JSON.stringify(this)); // 这里深拷贝一下数组，避免下面的splice操作改变了原数组的值
    let len = arr.length;
    if (len <= 1) {
        // 数组长度小于等于1直接返回数组
        return arr;
    }
    const centerIndex = Math.floor(len / 2); // 获取中间数索引，奇数向下取整
    const centerVal = arr.splice(centerIndex, 1)[0]; // 获取中间数并从原数组中将其删掉
    let leftArr = [], rightArr = [];
    arr.forEach(item => {
        if (sort === 'asc' ? (item <= centerVal) : (item >= centerVal)) {
            // 如果数组没去重，考虑下等于的情况，等于随意左右边
            leftArr.push(item);
        } else {
            rightArr.push(item);
        }
    })
    // 递归调用
    return leftArr.fastSort(sort).concat([centerVal], rightArr.fastSort(sort));
}
const arrTemp = [3, 4, 1, 6, -1, 10, 4]
console.log(arrTemp.fastSort()) // [-1, 1, 3, 4, 4, 6, 10]
console.log(arrTemp.fastSort('desc')) // [10, 6, 4, 4, 3, 1, -1]
复制代码

插入排序

思路

升序-默认第一项已排序，外循环中数组未排序的项依次取出比对。
内循环中，未排序的项依次比对已排序的项（从已排序的最后一项开始），如果取出来对比的值小于已排序的值（降序反之)，则已排序的项依次向后挪，否则不动。
最后，把在外循环中存储的当前值插入到内循环结束位置的下一个位置。

图片来源：星空之火@田兴

// sort 默认asc升序，desc降序
Array.prototype.insertSort = function (sort = 'asc') {
    let arr = this;
    let len = arr.length;
    let preIndex, current; // 当前要插入的位置,当前取出来的值
    for (let i = 1; i < len; i++) { // 默认第一项已排序，从第二项开始取出
        preIndex = i -1;
        current = arr[i];
        while (preIndex >= 0 && sort === 'asc' ? (current <= arr[preIndex]) : (current >= arr[preIndex])) {
            // 内循环依次比对已排序的项，符合条件则依次往后挪动
            // 注意是把前一项赋值给后一项依次挪动，而不是当前取出的项
            arr[preIndex + 1] = arr[preIndex];
            preIndex--; // 未满足第二项条件则跳出内循环，或者直到preIndex = -1
        }
        arr[preIndex + 1] = current; // 跳出内循环后，在外循环把取出的值赋值给跳出循环的下一个位置。
    }
    return arr;
}
const arrTemp = [3, 4, 1, 6, -1, 10, 4]
console.log(arrTemp.insertSort()) // [-1, 1, 3, 4, 4, 6, 10]
console.log(arrTemp.insertSort('desc')) // [10, 6, 4, 4, 3, 1, -1]
复制代码