JavaScript实现的几种排序:冒泡排序、选择排序、插入排序、归并排序

更新日期: 2018-06-28阅读: 2.2k标签: 冒泡

1.冒泡排序

原理:冒泡排序的过程就是将数组中相邻的两个元素进行比较,如果前面的元素比后面的元素要大交换位置,否则位置不变;举个栗子:有数组 arr = [3,5,4,2,1];
第一轮循环:3和5比较,3小于5两者位置不变,接下来5和4比较,5大于4,两者交换位置,接着5和2比较,5>2两者交换位置,继续5和1 比较 5>1两者交换位置,一轮后得到的数组是[3,4,2,1,5];把大的元素放到数组的最末尾,这种就像水泡样一层一层的像后移动,就是冒泡排序了;
代码实现:

    // 记录循环次数
    let count = 0 
   // 位置交换函数
    const change = function (arr, n1, n2) {
        let temp = arr[n1]
        arr[n1] = arr[n2]
        arr[n2] = temp
    }
    // 冒泡排序
    const bubbleSort = function (soucre) {
        let len = soucre.length
        for (let i = 0;i < len - 1; i++) {
            for (let j = 0; j < len - 1 - i;j++) {
                count ++
                if (soucre[j] > soucre[j+1]) {
                   change(soucre, j, j+1)
                }
            }
        }
        return soucre
    }
    //验证
    console.log(bubbleSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9]
    console.log(count) // 21


2.选择排序

选择排序和冒泡排序类似也是依次对相邻的数进行两两比较。不同之处在于,他不是每次两两相邻比较后交换位置,他是先找出最大(最小)将它放到正确的位置,然后再寻找次最大(最小)放在正确的位置;
举个栗子:有数组 arr = [3,5,4,2,1];
先假设第一个元素是最小值,并定义一个minidx=0变量记录最小(最大)值的位置,for循环和其他元素进行比较,3和5进行比较,5>3此时不做处理,4也是一样处理,当3和2比较时,3>2,此时将minidx赋值为2的位置,接下来用arr[minidx]和剩余的元素比较遇到比他小的就用minidx记录小值的位置;最后将最小的位置值和初始给的值位置进行互换(当然是初始的值和一轮循环下来的minidx位置不一样才互换);所以一轮循环下来结果是arr = [1,5,4,2,3]
代码实现:

// 记录循环次数
let count = 0
// 选择排序
 const selectSort = function (soucre) {
        let len = soucre.length
        let minidx;
        for (let i = 0; i < len; i ++) {
            minidx = i
            for (let j = i + 1; j < len; j++) {
                count ++
                if (soucre[minidx] > soucre[j]) {
                    minidx = j
                }
            }
            if (minidx !== i) {
                change(soucre,i,minidx)
            }
        }
        return soucre
    }
     console.log(selectSort([3,6,2,4,9,1,8,23,45,16,14])) // [1, 2, 3, 4, 6, 8, 9, 14, 16, 23, 45]
    console.log(count) // 55


3.插入排序

原理:将数组分为已排序和未排序,将第一个元素看作是已排序的元素,而其他是未排序的,从未排序的里面取出一元素和已排序元素进行比较,并插入到正确位置,这样已排序部分增加一个元素,而未排序的部分减少一个元素。直到排序完成
举个栗子:有数组 arr = [1,5,4,2,3],第一次假设元素1 是已排序部分,5,4,2,3为未排序,取出元素5加入已排序部分,5>1,已排序部分为1,5;而未排序部分为4,2,3;如此往复完成排序;
代码实现:

const insertSort = function (source) {
        let len = source.length
        let value
        let j
        let i
        for (i = 0; i < len; i++) {
            value = source[i]
            // 已排序部分进行元素的右移一位,并把目标值value插入到对应的位置
            for (j = i -1 ;j > -1 && source[j] > value; j--) {
                source[j+1] = source[j]
            }
            source[j+1] = value
        }
        return source
    }
        console.log(insertSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9]


4.归并排序

原理: 将两个已经排序的数组合并,要比从头开始排序所有元素来得快。因此,可以将数组拆开,分成n个只有一个元素的数组,然后不断地两两合并,直到全部排序完成
代码实现:

const mergeSort = function mergeSort(source) {
        let len = source.length
        if (len < 2) {
            return source
        }
        let mid = Math.floor(len/2)
        let left = source.slice(0,mid)
        let right = source.slice(mid)
        return merge(mergeSort(left), mergeSort(right))
    }
    function merge(left, right) {
        let result = []
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                result.push(left.shift())
            } else {
                result.push(right.shift())
            }
        }
        while (left.length){
            result.push(left.shift())
        }
        while (right.length){
            result.push(right.shift())
        }
        return result
    }
    console.log(mergeSort([4,8,1,3,5,9,6])) // [1,3,4,5,6,8,9]


来源:https://segmentfault.com/a/1190000015410457

链接: https://www.fly63.com/article/detial/900

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

javascript冒泡排序的实现,冒泡排序是一个非常常见的排序算法,对于一个数组,每趟排序时依次比较两个相邻的数,如果他们的顺序错误就交换两数位置。

vue.js阻止事件冒泡和默认事件

首先我们来看原生JS取消事件冒泡方法:原生JS阻止默认事件方法:而vue.js给我们提供了更简便的方法,我们可以通过function($event)来获取事件对象,$event.target则是选择发生事件的目标元素

React 事件冒泡

在React中,我们可以在创建element的时候,传入事件和处理函数,这些事件会被做为合成事件来处理,当然,有些时候,我们也需要定义原生事件,比如给document绑定事件。有些情况下,就需要通过阻止事件冒泡来实现预期的交互效果。下面是几个简单的demo

js中什么是事件冒泡?

在一个对象上触发某类事件,这个事件会向这个对象的的父级传播,从里到外,直至它被处理或者到达了对象层次的最顶层,即document对象。这个过程就是JavaScript的事件冒泡。

Js阻止冒泡和取消默认事件(默认行为)

js冒泡和捕获是事件的两种行为,使用event.stopPropagation()起到阻止捕获和冒泡阶段中当前事件的进一步传播。使用event.preventDefault()可以取消默认事件。

vue里面如何阻止事件冒泡 - 阻止click事件冒泡方法总汇

方法一:使用vue阻止子级元素的click事件冒泡。简单得:可以直接用stop;这样点击div里面的按钮1,就不会触发div绑定时间test1()方法。可以自己写个阻止冒泡事件 然后在发生冒泡的元素中调用这个事件

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