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

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

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

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

[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

一些常用的语音特征提取算法

语言是一种复杂的自然习得的人类运动能力。成人的特点是通过大约100块肌肉的协调运动,每秒发出14种不同的声音。说话人识别是指软件或硬件接收语音信号,识别语音信号中出现的说话人,然后识别说话人的能力

JavaScript十大排序必修算法

冒泡排序通过相邻元素的比较和交换,使得每一趟循环都能找到未有序数组的最大值或最小值,双向冒泡普通的冒泡排序在一趟循环中只能找出一个最大值或最小值,双向冒泡则是多一轮循环既找出最大值也找出最小

js实现1万的阶乘

但是这样就会存在问题,Js中最大的安全整数为2^53- 1,10000!结果溢出该范围,代码运行结果为Infinity,无法计算出正确的结果。那么如何才能计算大数据的阶乘呢?

js中常用的基础算法

今天给大家分享一下js中常用的基础算法,废话不多说,直接上代码;两个数字调换顺序;对象排序,安装对象中的id排序对象的位置;冒泡排序 ;随机出现不同的数字;字符串大小写互换

原生js数值开根算法

理论上来讲,开根后的值为x,那么x^2=n,即可以将其转换为数学问题,令y=x^2-n,那么只需要求方程与x轴正方向的焦点就可以得出想要的结果,我们作x=a与方程交于(a^2-n),求得他的切线与x轴的交点

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

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

Js算法模式:动态规划和贪心算法

动态规划(Dynamic Programming,DP)是一种将复杂问题分解成更小的子问题来解决的优化算法。下面有一些用动态规划来解决实际问题的算法:给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量。

Js集合的实现与应用

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

一致性hash算法和实现

一致性hash算法,是麻省理工学院1997年提出的一种算法,目前主要应用于分布式缓存当中。一致性hash算法可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。

JS 洗牌算法

最近的一个塔罗牌项目中,有一个洗牌的需求,其实也就是随机打乱数组,遂网上搜了下,再此做个整理…塔罗牌,举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9:

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

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

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