排序算法javascript的实现与讲解

稿件来源: 阳光企业网站管理系统   撰稿作者: 太阳光   发表日期: 2013-11-18   阅读次数: 86   查看权限: 游客查看

插入排序,选择排序,快速排序,冒泡排序都是比较排序。

冒泡排序
冒泡的原理是让最大元素或者最小元素”浮起来“
 
思路
依次比较相邻的两个数,将小数放在前面,大数放在后面。
 
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)
共有0 条评论 发言请遵守【相关规定

网友评论

会员头像
发 表同步腾讯微博    验证码:  点击更新请先登陆
  • 暂无评论
关闭模块文章图片 article Pictrue
  • 我的妈妈爸爸
  • 基于koa2+mysql+vue2.0+Element阳光内容管理系统
  • 代码覆盖率工具 Istanbul 入门教程
  • 全栈工程师的武器——MEAN
  • 9款超炫的 CSS3 复选框(Checkbox)
  • 微信开发在线翻译功能
  • CSS3那些不为人知的高级属性
  • 给easyui的datebox添加清空事件
  • flash写字效果
  • kendoUI系列教程之DropDownList下拉菜单
  • kendoUI系列教程之datetimepicker日期时间选择
  • kendoUI系列教程之datepicker日期选择
  • kendoUI系列教程之combobox下拉列表框
  • kendoUI系列教程之colorpicker
  • kendoUI系列教程之calendar日历表
  • kendoUI系列教程之autocomplete自动补齐