在线客服
 工作时间
周一至周五 :8:00-21:00
周六至周日 :8:00-22:00

动画演示几种常见排序算法--桶排序、冒泡、鸡尾酒、插入、快速...

 

动画演示几种常见排序算法 -- 桶排序、冒泡、鸡尾酒、快速...(JavaScript 版)


  同学们,如果你手上有54张次序乱了的扑克牌,你要把它们重新排序,用什么方法?先想想再往看下吧。

  对计算机算法有兴趣,或想参加全国青少年信息学(计算机)奥林匹克联赛NOIP的同学们请特别留神咯,希望通过这篇文章,让大家对算法有个初步认识。

  这个时候已经有同学举手了,哈哈,请说说你的排序法吧!

  只要把凌乱的牌逐个往桌子上放就可以了,放的时候,注意要放到适当的位置上。比如,第一张牌是葵扇9,我就放到第一排第九个位置;第二张牌是方片A,就放到第四排的第一个位置,如此类推,如下图,最后把全部牌按次序收拾起来就可以了!



  非常好!这种方法也类似于计算机排序算法里的"桶排序"(Bucket sort)法哦!这个算法就好比有54个桶,编号0~53,每出现一张牌,就往对应编号的桶里面放,最后将所有桶的排序结果合并起来。这是一种非常快的排序算法哦~ 当然,这里也要告诉大家,计算机往往要处理大量数据,真正的桶排序算法要比这个复杂些,每个桶不是存放一张牌,而是一定区间范围的牌,例如黑桃A到黑桃K由一个桶存放,红桃A到红桃K由第二个桶存放,如此类推,54张牌需4个桶。类似的,计算机对数据排序时,例如要对大小为[1..1000]范围内的n个整数A[1..n]排序,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储(10..20]的整数,……集合B[i]存储((i-1)*10, i*10]的整数,i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序,这时可用别的排序法,如冒泡法,快速排序法,或者是以递归方式继续使用桶排序进行排序都可以。现在,我们已经掌握了桶排序的基本思路咯!我们也需要知道,这种方法的缺点是什么? 就是要有足够大的桌子! 对计算机来说,内存空间要足够大,才能对大量的数据用"桶排序"法进行排序哦!


  如果我们压根就没有桌子,只有一对手,怎么把54张牌排好序呢?

  聪明的同学们想到了,先比较第1、第2两张牌,小的放前面,大的放后面,再比较第2,第3张牌,也是小的放前面,大的放后面,如此类推,经过53次比较,最大的那张牌“大鬼”就肯定排在最后,归位了,沉底了,小的牌就排比较前,浮上来,冒泡了。然后进行第二次循环,也就是再比较开头的两张牌...... 这思路也就是计算机“冒泡排序”法哦!但这种方法很慢,是不是?那我们继续开动脑筋咯!


   又想到新方法了吧? 好的,好的,开动脑筋就能想到了哦~

   让我们看看不同方法的比较,来看 排序动画演示看看哪种算法速度快吧,老师提醒一句,不要用太大数组去测试冒泡排序,浏览器崩溃了我不管哦。如果有兴趣,还可以  下载源码


  每个浏览器测试得出的数据会不一样。比如我用chrome 测试 一般快速排序都会最快,IE 则根据数组长度有可能希尔最快。(微信浏览器看不了动画演示,可能检测到JS怕不安全)。

  冒泡排序:最简单,也最慢,貌似长度小于7最优。
  插入排序: 比冒泡快,比快速排序和希尔排序慢,较小数据有优势。
  快速排序:这是一个非常快的排序方式,V8的sort方法就使用快速排序和插入排序的结合。
  希尔排序:在非chrome下数组长度小于1000,希尔排序比快速更快。
  系统方法:在firefox下系统的这个方法非常快。



代码举例:
// ---------- 一些排序算法
// js 利用sort进行排序
systemSort: function(array) {
   return array.sort(function(a, b) {
       return a - b;
   });
},


// 冒泡排序
bubbleSort: function(array) {
   var i = 0,
   len = array.length,
   j, d;
   for (; i < len; i++) {
       for (j = 0; j < len; j++) {
           if (array < array[j]) {
               d = array[j];
               array[j] = array;
               array = d;
           }
       }
   }
   return array;
},


// 快速排序
quickSort: function(array) {
   //var array = [8,4,6,2,7,9,3,5,74,5];
   //var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
   var i = 0;
   var j = array.length - 1;
   var Sort = function(i, j) {

       // 结束条件
       if (i == j) {
           return
       };

       var key = array;
       var stepi = i; // 记录开始位置
       var stepj = j; // 记录结束位置
       while (j > i) {
           // j <<-------------- 向前查找
           if (array[j] >= key) {
               j--;
           } else {
               array = array[j]
               //i++ ------------>>向后查找
               while (j > ++i) {
                   if (array > key) {
                       array[j] = array;
                       break;
                   }
               }
           }
       }

       // 如果第一个取出的 key 是最小的数
       if (stepi == i) {
           Sort(++i, stepj);
           return;
       }

       // 最后一个空位留给 key
       array = key;

       // 递归
       Sort(stepi, i);
       Sort(j, stepj);
   }

   Sort(i, j);

   return array;
},

// 插入排序
insertSort: function(array) {

   // http://baike.baidu.com/image/d57e99942da24e5dd21b7080
   // http://baike.baidu.com/view/396887.htm
   //var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
   var i = 1,
   j, step, key, len = array.length;

   for (; i < len; i++) {

       step = j = i;
       key = array[j];

       while (--j > -1) {
           if (array[j] > key) {
               array[j + 1] = array[j];
           } else {
               break;
           }
       }

       array[j + 1] = key;
   }

   return array;
},

// 希尔排序
//Jun.array.shellSort(Jun.array.df(10000));
shellSort: function(array) {

   // http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
   // var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
   var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在维基上看到这个最优的步长 较小数组
   //var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//针对大数组的步长选择
   var i = 0;
   var stepArrLength = stepArr.length;
   var len = array.length;
   var len2 = parseInt(len / 2);

   for (; i < stepArrLength; i++) {
       if (stepArr > len2) {
           continue;
       }

       stepSort(stepArr);
   }

   // 排序一个步长
   function stepSort(step) {

       //console.log(step) 使用的步长统计
       var i = 0,
       j = 0,
       f, tem, key;
       var stepLen = len % step > 0 ? parseInt(len / step) + 1 : len / step;

       for (; i < step; i++) { // 依次循环列
           for (j = 1;
           /*j < stepLen && */
           step * j + i < len; j++) { //依次循环每列的每行
               tem = f = step * j + i;
               key = array[f];

               while ((tem -= step) >= 0) { // 依次向上查找
                   if (array[tem] > key) {
                       array[tem + step] = array[tem];
                   } else {
                       break;
                   }
               }

               array[tem + step] = key;

           }
       }

   }
   return array;
}

部分内容摘自:来源


©智少年教育咨询有限公司独家原创,版权所有,转载请注明出处。


报名咨询
 
 
联系人*
电话*
课程
咨询内容*
我想报读...
验证码*
 看不清?换一张