基于js的排序算法

冒泡排序

冒泡排序的原理：

从第一个元素开始，把当前元素和下一个元素进行比较。如果当前元素大，那么就交换位置，重复操作知道比较到最后一个元素。那么此时最后一个元素已经是数组中最大的数。下一轮重复以上操作，但此时最后一个数已经是最大的数了，所以不需要比较最后一个数，只需要比较到length-1即可。

代码如下：

//冒泡排序
var fn = function (arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    return arr;
}
console.log("冒泡排序" + fn(arr));

冒泡排序的时间复杂度是O(n²)

插入排序

插入排序的原理：

默认第一个元素为已排序元素，此后，依次取出下一个元素和当前元素进行比较，将其插入到合适的位置。

代码如下：

//插入排序
var fn2 = function (arr) {
    for (var i = 1; i < arr.length; i++) {
        for (var j = i; j >= 0 && arr[j] < arr[j - 1];j--) {
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
        }
    }
    return arr;
}

插入排序的时间复杂度是O(n²)

选择排序

选择排序的原理：

遍历数组，设置最最最小值的索引为0，如果取出的值比当前最小值小，就替换最小值索引。遍历完成后，将第一个元素和索引元素交换，然后再依次比较后面的值。

代码如下：

// 选择排序
var fn3 = function (arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        var minIndex = i;
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        [arr[minIndex], arr[i]] = [arr[i],arr[minIndex]];
    }
    return arr;
}

选择排序的时间复杂度是O(n²)

归并排序

归并排序的原理:

递归地将数组两两分开直到最多包含两个元素，然后将数组排序合并，最终合并为排序好的数组。假设有⼀组数组 [3, 1, 2, 8, 9, 7, 6] ，中间数索引是 3，先排序数组 [3, 1, 2, 8]。在这个左边数组上，继续拆分直到变成数组包含两个元素（如果数组⻓度是奇数的话，会有⼀个拆分数组只包含⼀个元素）。然后排序数组 [3, 1] 和 [2, 8]，然后再排序数组 [1, 3, 2, 8]，这样左边数组就排序完成，然后按照以上思路排序右边数组，最后将数组 [1, 2, 3, 8] 和 [6, 7, 9] 排序。

代码如下：

var fn4 = function (arr) {
    if (arr.length == 1) {
        return arr;
    } else if (arr.length == 2) {
        return [Math.min(...arr), Math.max(...arr)]
    } else {
        var arr2 = [...arr];
        var arr1 = arr.splice(0, Math.ceil(arr.length /2));
        arr2 = arr2.splice(Math.ceil(arr2.length / 2),arr2.length);
        return fn5(fn4(arr1), fn4(arr2));
    }
}
// 合并两个已排序数组
var fn5 = function (arr1, arr2) {
    var result = [];
    for (var i = 0, j = 0; i < arr1.length || j <arr2.length;) {
        if (arr1[i] < arr2[j] || j == arr2.length) {
            result.push(arr1[i]);
            i++;
        } else if (arr2[j] <= arr1[i] || i ==arr1.length) {
            result.push(arr2[j]);
            j++;
        }
    }
    return result;
}

归并排序的时间复杂度为O(n*log n)

快速排序

快速排序的原理:

在待排序的数列中，我们首先要找一个数字作为基准数(一般选择第1个数字作为基准数）。接下来把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

代码如下:

var fn6 = function (arr) {
    if (arr.length <= 1) return arr;
    else {
        var midIndex=fn7(arr);
        var lower = [...arr].splice(0,midIndex);
        var higher = [...arr].splice(midIndex+1,arr.length-1);
        return [...fn6(lower),arr[midIndex],...fn6(higher)];
    }
}
// 辅助函数
var fn7=function(arr){
    var flag = true;
    for (var i = 0, j = arr.length - 1; i != j;) {
        if (arr[i] > arr[j]) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            flag = !flag;
        }
        flag ? j-- : i++;
    }
    return i;
}

快速排序的时间复杂度为O(n*log n)

'立即执行函数(setImmediate)'并不是'立即执行'，但'快速排序'是真的'快速'。