10大排序

1.冒泡

 var arr = [3, 6, 8, 5, 4, 2, 1, 9, 7, 0];
    function m(arr) {
        for (var i = 0; i < arr.length - 1; i++) {
            for (var j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    var temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

2.选择

 function x(arr) {
        for (var i = 0; i < arr.length - 1; i++) {
            var index = i;
            for (var j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
                var temp = arr[i];
                arr[i] = arr[index];
                arr[index] = arr[i];
            }
        }
        return arr;
    }

3.插入

 function c(arr) {
        for (var i = 0; i < arr.length; i++) {
            var a = arr[i];
            for (var j = i - 1; j >= 0 && arr[j] > a; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = a;
        }
        return arr;
    }

4.快速

 function k(arr) {
        if (arr.length <= 1) { return arr }
        var p = Math.floor(arr.length / 2);
        var point = arr.splice(p, 1)[0];
        var left = [];
        var right = [];
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] < point) {
                left.push(arr[i]);
            } else {
                right.push(arr[i])
            }
        }
        return k(left).concat(point, k(right));
    }

5.归并

 function g(arr) {
        if (arr.length < 2) { return arr };
        var mid = Math.round(arr.length / 2);
        var left = arr.slice(0, mid);
        var right = arr.slice(mid);
        return b(g(left), g(right));
    }
    function b(left, right) {
        var a = [];
        while (left.length > 0 && right.length > 0) {
            if (left[0] < right[0]) {
                a.push(left.shift());
            } else {
                a.push(right.shift());
            }
        }
        while (left.length > 0) {
            a.push(left.shift());
        }
        while (right.length > 0) {
            a.push(right.shift());
        }
        return a;
    }

6.希尔排序

            function sell(arr) {
                for (var gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {     
                    var a;
        // 数组遍历 i从第一个增量开始  从后面的比前面的
                    for (var i = gap; i < arr.length; i++) {
        // 定义一个变量储存当前的这个数
                        a = arr[i];
                        var j = i;
        // gap不变  是数组前半段    a是gap后面的数
                        while (j - gap >= 0  && arr[j - gap] > a) {
                            arr[j] = arr[j - gap];
                            j = j - gap;
                        }
                        arr[j] = a;
                    }
                }
                return arr;
            }

7.堆

 var len;   // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量
    function buildMaxHeap(arr) {  // 建立大顶堆
        len = arr.length;
        for (var i = Math.floor(len / 2)-1; i >= 0; i--) {//以他的父节点来进行判断
            //i ==取出来的父节点 
            heapify(arr, i);
            console.log(i);     
        }
    }
    function heapify(arr, i) {    // 堆调整
        var left = 2 * i + 1,//左边子节点
            right = 2 * i + 2,//右边子节点
            largest = i;//把i当成大顶堆中的父节点
        if (left < len && arr[left] > arr[largest]) {//不存在的节点排除
            largest = left;//如果左边的子节点大于他的父节点 将其位置交换
        }
        if (right < len && arr[right] > arr[largest]) {
            largest = right;//如果右边的子节点大于他的父节点 将其位置交换
        }
        if (largest != i) {//如果largest不等于i,说明他不大于他两个子节点中得其中一个
            swap(arr, i, largest);//将位置交换
            heapify(arr, largest);//重新调用该方法   已达到维护完全二叉树的性质
        }
    }
    //交换位置方法
    function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    function heapSort(arr) {
        buildMaxHeap(arr);//建立新的大顶堆
        //因为 排序后 最顶部已经是最大的数 
        //这里需要将第一位和最后一位的位置更换  将最后一位取出来
        //这时候 就需要保证大顶堆的成立 则需要调用 堆调整的方法
        // arr.length - 1 最后一位  0 为第一位(即最大值或者最小值)
        for (var i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;//每一次父级-1
            heapify(arr, 0);//保证大顶堆的成立
        }
        return arr;
    }

8.基数

  // 定义数组,表示桶
        var counter = [];
        // maxDigit最大位数   _ _ _
        function sort(arr, maxDigit) {
            var mod = 10;
            var dev = 1;
            //放桶里面
            for (var i = 0; i < maxDigit; i++) {
                // 遍历数组,将所有数放入对应桶中
                for (var j = 0; j < arr.length; j++) {
                    // 得到此数所在的桶
                    // 123%10  3/1=3
                    // 123%100 23/10=2.3
                    // 123%1000 123/100=1.23  
                    var bucket = parseInt((arr[j] % mod) / dev);
                    // 当此桶为空时
                    if (counter[bucket] == null) {
                        // 声明此桶为二维数组 
                        counter[bucket] = [];
                    }
                    // 将对应的数放入对应桶中
                    counter[bucket].push(arr[j]);
                }

                //放数组 再放上边
                var pos = 0;
                // 遍历桶,将桶中的数依次放入数组中
                for (var j = 0; j < counter.length; j++) {
                    var value = null;
                    // 桶不为空时
                    if (counter[j] != null) {
                        // 数组不为空,删除数组首位元素
                        while ((value = counter[j].shift()) != null) {
                            // 放入新数组
                            arr[pos++] = value;
                        }
                    }
                }
                mod *= 10, dev *= 10
            }
            return arr;
        }

9.计数排序

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

推荐阅读更多精彩内容