共计 3583 个字符，预计需要花费 9 分钟才能阅读完成。
前言
排序是计算机中对存储的数据执行最常见的操作之一。语法简单，却很精妙。在排序算法中绕不开的是循环，只有在深入学习排序算法时，才发现平时不起眼的循环语句不可小觑。
拿最简单的冒泡排序来说，道理我都懂，可为什么会想到两层嵌套的循环语句？为什么两层循环语句的条件会有所不同？两层循环的关联逻辑是什么？循环在冒泡中扮演着什么角色？循环是通过怎样的逻辑完成冒泡的？等等。这些问题的背后，都值得我们去探究。
循环
在说正题之前，需要说一个小插曲。由于互联网寒冬，程序员们都有一种危机感。在这场危机中，程序员的筛选条件也变得更加苛刻。无论是前端还是后端，都最好能够熟悉掌握一些基础算法。所以说，刷算法题，也在程序员间流行起来了。我旁边的一同事，就刷到了一个有趣的算法，说是挺有意思的，就让我也尝试一下。讲真，作为一个前端，除了简单处理一下接口数据，还真没有训练过应试般的算法。
题目大致是这样的，在 n*n 的平面中，以一半的空间螺旋有序排满以 1 起始若干数字。
画图如下：
<center>
</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！
