前端技术交流群:565733884

Js中的冒泡排序、选择排序、快速排序、桶排序原理

前端技术 码云 100℃ 0评论

今天是元宵佳节,在此小编祝大家元宵佳节快乐!年味儿渐散,收拾下心情,继续敲代码吧。对于即将到来金三银四的求职季,相信不少同学都在默默地做着准备。面对前端越来越多的算法面试题,我简单的整理了一下几种比较常见的数组排序方式,分别介绍其基本原理和优劣势。(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中的冒泡排序、选择排序、快速排序、桶排序原理

喜欢 (14)or分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(3)个小伙伴在吐槽
  1. 学习了
    Actor2019-02-27 09:40 回复
  2. 快排的缺点就是稳定性不如归并,最好情况和最坏情况差不多
    CringKong2019-02-19 15:37 回复