原生js实现冒泡排序算法,javascript冒泡排序

时间: 2017-11-17阅读: 853标签: 算法

冒泡排序是一个非常常见的排序算法,对于一个数组,每趟排序时依次比较两个相邻的数,如果他们的顺序错误就交换两数位置。所以,没趟排序都会排好一个数字,下一轮排序就可以少比较一个数字,直到只剩下一个数字,就全部排序好了。

举个例子,假设最终需要的结果是从小到大排列,对于数组:

[3, 5, 2, 6, 1, 7, 4]

第一趟排序的过程:

[3, 5, 2, 6, 1, 7, 4]

// 比较过程:
// 1. 比较 3 和 5,发现顺序正确,则不变
[3, 5, 2, 6, 1, 7, 4]

// 2. 比较 5 和 2,发现顺序错误,交换位置
[3, 2, 5, 6, 1, 7, 4]

// 3. 比较 5 和 6,发现顺序正确,不变
[3, 2, 5, 6, 1, 7, 4]

// 4. 比较 6 和 1,发现顺序错误,交换位置
[3, 2, 5, 1, 6, 7, 4]

// 5. 比较 6 和 7,发现顺序正确,不变
[3, 2, 5, 1, 6, 7, 4]

// 5. 比较 7 和 4,发现顺序错误,交换位置
[3, 2, 5, 1, 6, 4, 7]

排序过程中,所有相邻数字对都比较了一遍,比较的过程中,实质上是比较的相邻位置,而不管位置上的数字是否在上一次比较中交换了位置,只管一个一个位置的比较下去,数字顺序错误就把数字位置交换。经过这趟排序,发现最大的数字 7 已经排到了最后一个位置,所以下一趟排序就不需要再比较最后一个位置的数字了。

第二趟排序过程:

// 经过第一趟排序后的数组
[3, 2, 5, 1, 6, 4, 7]

// 比较过程:
// 1. 比较 3 和 2,发现顺序错误,交换位置
[2, 3, 5, 1, 6, 4, 7]

// 2. 比较 3 和 5,发现顺序正确,不变
[2, 3, 5, 1, 6, 4, 7]

// 3. 比较 5 和 1,发现顺序错误,交换位置
[2, 3, 1, 5, 6, 4, 7]

// 4. 比较 5 和 6,发现顺序正确,不变
[2, 3, 1, 5, 6, 4, 7]

// 5. 比较 6 和 4,发现顺序错误,交换位置
[2, 3, 1, 5, 4, 6, 7]

// 最后一个数字不用比较

经过第二趟排序后,数字 6 也排到了正确的位置。第三趟排序时,最后两位数字都不用比较了。

每一趟排序,都会把剩余数字中最大的排到最后面。后面的排序过程就不再分析了。清楚了排序过程,写代码来排序就很简单了,代码如下:

function bubbleSort(arr) {
    var arr = arr.slice(0); // 保证排序后原数组不变
    var len = arr.length;
    var tmp;

    // 只需要进行 len - 1 趟排序
    // 因为只剩下一个数字时不用再比较了
    for (var i = 0; i < len - 1; ++i) {

        // 每一趟都会排序好一个数字
        // 所以每趟只需排 len - i 个数字
        for (var j = 1; j < len - i; ++j) {

            // 如果右边的数比左边的小
            // 就交换位置
            if (arr[j] < arr[j-1]) {
                tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            }
        }

        // 这里可以打印出每趟排序的结果
        // 以便观察排序过程
        // console.log(arr);
    }

    return arr;
}

链接: http://www.fly63.com/article/detial/121

程序员必知必会的10 大基础算法!

快速排序算法:快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(nlogn)算法更快

Js集合的实现与应用

与数学中的集合概念类似,集合由一组无序的元素组成,且集合中的每个元素都是唯一存在的。可以回顾一下中学数学中集合的概念,我们这里所要定义的集合也具有空集(即集合的内容为空)、交集、并集、差集、子集的特性

Js队列和双端队列

最新添加的元素必须排在队列的末尾。在生活中也有队列的应用,比如我们在售票处排队等票,队头的人先拿到票,就走了,而新来的人,就必须排在队伟文明排队。

用 Javascript 写排序算法

至于为什么选择用 Javascript,则是因为我觉得 Javascript 是最方便运行和调试的,只需要复制代码粘贴到浏览器的控制台就可以了,我为所有的算法附上了测试用例,通过引入 Mocha 就可以在浏览器中显示用例的通过情况

简单理解梯度下降算法及js实现

看了很多文章,梯度下降算法描述都比较艰涩难懂,比如说: 目标函数f(θ)关于参数θ的梯度将是损失函数(loss function)上升最快的方向。然后会推导出下面这个公式。

从js讲解时间复杂度和空间复杂度

今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客;复杂度的表示方式之前有看过的,你可能会看到这么一串东西

Js算法:计算两数之和

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和

Js队列的实现与应用

队列与栈不同,它遵从先进先出(FIFO——First In First Out)原则,新添加的元素排在队列的尾部,元素只能从队列头部移除。

前端Js排序算法:冒泡排序、 选择排序、快速排序

典型的排序方法,命名来自鱼呼吸时吹出的气泡,上层的气泡总是最大的。选择排序:顾名思义,每次都选择最小的,然后交换位置,快速排序思路:二分法,先找一个基数

不懂算法,还想进大厂?做梦吧

学算法,刷题蛮干是不行的,需要遵循科学的方法。以下的经验技巧,对于算法新手,或大学没有搞过ACM,想利用业余时间提升算法能力的同学比较有帮助,对于算法高手和ACM大牛

fly63.com版权所有,内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权,请与小编联系!情况属实本人将予以删除!

广告赞助文章投稿关于web前端网站点搜索站长推荐网站地图站长QQ:522607023

小程序专栏: 土味情话心理测试脑筋急转弯幽默笑话段子句子语录成语大全