Js中的冒泡排序、选择排序、快速排序、桶排序原理
今天是元宵佳节,在此小编祝大家元宵佳节快乐!年味儿渐散,收拾下心情,继续敲代码吧。对于即将到来金三银四的求职季,相信不少同学都在默默地做着准备。面对前端越来越多的算法面试题,我简单的整理了一下几种比较常见的数组排序方式,分别介绍其基本原理和优劣势。(ps:才疏学浅,希望大家可以在讨论区下面指出问题)。
先来看一张图:
图片名词解释:
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存,不占用额外内存
Out-place: 占用额外内存
冒泡排序
1.冒泡排序原理
冒泡排序我先介绍说它的原理,你就明白它为什么叫冒泡排序了。有一个待排序的数组 [8, 3, 5, 9, 2, 3, 0, 8] ,需要由小到大排序。我们只需要把小的放在左边,大的放右边是不是就完成了排序呢?显然是的。将第一个 8 与 第二位 3 比较,8 大于 3,所以我们把 8 往右放,即将 8 与 3 更换位置,更换后的数组是 [3, 8, 5, 9, 2, 3, 0, 8] ,继续比较改变后的数组第二位 8 与 第三位 5 比较,8 大于 5,更换后的数组是 [3, 5, 8, 9, 2, 3, 0, 8],重复这样的操作,如果遇到相同或者当前数值小于后一位的则不需要改变,继续比较下一位即可。所以看这 8 的移动轨迹,像不像是一个气泡在往上冒,所以这个排序方法就叫冒泡排序。
1.1 原始人冒泡排序
function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { //相邻元素两两对比 var temp = arr[j+1]; //元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
这种算法不多说,有点编程基础的人都能看明白,可以说是“傻瓜排序” 。
1.2 进化版冒泡排序
function bubbleSort2(arr) { console.time('改进后冒泡排序耗时'); var i = arr.length-1; //初始时,最后位置保持不变 while ( i> 0) { var pos= 0; //每趟开始时,无记录交换 for (var j= 0; j< i; j++){ if (arr[j]> arr[j+1]) { pos= j; //记录交换的位置 var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; } } i= pos; //为下一趟排序作准备 } console.timeEnd('改进后冒泡排序耗时'); return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
“进化版”冒泡排序算法相对于“原始人”冒泡排序有个亮点,就是每一层的循环都记录上一次排序的位置,这两种排序算法都是先排最后一位,最后一位是最大的,然后以此类推。细细推敲第二种方法显然比第一种方法少走了一些冤枉路,也就是说每一层排完序之后,就记录排到最大的哪一位在什么位置,因为每一层最大的数就是它所在数组的倒数的位数,因此下一次就没必要再循环一遍,相对于第一种就少进行了很多计算。
1.3.升级版冒泡排序
function bubbleSort3(arr3) { var low = 0; var high= arr.length-1; //设置变量的初始值 var tmp,j; console.time('2.改进后冒泡排序耗时'); while (low < high) { for (j= low; j< high; ++j) { //正向冒泡,找到最大者 if (arr[j]> arr[j+1]) { tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; } } --high; //修改 high 值, 前移一位 for (j=high; j>low; --j) { //反向冒泡,找到最小者 if (arr[j]<arr[j-1]) { tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp; } } ++low; //修改 low 值,后移一位 } console.timeEnd('2.改进后冒泡排序耗时'); return arr3; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
这种排序方式也算是锦上添花,因为前两次的排序都是按最大或者最小方向进行排序,而第三种方法会选择从两头出发一起计算,双管齐下!
1.4 自创版冒泡排序
function bubbleSort3(arr3) { var low = 0; var high= arr.length-1; //设置变量的初始值 var tmp,j; console.time('3.改进后冒泡排序耗时'); while (low < high) { var pos1 = 0,pos2=0; for (let i= low; i< high; ++i) { //正向冒泡,找到最大者 if (arr[i]> arr[i+1]) { tmp = arr[i]; arr[i]=arr[i+1];arr[i+1]=tmp; pos1 = i ; } } high = pos1;// 记录上次位置 for (let j=high; j>low; --j) { //反向冒泡,找到最小者 if (arr[j]<arr[j-1]) { tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp; pos2 = j; } } low = pos2; //修改 low 值 } console.timeEnd('3.改进后冒泡排序耗时'); return arr3; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
既然每次记录位置可以减少计算,两头算双管齐下也能减少计算,那么思考,如果每次记录位置而且还两头算是不是会更加省事呢?(根据 1.2,1.3 自创)
但是冒泡排序也有弊端,就是两种极端的情况,一种是数据本来就是正序,那做的就是无用功,另外一种就是反序,不想理你。。。具体怎么弊端想想也就知道了
冒泡排序动图演示
选择排序
选择排序原理
选择排序从数组内遍历出最大值,加入新数组,将最大值从原数组中删除,重复上述操作,最后得出的新数组就是一个从大到小排序的数组了。
function selectionSort(arr) { var len = arr.length; var minIndex, temp; console.time('选择排序耗时'); for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { //寻找最小的数 minIndex = j; //将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } console.timeEnd('选择排序耗时'); return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
经小编测试,选择排序似乎比冒泡排序的自创版还要省时间,其实选择排序适合小数据排序,具体这个小数据有多小呢,简单的测试了一下,在 1000 条以内的数据,选择排序更胜 1.3 冒泡排序。
选择排序动图
快速排序
快速排序排序原理
快速排序的优点就是速度快,为什么速度快呢?我先介绍一下快速排序的原理。选择一个基准值,一般选择数组的一个值,遍历数组,大的放右边,小的放左边,一样大的放中间(哈哈哈哈哈😀),利用递归重复对大的数组和小的数组进行拆分,最后得出排序后的数组。
3.1 抽象版快速排序
function quickSort(array, left, right) { console.time('1.快速排序耗时'); if (left < right) { var x = array[right], i = left - 1, temp; for (var j = left; j <= right; j++) { if (array[j] <= x) { i++; temp = array[i]; array[i] = array[j]; array[j] = temp; } } console.log(array) ; console.log(left,i) ; quickSort(array, left, i - 1); console.log(array) console.log(i,right) quickSort(array, i + 1, right); } console.timeEnd('1.快速排序耗时'); console.log(array) return array; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
看完代码一脸懵逼,这是人写的么?瞬间觉得自己弱爆了,连别人代码都看不懂,更别说自己写了,别着急,一点点拆分看。
先看一个疑问点,函数中的参数有三个,第一个数组,没得说;第二个是左值,第三个是右值;好,到这里先分析结束,首先给读者一种什么感觉,就是这个排序算法是从左右两端依次逼近完成排序的,那么对于这个猜想对不对呢?
接着看,if 条件语句中判断 left < right,这没得说,就是从左到右排序的,而且 if 如果不成立直接结束本层循环了,那如果满足条件呢,直接进入 for 循环,而且在进入 for 循环之前先记录了一个本次循环的末尾值,又设置一个 i ,还有一个空变量,都分别又是什么意思呢?
接着看,for 循环遍历本层循环,然后依次和末尾值进行比较,那么可想而知,这个变量 x 无非就是个基数,好了,算法的亮点来了,就是 i 值,如果本层循环某个元素大于本层循环的基数,那么置换两者的位置,那么 i 的作用就是计数的作用,而 temp 就是作为交换暂时存储的介质,然后这样下来就是把每次本层循环的最大值放到了最后,这样下来在 quickSort(array, left, i – 1);不断递归循环之后,该数组的右边最小值大于左边的最大值(这里的左边和右边不一定等分),而且左边的顺序已经排好了,然后同理排右边的部分,这样下来函数结束之后就完成了排序。(暂时小编能理解的大概就是这种程度了,不当之处,还望博友指点一二)。
3.2 形象版快速排序
var quickSort2 = function(arr) { console.time('2.快速排序耗时'); if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; console.log(pivot) var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } console.timeEnd('2.快速排序耗时'); return quickSort2(left).concat([pivot], quickSort2(right)); }; var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(quickSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
看完第一种写法之后,有种放弃的念头,不要着急,慢慢拨开迷雾你能感受到快速排序的奇特之处。
废话不多说直接看代码,第二种开始还能理解,哦,原来和第一种写法类似,第二种则是选择中中间数作为基数进行比较,然后再遍历比较,把比中间值小的放在 left 数组,把比中间值大的放在 right 数组中,这种写法再简单不过了,而看到后面 return quickSort2(left).concat([pivot], quickSort2(right)); 这是什么鬼?是不是写错了,怎么感觉那么不对劲呢?不要怀疑经典,拆分代码看,哦,原来是不断把数组细分化,分到数组长度为 1 的最小单位,然后再把左右两个数组拼凑起来,试想每层基循环都有左右两个长度为 1 的数组,且左数组元素比右数组元素值小,而基循环的基数又是两基数组元素的中间数,那这不就比较完了吗,把三者拼凑起来不正是排序后的序列么,使用递归依次类推形成最后的数组。就是这么简单,完毕。
配上一个动图,第一次看可能会很懵逼,配合代码多看几遍或许能明白其巧妙之处。
桶排序
桶排序原理
一看到这个名字就会觉得奇特,几个意思,我排序还要再准备几个桶不成?还真别说,想用桶排序还得真准备几个桶,但是此桶非彼桶,这个桶是用来装数据用的。桶排序顾名思义,就是准备好一些“桶”,然后将待排序的数组值一个个放入对应的“桶内”,全部元素放入”桶“后,然后展开”桶“就得到了排序完成的数组了。比如:当前需要排序的数组 [8, 3, 5, 9, 2, 3, 0, 8],我们可以准备一个长度为 10 的数组,每一项的值为 0,我们对需要排序的数组开始便利,当我们遇到 8 时,我们将 newList[8]内的 0,加 1,改成 1;然后下一个 3,我们将 newList[3]内的 0,加 1,改成 1…,处理完所有元素后,将 newList 便利输出就得到了排序好的数组了。当然了这里只是简单的对桶排序的介绍,真正的桶排序肯定比这个复杂。
@param array 数组 @param num 桶的数量 function bucketSort(array, num) { if (array.length <= 1) { return array; } var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0; var index = Math.floor(len / num) ; while(index<2){ num--; index = Math.floor(len / num) ; } console.time('桶排序耗时'); for (var i = 1; i < len; i++) { min = min <= array[i] ? min : array[i]; max = max >= array[i] ? max : array[i]; } space = (max - min + 1) / num; //步长 for (var j = 0; j < len; j++) { var index = Math.floor((array[j] - min) / space); if (buckets[index]) { // 非空桶,插入排序 var k = buckets[index].length - 1; while (k >= 0 && buckets[index][k] > array[j]) { buckets[index][k + 1] = buckets[index][k]; k--; } buckets[index][k + 1] = array[j]; } else { //空桶,初始化 buckets[index] = []; buckets[index].push(array[j]); } } while (n < num) { result = result.concat(buckets[n]); n++; } console.timeEnd('桶排序耗时'); return result; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bucketSort(arr,4));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
但是这边有个坑点,就是桶的数量不能过多,也就说说至少两个桶!为什么?你试下就知道了!
附图理解:
以上就是我个人对排序算法的理解,如有不当之处请在下方留言指点一二,也为其他小伙伴提供更正确的帮助。
码云笔记 » Js中的冒泡排序、选择排序、快速排序、桶排序原理
学习了
快排的缺点就是稳定性不如归并,最好情况和最坏情况差不多
你说的对