文章分类 Classification
排序算法javascript的实现与讲解
稿件来源: 阳光企业网站管理系统 撰稿作者: 太阳光 发表日期: 2013-11-18 阅读次数: 102 查看权限: 游客查看
插入排序,选择排序,快速排序,冒泡排序都是比较排序。
冒泡排序
冒泡的原理是让最大元素或者最小元素”浮起来“
思路
依次比较相邻的两个数,将小数放在前面,大数放在后面。
step1:比较第1个和第2个数,将小数放前,大数放后。比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。
step2:在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。
如此下去,重复以上过程,直至最终完成排序。
由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。
function bubble_sort(array) { var l = array.length; for (var i = 0; i < l-1; i++) { //注意我们只需要循环到倒数第二即可。因为这里取的任意一位数都是跟后面一位数做比较的。 for (var j = 1; j < l-i; j++) { //内嵌交换的次数是从第一个数比较到倒数第(总长减n)个数。 if (array[j] < array[j - 1]) { //发现前一位大于后一位数时 array[j] = [array[j - 1], array[j - 1] = array[j]][0]; //在这里交换元素,巧用 b=[a,a=b][0]互换变量方法 } } } return array; }
动画效果:
选择排序
选择排序原理与冒泡非常相似,不同的是只有找到目标才交互元素。这也是一种简单的排序算法。
思路
循环把最小或最大的元素找出来,扔到数组里的一端,以此类推。
首先在未排序数组中找到最小元素,找的方法可以利用不断判断并赋值的手段,即:设数组第一个元素array[0]为最小元素,那么“最小元素”在数组中的序号就为0,然后遍历数组,若数组第二个元素比它还要小,那么说明第二个为最小元素,把“0” 更新为“1”。
遍历完毕后,我们就知道这一系列的最小元素下标为“n”;直接拿出来存放到排序序列的起始位置(array[n])。然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列的n+1位置。
function select_sort(array) { var min,l = array.length;//缓存长度 for (var i = 0; i < l-1; i++) { //开始进行循环,同样只循环到倒数第二个元素 min = i;//假设是当前最小元素下标 for (var j = i + 1; j < l; j++) { //内嵌遍历从第i+1个元素开始循环 if (array[min] > array[j]){ min = j;//发现更小元素,更新下标 } } if (min != i) { array[i] = [array[min],array[min]=array[i]][0]; //如果最小元素变化了,就交互下标 } } return array; }
动画效果:
插入排序
非常简单,就是我们摸牌插牌的步骤!
思路
先建一个空数组A,然后循环原数组每次取一个数出来。从A数组最后一个数作比较,发现比这个数还小时,就插入到当前,否则当前的数向后移动一个位置,然后继续向前一位比较。每次比较数组都增大一个元素。
function insert_sort(array){ var l = array.length,arr = [];//新建一个空数组 for(var i = 0 ;i < l; i++){ var v = array[i];//循环整个数组,一次取一位数出来作比较 for(var j = arr.length; j>=0; j--){ if(j == 0){ arr[0] = v;//如果第一次比较或者是v小于数组的任何一位数时 }else{ if(v >= arr[j-1]){ arr[j] = v;//发现了不比v小的数,就替换当前的位置 break;//并跳出循环 }else{ arr[j] = arr[j-1];//新数组中每个比v大的数都向后移动一位 } //arr.splice(j-1,0,v);break;等同此功能 } } } return arr; }
动画效果:
快速排序
快速排序是目前最强大的排序算法,算法利用了递归的思想。
思路
从数组中挑出一个元素,称为 “基准”,这个可以直接利用length/2位置上从数组中截取出来。然后遍历数组,所有元素比基准值小的摆放在基准前面,其他不比基准值小的摆在基准的后面。
之后我们得到了一个这样的数组: array= 比基准小的部分组成的数组lArray+基准数+不比基准小的部分组成的数组rArray。
那么我们之后只需要再把lArray,rArray进行“同样的”处理即可~
这就需要用到 递归 的写法了。处理之后直到发现数组长度变成1了,不足以再分下去了,我们认为排序结束。
function quick_sort(arr) { var l = arr.length;//缓存数组长度 if(arr.length <= 1){return arr} //如果长度比1还小就不再排序了 var num = Math.floor(arr.length / 2);//取数组中间的那个数。注意length/2不一定是整数,用Math.floor取整 var numValue = arr.splice(num, 1)[0];//利用splice方法,取一个基准元素出来,注意语法 var left = [];//创建左边基准容器 var right = [];//创建右边基准容器 for (var i = 0; i < l - 1; i ++) { //开始遍历数组 必须 -1 因为已经截取了一个中间值 arr[i] < numValue ? left.push(arr[i]) : right.push(arr[i]); //相对于基准元素,比它小的在左边,比它大的在右边。 } return quick_sort(left).concat([numValue], quick_sort(right)); //递归,继续对左右数组进行操作。 }
动画效果:
以上各排序函数运行排序数组[3,32,12,83,0,42,12,24,74,357,987,23,577,235,74,287,63,865,246,63]十万次耗时结果比较表:
序号 | 排序函数 | 耗时 |
---|---|---|
1 | 冒泡法bubble_sort | 798ms |
2 | 选择法select_sort | 645ms |
3 | 插入法insert_sort | 285ms |
4 | 快速法quick_sort | 65ms |
可见快速算法之快!
关键词: js,算法,排序,sort 编辑时间: 2013-11-18 17:52:32
0
高兴0
支持0
搞笑0
不解0
谎言0
枪稿0
震惊0
无奈0
无聊0
反对0
愤怒
0%(0)
0%(0)
- 暂无评论
文章图片 article Pictrue
网友评论