排序算法

选择排序O(n^2)

//返回数列的最小值
//递归方法
let min = (number) => {
    if (number.length > 2) {
        return min([number[0], min(number.slice(1))]);
    } else {
        return Math.min.apply(null, number);
    }
};
//循环方法
// let minCycle = (number) => {
//     return number[minIndexCycle(number)];
// };

//选择排序
//递归方法
let minIndex = (number) => number.indexOf(min(number));

//递归方法
let sort = (number) => {
    if (number.length > 2) {
        let index = minIndex(number);
        let min = number[index];
        number.splice(index, 1);
        return [min].concat(sort(number));
    } else {
        return number[0] < number[1] ? number : number.reverse();
    }
};

//选择排序
//循环方法
let minIndexCycle = (number) => {
    let minIndex = 0;
    for (let i = 1; i < number.length; i++) {
        if (number[i] < number[minIndex])
            minIndex = i;
    }
    return minIndex;
};

let swap = (number, a, b) => {
    number[a] = number[a] ^ number[b];
    number[b] = number[a] ^ number[b];
    number[a] = number[a] ^ number[b];
    return number;
}

//循环方法
let sortCycle = (number) => {
    for (let i = 0; i < number.length - 1; i++) {
        console.log("------");
        console.log(`i:${i}`);
        // let tempNumber = number.slice(i);
        // let minIndex = minIndexCycle(tempNumber) + i;
        // 第i项及之前数列都是排好序的，只用考虑第i项之后的数列排序
        // minIndexCycle(tempNumber)得到的是剔除前i项排好序数列之后的新数组中，最小数在该数组中的下标
        // 由于新数组下标是重新从零开始的，要找到此最小数在number中对应的下标。应该加i。
        let minIndex = minIndexCycle(number.slice(i)) + i;
        console.log(`minIndex:${minIndex}`);
        console.log(`min:${number[minIndex]}`);
        //找到number中最小数字的下标，然后将其与当前下标的数字交换位置
        if (minIndex != i)
            swap(number, minIndex, i);
        console.log(`number:[${number}]`);
    }
    return number;
};

快速排序O(nlog2n)

//快速排序
//递归方法
let quickSort = arr => {
    if (arr.length <= 1)
        return arr;
    // 基准数字选择arr中间位置最大整数数(向下取整)
    let pivotIndex = Math.floor(arr.length / 2);
    // 取出基准数字
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        // 如果剩余数小于基准数，则将其放入左边数组；反之放入右边数组
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
};

归并排序O(nlog2n)

// 归并排序
// 先分解，再合并
// 递归方法

// 分解
let mergeSort = arr => {
    if (arr.length === 1) {
        return arr;
    }
    console.log(`----`);
    /* slice() 方法返回一个新的数组对象，这一对象是一个由 begin 和 end 决定的原数组的浅拷贝（包括 begin，不包括end）。原始数组不会被改变。*/
    let left = arr.slice(0, Math.floor(arr.length / 2));
    console.log(`left:${left}`);
    let right = arr.slice(Math.floor(arr.length / 2),);
    console.log(`right:${right}`);
    return merge(mergeSort(left), mergeSort(right));
};

// 合并
let merge = (left, right) => {
    if (!left.length)
        // 当left数组已经全部拿空了，那么就直接将right数组连接到新数组
        return right;
    if (!right.length)
        return left;

    if (left[0] > right[0]) {
        // right[0]是两个数组中的最小数，先放在左边。然后left和right剩余部分按相同方法进行合并。
        return [right[0]].concat(merge(left, right.slice(1,)))
    } else {
        return [left[0]].concat(merge(left.slice(1,), right));
    }
    // return left[0] > right[0] ? [right[0]].concat(merge(left, right.slice(1))) : [left[0]].concat(merge(left.slice(1), right));
};

计数排序O(n+max)

// 计数排序
let countSort = arr => {
    let count = {},
        // count用一个哈希表定义，便于计数
        max = 0,
        result = [];

    // 遍历数组，对所有数字计数。获得哈希表count
    // 这样做的目的是便于下一步循环，判断数字是否应该压入数组
    for (let index = 0; index < arr.length; index++) {
        if (!(arr[index] in count)) {
            count[arr[index]] = 1;
        } else {
            count[arr[index]] += 1;
        }
        if (arr[index] > max)
            max = arr[index];
    }

    // 遍历哈希表，从小到大依次将所有数字压入新数组
    for (let value = 0; value <= max; value++) {
        if (value in count) {
    // 将所有数字都压入新数组。count记录了几次，value就要压入几次
            for (let i = 0; i < count[value]; i++) {
                result.push(value);
            }
        }
    }

    return result;
}

各种排序方法的比较