JS排序

排序除了面试会考，好像实际项目中也用的不多，但是用来了解算法，开拓思维也是很nice的，站在巨人肩膀上学习了几种比较好理解的：

• 选择排序：
  思想很简洁，也是最符合常规思维的一种方法，每次以既定的第一个为基准，遍历后面的每一个元素，比基准小则交换位置

            function selectionSort(arr) {
                if(arr instanceof Array){ //校验参数类型
                    var len = arr.length;
                    var count = 0; //计数，非必须
                    for (var i = 0; i < len - 1; i++) {
                        for (var j = i + 1; j < len - 1; j++) {
                            let tmp;
                            count++;
                            if (arr[i] > arr[j]) { //交换值
                                tmp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = tmp;
                            }
                        }
                    }
                    console.log(`count = ${count}`);
                    return arr;
                }
            }

• 冒泡排序:
  每次从头开始，比较相邻两个元素的值大小，如果前者大于后者，则交换二者的位置，就向气泡一样，最大（或者最小）的会往尾部靠

            function sort(arr,  type = "up") { //type为升序或者降序
                if (!(arr instanceof Array)) { //校验数据类型
                    return;
                } else {
                    let count = 0;
                    for (let i = 0; i < arr.length - 1; i++) { //精简循环次数
                        for (let j = 0; j < arr.length - 1 - i; j++) { //每次循环会确实一个值，不用循环已经确定的值
                            let tmp;
                            if (
                                type == "up"
                                    ? arr[j] > arr[j + 1]
                                    : arr[j] < arr[j + 1]
                            ) {
                                // if(arr[j] > arr[j+1]){
                                tmp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = tmp;
                            }
                            count++;
                        }
                    }
                    console.log(`count = ${count}`);
                    return arr;
                }
            }

• 快速排序法，二分法：
  1.选择数组中间的值为基准值。
  2.比基准小的推入一个数组，比基准大推入一个数组。并拼接
  3.递归执行1，2两个步骤去分别筛选新数组，直到数组长度为0或者1，终止循环。

    function quickSort(arr){
        if(arr.length <=1){
            return arr
        }
        var midIndex = Math.floor(arr.length/2); //取数组中间值
        var midValue = arr.splice(midIndex, 1)[0];
        var left = [],right=[]; //新建两个分类数组
        for (let index = 0; index < arr.length; index++) {
            const element = arr[index]
            element > midValue? right.push(element) : left.push(element) //把数组分为两类
        }
        return quickSort(left).concat([midValue], quickSort(right)) //递归调用
    }

递归的思想，耐人寻味。