数组-排序

数组排序算法整理
参考

冒泡排序

思想：

1. 两层循环
2. 外层循环控制循环控制开始比较的下标 i
3. 内循环将 i 之后元素两两比较，交换位置，将最大值或最小值移动到位置 i。

function bubbleSort(fun) {
    return function inner(arr) {
        if (arr.length <=1) {
            return arr
        }
        for (let i = 0; i < arr.length; i++) {
            for (let j = i + 1; j < arr.length; j++) {
                let res = fun(arr[i], arr[j]);
                console.log(res)
                if (res > 0) {
                    let temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp
                }
            }
        }
        return arr
    }
}
let fun = (a, b) => a.charCodeAt() - b.charCodeAt();
let sort = bubbleSort(fun)

快速排序

思想：

1. 新建两个数组 left,right
2. 选择一个数作为基准数，可以是数组中的任意一个元素，一般取数组的中间元素
3. 将数组中的元素与基准数比较，小于基准数放 left 数组(升序)，大于基准值的放进右边 right 数组。
4. 将左右数组作为参数递归调用排序函数

function quickSort(fun) {
    return function inner(arr) {
        if (arr.length <= 1) {
            return arr
        }
        let left = [],
            right = [],
            standard = arr[Math.floor(arr.length / 2)];
        arr.splice(arr.indexOf(standard), 1)//如果不做处理，存在相同值会无无限递归到栈溢出
        for (let i = 0; i < arr.length; i++) {
            if (fun(standard, arr[i]) > 0) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return inner(left).concat(standard, inner(right))

    }
}

插入排序

思想：

1. 从第一个元素开始，默认该元素为已被排序元素（最大或最小）
2. 取出当前元素的后一个元素，与已经排序的元素序列（此元素的前面元素）从后向前循环比较
3. 如果该元素小于（递增排序）循环拿到的元素，就与下一位循环元素比较，
4. 重复步骤 3，直到找到已排序元素中小于或等于新元素的位置，将该元素插入循环元素的后面
5. 如果没有找到，就插入到数组最后面
6. 重复步骤 2-5
   

function insertSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    let result = [arr[0]];
    for (let i = 1; i < arr.length; i++) {
        let standard = arr[i];
        for (let j = result.length - 1; j >= 0;j--) {
            if (standard > result[j]) {
                result.splice(j + 1, 0, standard);
                break
            }
            if (j === 0) {
                result.push(standard)
            }
        }
    }
 return result
}

选择排序

思想：

1. 设置索引值为 0 的元素为最小值
2. 遍历索引为 0 以后的数组，如果后面的元素小于索引为 0 的元素就交换
3. 遍历完成后，将索引为加一，以此元素为最小值，重复 2

function selectionSort(fun) {
        return function inner(arr) {
            if (arr.length <= 1) {
                return arr
            }

            for (let i = 0; i < arr.length; i++) {
                for (let j = i + 1; j < arr.length; j++) {
                    if (fun(arr[i], arr[j])) {
                        let tmp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
            return arr

        }
    }
    let fun = (a, b) => {
        return a.charCodeAt() - b.charCodeAt() < 0
    };
    let sort = selectionSort(fun)

    sort(array)