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