解剖排序算法

jiezi

5 年前

排序是计算机中对存储的数据执行最常见的操作之一。语法简单，却很精妙。在排序算法中绕不开的是循环，只有在深入学习排序算法时，才发现平时不起眼的循环语句不可小觑。

拿最简单的冒泡排序来说，道理我都懂，可为什么会想到两层嵌套的循环语句？为什么两层循环语句的条件会有所不同？两层循环的关联逻辑是什么？循环在冒泡中扮演着什么角色？循环是通过怎样的逻辑完成冒泡的？等等。这些问题的背后，都值得我们去探究。

在说正题之前，需要说一个小插曲。由于互联网寒冬，程序员们都有一种危机感。在这场危机中，程序员的筛选条件也变得更加苛刻。无论是前端还是后端，都最好能够熟悉掌握一些基础算法。所以说，刷算法题，也在程序员间流行起来了。我旁边的一同事，就刷到了一个有趣的算法，说是挺有意思的，就让我也尝试一下。讲真，作为一个前端，除了简单处理一下接口数据，还真没有训练过应试般的算法。

题目大致是这样的，在 n*n 的平面中，以一半的空间螺旋有序排满以 1 起始若干数字。
画图如下：

</center>

随着思考的深入，突然发现，这 tm 不就是一道数学题么？（原谅我说粗话了）
找出已知，列出未知，关联已知未知，就差列 x、y 了。

以下以 5*5 为例：

var arr = Array.from({length: 5}).map(item => ([]));
var i = 1;
function Sort(init, length){
    let m = init, n= init;
    while(m < length){arr[m++][init] = i++;
    }
    --m;
    while(n < length -1) {arr[--m][++n] = i++;
    }
    --n;
    while(n > init) {arr[m][n--] = i++;
    }
    if (length <= 3) return arr;
    Sort(n+1, length - 2);
}

console.log(Sort(0, 5), arr)

变动的就是未知，找出循环条件，关联已知，这样等式就算列出来了。在这里我把平面想像成平面坐标，m、n 当作 x、y 轴，数组就是坐标点的集合，数字螺旋折转的条件作为循环递归条件，就这样，一个粗糙的算法算是完成了。

虽然这和本次主题的关系不是很大，但是很受启发，让我觉得程序和数学果然存在着紧密的关系。回到这一小节，以最简单的 for 循环为例。

let arr = [1, 2, 3];
for(let i = 0;i < arr.length; i++){}

以上就是最简单的 for 循环写法，从这个简单的 for 语句，我们能够知道的是，第几次循环 i（即当前），循环的次数arr.length 及循环的驱动i++。很重要的一点就是，i 是随着循环递增的。循环就是这么简单，也没有什么其他魔力。

在排序算法中，还有一点需要注意的，那就是数组。在 JavaScript 中，数组元素在内存中并不是连续的。我们可以通过索引来引用相应位置的元素。更重要的是，我们通常操作数组元素的时候，并不是操作数组元素本身，而是该位置上的变量。我们可以想象成，每一个索引位置都是一个变量，然后通过给变量赋值数组元素。

循环和数组，如果单独使用倒也没什么。如果两者结合，你就会发现，随着循环的次数增加，数组索引也会递增，再结合一些逻辑，就可以把某些元素移动到制定的位置。

那么，都结合怎样的逻辑呢？

冒泡排序逻辑，通过两两比较，把较大的元素赋值给当前位置索引的后一索引位置，然后随着循环增加，当前索引也会递增，最终会把最大值推到末尾。然后把这个过程循环多次，最终把倒数第二大、倒数第三大 … 移到指定位置。

function bubbleSort(arr){
    let len = arr.length;
    for(let i = 0; i < len - 1; i++){for(let j = 0; j < len - 1 - i; j++){    // 递增更换当前元素；if (arr[j] > arr[j+1]){    // 相邻元素比较；[arr[j], arr[j+1]] = [arr[j+1], arr[j]];    // 位置互换；}
        }
    }
    return arr;
}

选择排序逻辑，比较当前数组元素，找出最小元素的索引，将该位置的元素移动指定位置。然后多次循环遍历，最终将剩下数组元素中第二小元素、第三小元素 … 移到指定位置。

function selectionSort(arr){
    let len = arr.length;
    for(let i = 0; i < len - 1; i++){
        let minIndex = i;
        for(let j = i + 1; j < len; j ++){    // 递增替换当前元素；if(arr[j] < arr[minIndex]){minIndex = j;    // 更新最小元素索引；}
        }
        [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];    // 与最小元素互换位置；}
    return arr;
}

插入排序逻辑，将当前的数组元素与之前的数组元素比较，并将其插入到适当位置。

function insertionSort(arr){
    let len = arr.length;
    for(let i = 1; i < len; i++){let temp = arr[i];
        let preIndex = i -1;
        while(preIndex >= 0 && arr[preIndex] > temp){arr[preIndex + 1] = arr[preIndex--];    // 该位置元素若小于当前元素，则将其后移动；}
        arr[preIndex+1] = temp;
    }
    return arr;
}

希尔排序算是插入排序的升级版本，插入排序是与之前的数组元素挨个进行比较，而希尔排序是以特定间隔进行多次分组比较，所以说在代码上很相似。

function shellSort(gap, arr){
    let len = arr.length;
    for(let i = 0; i < gap.length; i++){    // 以不同间隔分组比较；for(let j = gap[i]; j < len; j++){    // 以间隔的下一索引位置起始；let temp = arr[j];
            let preGapIndex = j - gap[i];
            while(preGapIndex >= 0 && arr[preGapIndex] > temp){    // 当前元素与之前固定间隔索引位置元素进行比较；arr[preGapIndex + gap[i]] = arr[preGapIndex];
                preGapIndex = preGapIndex - gap[i];
            }
            arr[preGapIndex + gap[i]] = temp;
        }
    }
    return arr;
}

归并排序逻辑，使用递归的方式将数组划分为更小的数组对，通过比较重新合成完整的数组。本文采用的是自顶向下的归并排序，还可以使用自底向上的归并排序。

function mergeSort(arr){
    let len = arr.length;
    if(len < 2) return arr;
    let middle = Math.floor(len/2);    // 分组；let left = arr.slice(0, middle);
    let right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right){
    let len = left.length + right.length;
    let result = [], m = 0, n = 0;
    left[left.length] = Infinity;
    right[right.length] = Infinity;
    for(let i = 0; i < len; i++){    // 循环的次数为新数组的长度；if(left[m] <= right[n]){    // 比较左右数组元素重新排列组合成新的数组；result[i] = left[m];
            m++;
        }else{result[i] = right[n];
            n++;
        }
    }
    return result;
}

快速排序逻辑，从数组中选出基准值，将大于基准值的元素移到右侧数组，将小于基准值的元素移到左侧数组，递归循环此操作直到数组为空。然后合并各组数组，最终得到排序后的新数组。

function quickSort(arr){if(arr.length < 1) return arr;
    let len = arr.length;
    let pivot = arr[0];    // 设置基准值；let lesser = [], greater = [];
    for(let i = 1; i < len; i++){if(arr[i] < pivot){lesser.push(arr[i]);    // 将小于基准值推至左侧；} else {greater.push(arr[i]);    // 将大于基准值推至右侧；}
    }
    return quickSort(lesser).concat(pivot, quickSort(greater));
}

over！

前言

循环

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序