文档章节

JS数据结构与算法 - 排序(冒泡、选择、插入、归并、快排)

o
 osc_ccy4urvn
发布于 07/14 09:23
字数 1520
阅读 35
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

🌸本文主要内容:

时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)

js默认sort算法于各浏览器中的实现

冒泡排序O(n^2)

冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。

function bubbleSort(array) {
    let length = array.length
    for (let i = 0; i < length; i++) { //控制了在数组中经过多少轮排序
        for (let j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                let temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
            }
        }
    }
    return array
}

选择排序O(n^2)

选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。

function selectSort(array) {
    let length = array.length
    let indexMin //记录每次最小值所在的位置
    for (let i = 0; i < length; i++) {
        indexMin = i
        // 开始查找i以及i之后的最小值
        for (let j = i; j < length; j++) {
            if (array[indexMin] > array[j]) {
                indexMin = j
            }
        }
        if (i != indexMin) {
            let temp = array[i]
            array[i] = array[indexMin]
            array[indexMin] = temp
        }
    }
    return array
}

插入排序O(n^2)

插入排序每次排一个数组项,以此方式构建最后的排序数组。假定第一项已经排序了,接着,它和第二项进行比较,第二项是应该待在原位还是插到第一项之前呢?这样,头两项就已正确排序,接着和第三项比较(它是该插入到第一、第二还是第三的位置呢?),以此类推。

function insertSort(array) {
    let length = array.length
    for (let i = 0; i < length; i++) {
        j = i
        temp = array[i]
        while (j > 0 && array[j - 1] > temp) {
            // 交换位置
            array[j] = array[j - 1]
            j--
        }
        array[j] = temp
    }
    return array
}

归并排序O(nlogn)

归并排序是第一个可以被实际使用的排序算法。前三个排序算法性能不好,但归并排序性能不错,其复杂度为O(nlogn)

归并排序是一种分治算法。其思想是将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。点击查看归并排序小动画

// 创建
function Sort() {
    this.mergeSort = function (array) {
        return  mergeSortRec(array);
    };

    var mergeSortRec = function (item) {
        var length = item.length;
        if (length === 1) { //递归停止条件
            return item;
        }
        var mid = Math.floor(length / 2), //将数组分为左右两部分
            left = item.slice(0, mid),
            right = item.slice(mid, length);
        return merge(mergeSortRec(left), mergeSortRec(right));
    };

    // 负责合并和排序小数组来产生大数组
    var merge = function (left, right) {
        // console.log(left,right)
        var result = [],
            il = 0,
            ir = 0;
        //例子: [7,8],[5,6]
        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }
        while (il < left.length) {
            result.push(left[il++]);
        }
        while (ir < right.length) {
            result.push(right[ir++]);
        }
        // console.log(result)
        return result;
    };
}

// 使用
let sort = new Sort()
console.log(sort.mergeSort([2,3,4,5,2,1]))

快速排序O(nlogn)

快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn),且它的性能通常比其他的复杂度为O(nlogn)的排序算法要好。和归并排序一样,快速排序也使用分治的方法,将原始数组分为较小的数组(但它没有像归并排序那样将它们分割开)。

(1) 首先,从数组中选择中间一项作为主元。

(2) 创建两个指针,左边一个指向数组第一个项,右边一个指向数组最后一个项。移动左指针直到我们找到一个比主元大的元素,接着,移动右指针直到找到一个比主元小的元素,然后交换它们,重复这个过程,直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前,比主元大的值都排在主元之后。这一步叫作划分操作。

(3) 接着,算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的子数组)重复之前的两个步骤,直至数组已完全排序。

图示:点击可看大图。或者点击查看快速排序小动画

// 创建
function Sort() {
    this.quickSort = function (array) {
        quick(array, 0, array.length - 1);
    };

    //声明一个主方法来调用递归函数,传递待排序数组,以及索引0及其最末的位置(因为我们要排整个数组,而不是一个子数组)作为参数。
    var quick = function (item, left, right) {
        var index;
        if (item.length > 1) {
            index = partition(item, left, right); //index帮助将数组分离为较小的和较大的数组
            if (left < index - 1) { //如果子数组存在较小值的元素
                quick(item, left, index - 1); //对该数组重复该过程
            }
            if (index < right) { //同理
                quick(item, index, right);
            }
        }
    };

    //划分过程
    var partition = function (item, left, right) {
        var pivot = item[Math.floor((right + left) / 2)], //选择主元(可随机),这里选择中间值
            i = left,
            j = right;
        while (i <= j) { //只要左右指针没有相互交错,就执行划分操作
            while (item[i] < pivot) { //移动left指针直到找到一个元素比主元大
                i++;
            }
            while (item[j] > pivot) { //移动right指针直到找到一个元素比主元小
                j--;
            }
            if (i <= j) { //左右指针没有相互交错
                swapQuickStort(item, i, j); //交换值
                i++; //继续往下走
                j--;
            }
        }
        return i; //此刻顺序 比主元小 主元 比主元大。返回分界指针到quick()相应语句中
    };

    var swapQuickStort = function (item, index1, index2) {
        var aux = item[index1];
        item[index1] = item[index2];
        item[index2] = aux;
    };
}

// 使用
let quickSort = new Sort()
let array = [4, 5, 1, 6, 2, 7, 3, 8]
quickSort.quickSort(array)
console.log(array)

推荐文章

Array.prototype.sort 各浏览器的算法实现

维基百科 - 排序算法(讲解了各种排序算法,超多超详)

选择排序小动画

冒泡排序小动画

o
粉丝 0
博文 84
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
3.9K
3
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
树莓派(Raspberry Pi):完美的家用服务器

自从树莓派发布后,所有在互联网上的网站为此激动人心的设备提供了很多有趣和具有挑战性的使用方法。虽然这些想法都很棒,但树莓派( RPi )最明显却又是最不吸引人的用处是:创建你的完美家用...

异次元
2013/11/09
5.4K
8
桌面即时贴软件--GloboNote

GloboNote 是一个桌面记事软件,可帮你创建待办事宜、提醒和其他笔记信息。无限制即时贴的数量,可分组整理,支持搜索,可定制文本的显示格式(字体、颜色和大小),可将某个即时贴始终显示在...

匿名
2013/01/21
6.7K
1
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2

没有更多内容

加载失败,请刷新页面

加载更多

如何在Android中以像素为单位获取屏幕尺寸 - How to get screen dimensions as pixels in Android

问题: I created some custom elements, and I want to programmatically place them to the upper right corner ( n pixels from the top edge and m pixels from the right edge). 我创建......

javail
58分钟前
7
0
如何在不安装Microsoft Office的情况下用C#创建Excel(.XLS和.XLSX)文件?

问题: 如何在不使用运行代码的计算机上安装Excel的情况下使用C#创建Excel电子表格? 解决方案: 参考一: https://stackoom.com/question/dHZ/如何在不安装Microsoft-Office的情况下用C-创...

技术盛宴
今天
7
0
如何使用pip升级所有Python软件包? - How to upgrade all Python packages with pip?

问题: Is it possible to upgrade all Python packages at one time with pip ? 是否可以通过pip一次升级所有Python软件包? Note : that there is a feature request for this on the off......

法国红酒甜
今天
21
0
活体检测+合成图鉴别面前,人脸“照片活化”黑产攻击一秒被擒

本文作者:y****n 如今,随着人脸技术的日趋成熟,新兴娱乐文化得到了极大的推动,尤其是随着 DeepFake、FaceSwap 等人脸编辑及生成技术的发展,虚拟主播、人脸合成带给人们全新的体验,但同...

百度开发者中心
昨天
12
0
如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部