用js实现各种排序

1. 冒泡排序

冒泡排序的思想就是不断进行相邻交换,较小的数字如同气泡般慢慢浮到上面。
优化:如果在排第i个元素时,没有交换任何元素,则排序已完成,无需继续遍历

function mSort(array){
    var flag=true;   //是否还要继续排序,排序优化
    for(var i=0;i<array.length-1 && flag;i++){
        flag=false;
        for(var j=array.length-2;j>=i;j--){
            if(array[j]>array[j+1]){
                var temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                flag=true;
            }
        }
    }
}

最好情况:O(n)
最坏情况:O(n^2)
平均情况:O(n^2)

2. 选择排序

选择排序的思想是每次遍历找到最小的元素,然后和相应位置的元素交换位置。

function sSort(array){
    for(var i=0;i<array.length-1;i++){
        //查找最小的元素
        var min=i;
        for(var j=i+1;j<array.length;j++){
            if(array[j]<array[min]){
                min=j;
            }
        }

        //交换位置
        var temp=array[i];
        array[i]=array[min];
        array[min]=temp;
    }
}

最好情况:O(n^2)
最坏情况:O(n^2)
平均情况:O(n^2)
略优于冒泡排序。

3.插入排序

插入排序的主要思想是将一个记录插入到已经安排好的有序表中,需要一个辅助空间来存放这个记录,以方便前面的元素进行右移。

function iSort(array){
    for(var i=1;i<array.length;i++){
        var temp=array[i];
        //将前面大于其的元素右移
        for(var j=i-1;array[j]>temp && j>=0;j--){
            array[j+1]=array[j];
        }
        //将记录插入对应位置
        array[j+1]=temp;
    }
}

最好情况:O(n)
最坏情况:O(n^2)
平均情况:O(n^2)
插入排序比冒泡和简单选择排序的性能要好。

4.快速排序

快速排序的主要思想是,通过一趟排序将待排序的记录分割成独立的两部分,其中一部分的关键字都比另一部分的关键字小,则可以对这两部分继续进行排序,以达到整个序列有序的状态。
最主要的就是要实现一个partition函数,可以选取一个枢轴,并将其放在一个合适的位置,使其左侧值都比它小,右侧值都比它大。

    //快速排序
    function qSort(array,low,high){
        if(low<high){
            var pivot=partition(array,low,high);

            //递归排序低子表和高子表
            qSort(array,low,pivot-1);
            qSort(array,pivot+1,high);
        }
    }

    //选取一个关键字,放置到合适的位置,左侧值都比其小,右侧值都比其大
    function partition(array,low,high){
        //设置枢值为第一个元素
        var pivotkey=array[low];

        //交替向中间扫描,直到两个指针指向同一个位置,即为枢值的位置
        while(low<high){
            while(high>low && array[high]>=pivotkey){
                high--;
            }
            swap(array,low,high);

            while(low<high && array[low]<=pivotkey){
                low++;
            }
            swap(array,low,high);
        }
        return low;
    }

    //交换数组中a和b的位置
    function swap(array,a,b){
        var temp=array[a];
        array[a]=array[b];
        array[b]=temp;
    }

    var array=[5,4,3,2,1];
    qSort(array,0,array.length-1);
    console.log(array);

快速排序的时间性能取决于其快速排序递归的深度,一般partition每次划分都比较均匀时,其递归树的深度为log2n+1,而每次partition划分时,需要对数组的部分做扫描,每一层的时间复杂度为n,所以其时间复杂度为O(nlogn)。
由于关键词的比较和交换时跳跃进行的,因此,快速排序是一种不稳定的排序方法。

5.归并排序

基本思想为分治策略,先将数组进行划分,然后再进行合并,关键点是实现两个数组的合并

//合并两个数组
function merge(left,right){
    var res=[];
    while(left.length>0 && right.length>0){
        if(left[0]<=right[0]){
            res.push(left.shift());
        } else {
            res.push(right.shift());
        }
    }
    return res.concat(left).concat(right);
}

//归并排序
function sort(arr){
    //直到数组的长度为1,则终止递归
    if(arr.length===1){
        return arr;
    }

    var mid=Math.floor(arr.length/2);
    var left=arr.slice(0,mid);
    var right=arr.slice(mid);
    return merge(sort(left),sort(right));
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,951评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,606评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,601评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,478评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,565评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,587评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,590评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,337评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,785评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,096评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,273评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,935评论 5 339
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,578评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,199评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,440评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,163评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,133评论 2 352

推荐阅读更多精彩内容

  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,729评论 0 15
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,178评论 0 52
  • 柴米油盐酱醋茶 是生活 琴棋书画诗词歌 是理想中的生活 听说 幸福很简单 只是我们不知足 听说 岁月可长留 只是渴...
    大清晨的小太阳阅读 157评论 0 0
  • 金融投资类公司暂停注册与壳交易的走俏 2016年初以来,全国很多省市已经开始暂停登记注册在名称、经营范围中含有金融...
    简法帮阅读 438评论 0 1