当前位置:首页 > 短网址资讯 > 正文内容

【FT12短网址】借助JavaScript实现几种常见的排序算法

www.ft12.com4年前 (2017-08-15)短网址资讯1223

引言

排序算法有千千万万种,实现的代码也有很多,比如php, html5, JS等等。但是我们常见的排序算法也就几种而已,比如按大小升序或者降序;比如按字母先后顺序排序;比如按字符长度排序等等。

排序算法是所有算法中最基础的基础。虽然关键在于算法的思想而不是语言,但还是决定借助算法可视化工具结合自己常用的语言实现一遍。

目录

  • 冒泡排序

  • 选择排序

  • 插入排序

  • 合并排序

  • 快速排序

为了方便说明,默认按从小到大排序

1.冒泡排序

基本思路:

1.依次比较相邻的两个数,如果第一个比第二个小,不变。如果第一个比第二个大,调换顺序。一轮下来,最后一个是最大的数

2.对除了最后一个之外的数重复第一步,直到只剩一个数

图形展示:




代码:

function bubbleSort(myArray){
 var len = myArray.length;
 var i;
 var j;
 var stop;

 for (i = 0; i < len - 1; i++){
   for (j = 0, stop = len - 1 - i; j < stop; j++){
     if (myArray[j] > myArray[j + 1]){
       swap(myArray, j, j + 1);
     }
   }
 }
 return myArray;
}

function swap(myArray, p1, p2){
 var temp = myArray[p1];
 myArray[p1] = myArray[p2];
 myArray[p2] = temp;
}

2.选择排序

基本思路:

1.找出最小的数,和第一个交换位置

2.在剩下的数中,找出最二小的数,放在第二个

3.依次类推,排出顺序

图形展示:




代码:

function selectionSort(myArray){

   var len = myArray.length,
       min;

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

       // 将当前位置设为最小值
       min = i;

       // 检查数组其余部分是否更小
       for (j=i+1; j < len; j++){
           if (myArray[j] < myArray[min]){
               min = j;
           }
       }

       // 如果当前位置不是最小值,将其换为最小值
       if (i != min){
           swap(myArray, i, min);
       }
   }

   return myArray;
}
function swap(myArray, p1, p2){
   var temp = myArray[p1];
   myArray[p1] = myArray[p2];
   myArray[p2] = temp;
}

3.插入排序

基本思路:

1.把数组分为[已排序]和[未排序]两部分,第一个数为[已排序],其余为[未排序]

2.从[未排序]抽出第一个数,和[已排序]部分比较,插入到合适的位置

图形展示:




代码:

function insertionSort(myArray) {

   var len     = myArray.length,     // 数组的长度
       value,                      // 当前比较的值
       i,                          // 未排序部分的当前位置
       j;                          // 已排序部分的当前位置

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

       // 储存当前位置的值
       value = myArray[i];

       /*
        * 当已排序部分的当前元素大于value,
        * 就将当前元素向后移一位,再将前一位与value比较
        */

       for (j=i-1; j > -1 && myArray[j] > value; j--) {
           myArray[j+1] = myArray[j];
       }

       myArray[j+1] = value;
   }

   return myArray;
}

4.合并排序(分而治之)

基本思路:

1.不断将数组对半分,直到每个数组只有一个

2.将分出来的部分重新合并

3.合并的时候按顺序排列

图形展示:



代码:


// 被拆分的数组重新合并
function merge(left, right) {
   var result = [],
       left_index = 0,
       right_index = 0;

   // 将两个数组合并
   // 合并的时候按从小到大的顺序
   while (left_index < left.length && right_index < right.length) {
       if (left[left_index] < right[right_index]) {
           result.push(left[left_index++]);
       } else {
           result.push(right[right_index++]);
       }
   }

   // 和其他数组拼接
   return result.concat(left.slice(left_index)).concat(right.slice(right_index));
}

function mergeSort(myArray) {
   // 只有一个数的时候退出递归
   if (myArray.length < 2) {
       return myArray;
   }

   var middle = Math.floor(myArray.length / 2),
       left = myArray.slice(0, middle),
       right = myArray.slice(middle);

   // 递归
   // 不断拆分只到一个数组只有一个数
   return merge(mergeSort(left), mergeSort(right));
}

5.快速排序

基本思路:

1.以一个数为基准(中间的数),比基准小的放到左边,比基准大的放到右边

2.再按此方法对这两部分数据分别进行快速排序(递归进行)

3.不能再分后退出递归,并重新将数组合并

图片展示:




代码:

var quickSort = function(myArray) {  
// 当被分的数组只剩一个时,退出递归
if (myArray.length <= 1) {
return myArray;
  }

// 中间基准值的index
var pivotIndex = Math.floor(myArray.length / 2);  
// 基准值
var pivot = myArray.splice(pivotIndex, 1)[0];  
var left = [];  
var right = [];  
// 小的放左边,大的放右边
for (var i = 0; i < myArray.length; i++) {    
if (myArray[i] < pivot) {  
left.push(myArray[i]); 
      } else {
right.push(myArray[i]); 
      }  
  }  
// 递归
// 把数组合并在一起
return quickSort(left).concat([pivot], quickSort(right));
};



扫描二维码推送至手机访问。

版权声明:本文由短链接发布,如需转载请注明出处。

本文链接:https://www.ft12.com/article_409.html

标签: 算法排序JS
分享给朋友:

相关文章

人人网,微博等网站在分享url的时候都会转换成短链接,这样有什么好处?

比如 http://u6.gg/baidu【李卿的回答(9票)】:正如@sqybi 所说,初衷应该是微博类网站为了缩短字数,毕竟这些地方惜字如金。前几位都说到了垃圾外链的问题,其实这个并不是大问题,是可以用nofollow属性来处...

央行担心升值太快,人民币大逆转!

央行担心升值太快,人民币大逆转!

人民币大逆转!央行担心升值太快原上草人民币的走势非常神秘,经常会出现一些我们预想不到的情形,比如,对内物价上涨,表现为贬值,对外却不断升值;再比如,经济形势不太好,大家都认为要贬值的时候,它突然180度大转弯,来了个措手不及的升值。截止到上...

解密京东短网址大规模内存数据库的演进之路

解密京东短网址大规模内存数据库的演进之路

京东商城研发体系基础平台团队:包括大规模容器集群调度、数据库与存储技术、消息系统与服务框架、架构与运维、机器学习与人工智能等技术方向。由京东商城首席架构师刘海锋担任部门负责人。基础平台运营多个数据中心数万台服务器,支撑京东无数在线业务。缓存...

从产品、市场、投资等,深入了解与分析共享充电宝

从产品、市场、投资等,深入了解与分析共享充电宝

从4月开始,继共享单车之后,共享充电宝突然为科技创投圈所青睐。共享充电宝前景如何?本文作者从产品、市场、投资等多个维度对此进行了分析,共享充电宝的未来似乎并不那么扑朔迷离。忽如一夜春风来,千树万树梨花开。今年春天,共享充电宝火了。3月31日...

浅析无人驾驶技术未来发展的六大方向

浅析无人驾驶技术未来发展的六大方向

[ FT12短网址资讯 ] 许多创业公司和大型公司的终极目标是改动上个世纪的交通形式,从私人具有轿车转向同享无人驾驶车队,从而依照需要使用轿车。这种愿景经常与内燃机向电动轿车的转移融合起来。科技一直以来都是轿车研发的关键,但过去几...

FT12短网址:太聪明的人,往往会失败的很离谱

FT12短网址:太聪明的人,往往会失败的很离谱

有傻瓜的当地才会发作奇观印度有一位闻名的哲学家,气质高雅,因而变成很多女性的偶像。某天,一个女子来访问他,她表达了爱慕之情后说:“错过我,你将再也找不到比我更爱你的女性了!”哲学家尽管也很中意她,但仍习气性地答复说:“容我再思考思考!”过后...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。