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

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

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

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

[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;
}
站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

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

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

Js实现插入排序

插入排序是一种非常简单的算法,最适合大部分已经被排好序的数据。在开始之前,通过可视化演示算法如何运作一个好主意。你可以参考前面的动画来了解插入排序的工作原理。

如何用 JS 实现二叉堆

二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点、分支节点、叶子节点组成,如下图所示

用 Javascript 写排序算法

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

Leetcode 242 有效的字母异位词的三种解法

题目描述:给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。这个题目比较简单,属于一眼看过去就有思路的那种。我用了三种解法,你也尝试一些别的方法, 拓宽思路。

js求水仙花数_JavaScript可自定义范围打印水仙花数

水仙花数是指一个 n 位正整数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身(例如:1^3 + 5^3+ 3^3 = 153)。这篇文章主要介绍js实现生成自定义范围内的水仙花数。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

Js排列组合的实现

犹记得高中数学,组合表示C(m, n),意思为从集合m,选出n个数生成一项,总共有多少个项的可能?组合是无序的,排列是有序的。所以排列的项数量多于组合

为什么我认为数据结构与算法对前端开发很重要?

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

点击更多...

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