极念网欢迎您!
javascript简单排序算法实现
作者:WAxes来源:博客园发布时间:2014/4/10 18:44:19查看数:60665

本文使用javascript实现几个简单排序算法,包括冒泡排序算法,插入排序算法,希尔排序算法,快速排序算法,选择排序算法。首先我们从最简单的冒泡排序算法看起:

 

冒泡排序

感觉这个是最简单的排序算法了。直接引用维基百科里的解释:

冒泡排序算法的运作如下:比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

原理相当容易理解:

 

实现代码如下:

var array = [],maxNum = 100; for(var i=0;i<maxNum;i++){ array.push(parseInt(Math.random()*maxNum)); } console.log("排序前:"+array); bubbleSort(array); console.log("排序后:"+array); function bubbleSort(array){ var end = array.length-1; while(end>0){ for(var i=0;i<end;i++){ if(array[i]>array[i+1]){ var md = array[i+1]; array[i+1] = array[i]; array[i] = md; } } end--; } }

 

插入排序

插入排序算法大概原理:遍历数组,取两个相邻数据a和b,a数据之前的数据为有序区,b数据之后的为无序区。如果b大于a,继续往下遍历。如果b小于a,则把b跟有序区里的值按<-方向进行比对,比b大的数据索引均加一。当遍历到小于或等于b的数据时,那个位置就是b应该呆的位置。用维基百科上的一张图,就能秒懂了!

 

插入排序

 

实现代码如下:

var array = [],maxNum = 100; for(var i=0;i<maxNum;i++){ array.push(parseInt(Math.random()*maxNum)); } console.log("排序前:"+array); insertSort(array); console.log("排序后:"+array); function insertSort(array){ for(var i=0;i<array.length;i++){ var a = i,b = i+1; if(array[a]>array[b]){ var j = b-1,ayb = array[b]; while(ayb<array[j]){ array[j+1] = array[j] j--; } array[j+1] = ayb; } } }

 

希尔排序

希尔排序算法大概原理:遍历的方法跟插入排序差不多,不一样的就是希尔排序是先将数组分成多列,对每一列里的数据进行排序,然后对列数进行N/2操作,再进行逐列排序,直至列数为1时,数组即排列完毕。 

 

实现代码如下:

var array = [],maxNum = 100; for(var i=0;i<maxNum;i++){ array.push(parseInt(Math.random()*maxNum)); } console.log("排序前:"+array); shellSort(array ,10); console.log("排序后:"+array); function shellSort(array , d){ // var d = d; while(d>=1){ sort(array , d); d = Math.floor(d/2) } } function sort(array , d){ var h = array.length/d; for(var i=0;i<d;i++){ for(var j=0;j<h;j++){ var a = i+j*d , b=a+d; if(array[a]>array[b]){ var g = a,ayb = array[b]; while(ayb<array[g]){ array[g+d] = array[g] g-=d; } array[g+d] = ayb; } } } }

 

快速排序

这个排序算法想了比较久,脑子没那么灵活,所以研究了好一会才弄懂原理。其实说白了就是取个key作为中间值,把比key大的数据扔右边,把比key小的扔左边,循环递归。

 

再详细说下快速排序算法原理(我理解的):取数组的一个数据作为key,一般取第一个数据,然后进行遍历,将比key大的值扔在右边,把比key小的值扔在左边。遍历的方法:定义变量i、j,i为0,j为数组最后一个元素的索引。首先先从j到i方向开始遍历,i不动。即是<--方向,当遍历到的数据比key小且比array[i]的值小的时候,交换array[i]和array[j]的值。然后停止j向i的运动,开始i向j方向进行遍历当遍历到的数据比key小且比array[j]的值大的时候,交换array[i]和array[j]的值。然后停止i向j的运动,再开始j向i方向进行遍历,如此循环,当i==j的时候,说明array[i]的位置就是key值应该在的位置,key值在的位置左边都是比key小的值,右边都是比key大的值。 这是第一次循环,所以把key作为中点把数据分成两边,然后再对两边同时进行递归。算到最后排序的开始点与结束点相差仅为1时,整个数组的排序就已经排序好了。

 

实现代码如下:

var array = [],maxNum = 100; for(var i=0;i<maxNum;i++){ array.push(parseInt(Math.random()*maxNum)); } console.log("排序前:"+array); quickSort(array , 0 , array.length-1); console.log("排序后:"+array); function quickSort(array , start , end){ //key是分割线 var i=start;j = end,key = array[start]; while(i<j){ while(i<j){ if(array[j]<=key&&array[j]<array[i]){ //j->i方向的遍历,如果比key小且比array[i]小,交换数据 var md = array[i]; array[i] = array[j]; array[j] = md; break; } j--; } while(i<j){ if(array[i]>=key&&array[i]>array[j]){ //i->j方向的遍历,如果比key大且比array[j]大,交换数据 var md = array[i]; array[i] = array[j]; array[j] = md; break; } i++; } } if(i-start>1){ //对key左边的数据进行递归排序 quickSort(array , start , i-1) } if(end-i>1){ //对key右边的数据进行递归排序 quickSort(array , i+1 , end) } }

 

选择排序

原理:将序列划分为无序和有序区,寻找无序区中的最小值和无序区的首元素交换,有序区扩大一个,循环最终完成全部排序。

 

实现代码如下:

var array = [],maxNum = 100; for(var i=0;i<maxNum;i++){ array.push(parseInt(Math.random()*maxNum)); } console.log("排序前:"+array); selectSort(array); console.log("排序后:"+array); function selectSort(array){ var i = 0; //无序区最小指针 while(i<array.length){ var index = 0 , min = null; //index为当前遍历到的地址,min存放最小值 for(var j=i;j<array.length;j++){ if(array[j]<min||min===null){ min = array[j]; index = j; } } if(array[i]!==min){ //提高排序稳定性,如果两个元素值相同则不交换 var md = array[i]; array[i] = array[index]; array[index] = md; } i++; } }

 

本文作者:WAxes(http://www.cnblogs.com/axes)

原文网址:http://www.cnblogs.com/axes/p/3657009.html