常见的排序算法

前言

作为前端开发者而言，算法虽然是一种只需要涉猎的领域，但它对于我而言，确是一道不得不踏过的槛。原因有俩，其一，前端在遇到复杂的逻辑问题时可以有更好地去理解与分析；其二，个人的竞争力也会比较突出（大厂面经必备）

友情提示 5道基础算法题，阅读时间为5-10分钟
下面来看下有哪些排序算法

---

冒泡排序

主要思路：比较相邻两个项，如果第一个比第二个大，就交换位置。

var bubbleSort = function (array) {
    var len = array.length;
    //循环length不减一，用于获取数组循环轮数，以便于相邻数值的比较
    for(var i =0; i < len; i++){
        for(var j =0; j < len - 1; j++){
           if(array[j] > array[j+1]){
               var firstVal = array[j];
               array[j] = array[j+1];
               array[j+1] = firstVal; 
           }
        }
    }
}

选择排序

选择排序，也称为原址比较算法。主要思路是，找到数据结构中的最小值并将其放置在第一位，接着找到第二小值放到第二位。以此类推。

var selectionSort = function (array) {
    var indexMin;
    for (var i = 0; i < array.length-1; i++) {
        indexMin = i;

        //循环length不减一，用于获取数组最后一个元素与前一个元素进行比较
        for (var j = i; j < array.length; j++) {
            if (array[indexMin] > array[j]) {
                indexMin = j;
            }
        }
        if (i !== indexMin) {
            var ux = array[i];
            array[i] = array[indexMin];
            array[indexMin] = ux;
        }
    }
}

插入排序

插入排序，相较前两种算法性能是有所提高，思路是将第一项与第二项比较，得出正确排序；接着与第三项比较，得出1，2，3项的正确排序，以此类推

var insertionSort = function (array) {
    for (var i = 0; i < array.length; i++) {
        var j = i;
        var temp = array[i];
        while(j > 0 && array[j-1] > temp) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = temp;
    }
}

归并排序

归并排序,是一个比较优化的算法,思路是将其递归分解数列,再合并数列

var mergeSort = function (array) {
    var len = array.length;
    if (len <= 1) {
        return array;
    }
    var mid = Math.floor(len / 2);
    var left = array.slice(0, mid);
    var right = array.slice(mid, len);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var i = 0, j = 0, result = [];
    while(i < left.length && j < right.length) {
        if (left[i] > right[j]) {
            result.push(right[j++]);
        } else {
            result.push(left[i++]);
        }
    }
    while (i < left.length) {
        result.push(left[i++]);
    }
    while (j < left.length) {
        result.push(left[j++]);
    }

    return result;
}

快速排序

快速排序，常用的一种排序方法。主要思路是取一个基准点，以基准点为中心，分割成小于基准点或者大于基准点的两个数组，按顺序递归排列

var quickSort = function (array) {
    if (array.length <= 1) {
        return array;
    }
    var mid = Math.floor(array.length / 2);
    var temp = array.splice(mid, 1)[0];
    var left = [];
    var right = [];

    for (var i = 0; i < array.length; i++) {
        if (array[i] < temp) {
            left.push(array[i]);
        } else {
            right.push(array[i]);
        }
    }

    return quickSort(left).concat(temp, quickSort(right));
}

---

思考

这几种算法有哪些优缺点？
首先，选择排序跟冒泡排序是比较简单的算法，然而这两种排序算法在运行性能上都是比较差的。只考虑用于学习；
其次，插入排序跟前两者一样，都是通过比较来进行排序，在小型数组方面性能相对较好，但还是不支持用于实战；
对于归并排序与快速排序而言，两者的相同点在于采用分治的思想，只不过快排没有将数组切割。而在实用性方面，归并与快排都是能进行实用的算法，但快排应该是最常用的一种。
其他排序算法呢？
其实排序算法还有堆排序、希尔排序、计数排序、桶排序、基数排序等，只不过对这几种掌握不深，不敢班门弄斧。后面对算法更熟悉些，会进行这几种算法的学习并且与前几种算法的优势比较