JavaScript 基础排序的实现(一)
作为一个有追求的前端,忙里偷闲(闲得发慌)地复习了一下基础的排序算法,以此文留念. 本篇主要记录O(n²)复杂度的基础算法O(nlogn)的算法将在下次有空(闲得发慌)时更新 在记录时发现Es6语法中的解构赋值与传统的中间变量交换相比效率低下,经过几次测试发现其耗时大约为交换中间变量的两倍 1.冒泡排序 众所周知排序最基础的算法,也就是大名鼎鼎的冒泡了,为了方便日后回顾还是简单提一下冒泡的原理: 其核心思想在于不停地比较相邻元素的大小关系,如果前面的比后面的大则两个元素互换位置(此处以顺序为例);每当一次大的循环后总能将当前剩余数中最大的数交换到数组的末尾,类似于一个泡泡从底部浮出水面,故得名冒泡算法.下方代码为未使用任何优化的原始冒泡算法. 其时间复杂度为O(n²)不需要额外空间; 1 //冒泡排序 2 function BubbleSort(arr) {//arr即需要排序的数组;本文后续中的arr均为此意 3 console.time('timer');//用于统计代码执行时间 4 for (let i = 0; i < arr.length; i++) { 5 for (let j = 0; j < arr.length; j++) { 6 if (arr[j] > arr[j + 1]) 7 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];//交换元素(解构赋值ES6) 8 } 9 } 10 console.timeEnd('timer'); 11 } 以一万个数构成的倒序(从大到小)数组变为顺序的时间如下图(与个人电脑及其它因素有关请勿较真)用解构赋值交换: 后续算法的时间均以同一数组测试 2.鸡尾酒排序 这种排序算法乃是对冒泡算法的一种小优化,其与冒泡的区别在于,在一趟排序中可以将一个最大的移到后端,同时将一个最小的移到前端,从而对冒泡算法进行优化 核心代码如下: //鸡尾酒排序 function CocktailSort(arr) { console.time('timer'); let [start, end] = [0, arr.length]; while (start < end) { //此循环与正常冒泡一致 for (let i = start; i < end; i++) { if (arr[i] > arr[i + 1]) [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; } end--;//由于数组最后一位已经是最大的所以没有必要再让其参与后续的排序 for (let i = end - 1; i >= start; i--) { if (arr[i] < arr[i - 1]) [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]]; } start++; } console.timeEnd('timer'); } 耗费时间如下 由于其本质与冒泡算法类似,虽然好上些许,但其本质仍为O(n²)的时间复杂度故时间并未得到太大的缩减(由于解构赋值的原因优化后的算法还不如不优化,是真的骚) 3.选择排序 选择排序也是大家所熟知的一种基础算法,其核心在于每一次选出最小(或最大)的一个数放到已经有序的数列后,经过如此重复操作后获得有序的数列 代码如下: //选择排序 function SelecttionSort(arr) { console.time('timer'); for (let i = 0; i < arr.length; i++) { let min = i;//min表示当前最小值的下标 for (let j = i + 1; j < arr.length; j++) { min = arr[j] < arr[min] ? j : min; //如果当前下标的值比arr[min]的值要小则以当前值替换 } [arr[i], arr[min]] = [arr[min], arr[i]]; } console.timeEnd('timer'); } 花费时间如下: 按理说同为n平方的复杂度时间耗费应该相差不大才对,结果由于交换次数的减少导致耗时大幅下降,感觉Js在这方面效率有点低 4.插入排序 插入排序的原理为将当前下标的数插入之前已经有序的数列中,从后往前遍历找到合适的位置后将值插入,并将该位置之后的元素依次后移从而进行排序 代码如下: function InsertionSort(arr) { console.time('timer'); for (let i = 1; i < arr.length; i++) { for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) { [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; } } console.timeEnd('timer'); } 同数组耗时如下: 总结:在Js的情况下交换数据应尽量少的使用解构赋值,虽然其便利性很强,但是当网页对性能要求较高时应减少解构赋值的使用,如果非用不可,在同等级时间复杂度算法的情况下应使用数字交换次数少的算法以提升页面性能
