JS常见排序算法

最近看到一篇介绍排序算法的文章，自己在此学习总结一下。

1-冒泡排序

算法思路

依次比较相邻2个数的大小，如果不符合要求则交换。这样第一轮循环结束，最大值或最小值排在数组最后一位。剩下的数值重复以上步骤，直到排序结束。

以对数组[3,2,5,1,4] 进行从小到大排序为例，步骤如下：

1. 3和2比较，3大于2。交换位置，数组为[2,3,5,1,4]
2. 3和5比较，3小于5。不交换位置，数组不变。
3. 5和1比较，5大于1。交换位置，数组为[2,3,1,5,4]
4. 5和4比较，5大于4。交换位置，数组为[2,3,1,4,5]

这样第一轮循环结束，最大值5排在数组最后一位。然后再对剩下的数值重复这个过程，这样下来每次循环都会排到一个正确的数值。直至剩下最后一个位置，所有排序结束。

代码实现

//交互数值函数
function swap(myArray, p1, p2){
    var temp = myArray[p1];
    myArray[p1] = myArray[p2];
    myArray[p2] = temp;
}

//冒泡排序
function bubbleSort(myArray) {
    var len = myArray.length,
        stop = 0;

    for(let i = 0; i < len - 1; i++){
        for(let j = 0,stop = len - 1 - i; j < stop; j++){
            if(myArray[j] > myArray[j+1]){
                swap(myArray, j, j + 1);
            }
        }
    }

    return myArray;

}

---

2-选择排序

算法思路

选择排序与冒泡类似，也是相邻位2个数比较大小。不同的是当不符合要求时，不是立马交换位置，而是给当前数值标记来表明最小或最大值，并且当前的最小或最大值依次比较数组里的数值。等一轮结束，找出最小或最大值再交换位置，其余位置不变。剩余数值重复以上步骤，直到排序结束。

以对数组[3,2,5,1,4] 进行从小到大排序为例，步骤如下：

1. 假设第一个位置的3为最小值。
2. 最小值3和2比较，3大于2。那么2标记为最小值。
3. 最小值2和5比较，2小于5。最小值标记不变。
4. 最小值2和1比较，2小于1。那么1为最小值。
5. 最小值1和4比较，1小于4。最小值标记不变。
6. 一轮结束后，第一位置的3和第四位置的1交换位置，数组为[1,2,5,3,4]

第一轮结束后，最小值1排到正确位置。剩下数值重复上述步骤，直到排序结束。

代码实现

//选择排序
function selectionSort(myArray) {
    let len = myArray.length;

    for(let i = 0; i < len; i++){

        //假设当前位置为最小值
        let min = i;

        //遍历剩下数字是否为最小
        for(let j = i + 1; j < len; j++){
            if(myArray[j] < myArray[min]){
                min = j;
            }
        }

        //如果当前位置不是最小值，替换最小值
        if(i !== min){
            swap(myArray,i,min);
        }
    }

    return myArray;


}

---

3-插入排序

算法思路

将数组分为两部分，一个是已排序，一个是未排序。最开始已排序只有一个数值，然后将已排序最后一个元素后面的元素从未排序里取出，插入到已排序里并且进行排序。这样”已排序“增加一个，未排序减少一个。重复以上步骤，直到排序结束。

以对数组[3,2,5,1,4] 进行从小到大排序为例，步骤如下：

1. 数组[3,2,5,1,4]分为已排序为[3]和未排序为[2,5,1,4]
2. 已排序最后一个元素是3，未排序第一个元素是2，2小于3。那么已排序为[2,3]，未排序为[5,1,4]
3. 已排序最后一个元素是3，未排序第一个元素是5，5大于3。那么已排序为[2,3,5]，未排序为[1,4]
4. 已排序最后一个元素是5，未排序第一个元素是1，1小于5。
   继续比较已排序的前一个元素3，1小于3，
   继续比较已排序的前一个元素2，1小于2，所以1为第一位元素，那么已排序为[1,2,3,5]，未排序为[4]
5. 已排序最后一个元素是5，未排序第一个元素是4，4小于5。
   继续比较已排序的前一个元素3，4大于3。因为4是未排序里最后一个元素，所以排序结束，结果为[1,2,3,4,5]

代码实现

//插入排序
function insertionSort(myArray) {
    let len = myArray.length,
        value = 0;        //需要比较的当前值

    for(let i = 0; i < len; i++){   //i 为未排序的当前位置

        //负责当前比较的值
        value = myArray[i];

        /**
         * 已排序的当当前值大于比较值
         * 已排序后移一位再次比较value
         * **/
        for(var j = i - 1; j > -1 && myArray[j] > value; j--){   //j 为已排序的当前位置
            myArray[j+1] = myArray[j];
        }

        myArray[j+1] = value;
    }

    return myArray;

}

---

4-合并排序

算法思路

基本思路是化整为零，将数组拆分为n个单个元素的数组，然后不断两两合并，直到排序完成。

以对数组[3,2,5,1,4] 进行从小到大排序为例，步骤如下：

1. 拆分为[3,2] 和 [5,1,4]
2. [3,2]拆分为[3] 、[2],然后合并为[2,3]
3. 将[5,1,4]拆分为[5]和[1,4]
4. [1,4]拆分为[1]和[4],然后合并为[1,4]
5. 在将[1,4]和[5]合并起来为[1,4,5]
6. 最后合并[2,3]和[1,4,5]，返回结果[1,2,3,4,5]

代码实现

/*
* 合并两个已排序数组，这是关键代码
* merge函数将2个已排序的数组进行合并，首先2个数组的第一个元素进行对比，
较小的添加到result里，然后较大的元素和另外一个数组的第二个元素继续比较，
同时把较小值添加到result，如此循环，直到其中一个数组长度为0,同时result合并截取后的2个数组。
*/

function merge(left, right){
    var result  = [],
        il      = 0,
        ir      = 0;

    while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }

    return result.concat(left.slice(il)).concat(right.slice(ir));
}

/**
mergeSort不断拆分均分数组，直到数组长度为1或0，然后利用merge不断合并


**/
function mergeSort(myArray) {
    if(myArray.length < 2){
        return myArray;
    }

    var middle = Math.floor(myArray.length / 2),
        left = myArray.slice(0,middle),
        right = myArray.slice(middle),
        params = merge(mergeSort(left),mergeSort(right));


    //返回的数组头部加2个参数，0 和数组长度
    params.unshift(0,params.length);

    /**
     * splice的参数无法直接使用数组，所以使用apply，
     * 第一个参数是开始的位置，第二参数删除元素的个数，
     其余参数为需要添加进数组的元素

     这样做的原因是避免产生新数组，占用多余空间，直接在原数组修改
     *
     * */
    myArray.splice.apply(myArray,params);


    return myArray;



}

---

5-快速排序

算法思路

先确认一个支点，所以小于支点的数值放到该点的左侧，大于支点的数值放到该点的右侧，然后对左右两侧重复上述操作，直到排序结束。

具体做法是：

1. 先确认支点，一般取数组中间值。

2. 建立数组两端的指针，左侧指针指向数组第一个元素，右侧指针指向数组最后一个元素。
3. 左侧指针指向元素值依次与支点比较大小，如果小于支点指针则向后移动，否则指针停止原地。
4. 右侧指针指向元素值依次与支点比较大小，如果大于支点指针则向前移动，否则指针停止原地。
5. 左右两侧指针的下标比较，如果左侧小于右侧则交换数值，而大于则本轮排序结束。
6. 重复以上步骤，排序结束。

以对数组[3,2,5,1,4] 进行从小到大排序为例，步骤如下：

1. 先确认支点，我们这里取中间值5。
2. 左侧指针指向数组第一个元素3，3小于5，指针向后移动一位，2小于5，指针向后移动一位，5等于5，指针停止移动。
3. 右侧指针指向数组最后一个元素4，4小于5，指针停止移动。
4. 左侧指针下标为2，右侧指针下标为4，所以交换数值，交换后数组为[3，2，4，1，5]
5. 左侧指针继续向后移动一位，1小于5，指针向后移动一位，5等于5，指针停止移动。
6. 右侧指针向前移动一位，1是小于5，指针停止移动。
7. 左右指针下标比较，左指针是4，右指针是3，左侧大于右侧，本轮排序结束。
8. [3,2,4,1]和[5],分别继续以上步骤，直到排序结束。

代码实现

//快速排序
function partition(myArray, left, right) {
    var pivot = myArray[Math.floor((left + right) / 2)],
        i = left,     //左侧下标
        j = right;    //右侧下标
        
    while (i <= j){

        while (myArray[i] < pivot){
            i++;
        }

        while(myArray[j] > pivot){
            j--;
        }

        if(i <= j){
            swap(myArray,i,j);
            i++;
            j--;
        }

    }
    return i;
}

function quickSort(myArray, left, right) {
    if(myArray.length < 2){ return myArray;}

    left = (typeof left !== 'number' ? 0 : left);
    right = (typeof right !== 'number' ? myArray.length - 1 : right);

    var index = partition(myArray, left, right);

    //递归
    if(left < index -1){
        quickSort(myArray,left,index - 1);
    }
    if(index < right){
        quickSort(myArray,index,right);
    }

    return myArray;


}

---

参考链接

排序算法