找回密码
当前位置：前端开发者 > JavaScript > 正文

JS排序算法（冒泡，选择，插入，归并，快速）

2018-10-14 分类：JavaScript 阅读(799) 评论(0)
前端开发设计模板
前端开发psd模板使用
前端项目开发文档模板

目前共整理出了五种：冒泡排序,选择排序,插入排序,归并排序，快速排序(递归)
经典的排序算法有十种，剩下五种再慢慢研究

1、冒泡算法：比较任意两个相邻的项，如果第一个比第二个大，则交换顺序
javascript 代码

/*冒泡排序*/
for (var i = 0; i < a.length; i++) {
    for (var j = i + 1; j < a.length; j++) {
        if (a[j] < a[i]) {
            // var t = a[i];
            // a[i] = a[j];
            // a[j] = t;
            swap(i, j)
        }
    }
}

2、选择排序：找到数组中最小的项并将其放到第一位，找到第二小的值，并将其放到第二位，依次……
javascript 代码

/*选择排序*/
var indexMin
for (var i = 0; i < a.length – 1; i++) {
    // 假设下标indexMin的值最小
    indexMin = i
    for (var j = i + 1; j < a.length; j++) {
        if (a[indexMin] > a[j]) {
            // 交换最小值下标
            indexMin = j
        }
    }
    // 如果找到的最小值跟原来设定的最小值不一样，交换其值
    if (i !== indexMin) {
        swap(i, indexMin)
    }
}

3、插入排序：每次只排序一个数组项，确定它应该插入到哪个位置
javascript 代码

/*插入排序*/
var j, temp
// 默认第一项已经排序，所以从第二项开始
for (var i = 1; i < a.length; i++) {
    // 辅助变量和值，存储当前下标和值
    j = i
    temp = a[i]
    // 一直跟前一项比较，直到找到正确的位置插入
    while (j > 0 && a[j – 1] > temp) {
        // 移到当前位置
        a[j] = a[j – 1]
        j–
    }
    a[j] = temp
}

4、归并排序（分治）：
①将数组拆分成较小的数组，直到每个数组的长度为1；
②合并和排序小数组，直到回到原始数组的长度；
javascript 代码

function merge(left, right) {
    var result = []
    while (left.length > 0 && right.length > 0) {
        // 比较左边的数组的值是否被右边的小
        if (left[0] < right[0]) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    return result.concat(left).concat(right)
}
function mergeSort(arr) {
    // 递归的停止条件
    if (arr.length == 1) {
        return arr
    }
    // 中间值取整，分成两个小组
    var middle = Math.floor(arr.length / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle)
    // 递归，对左右两部分数据进行合并排序
    return merge(mergeSort(left), mergeSort(right))
}

5、快速排序（分治）
①从数组中选择中间项目作为主元
②建立左右两个数组，分别存储左边和右边的数组
③利用递归进行下次比较
javascript 代码

/*快速排序*/
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    // 取中间数作为基准索引，浮点数向下取整
    var index = Math.floor(arr.length / 2)
    // 取得该值
    var pivot = arr.splice(index, 1)
    // 分别建立左右空数组，作为push所用
    var left = []
    var right = []
    for (var i = 0; i < arr.length; i++) {
        // 基准左边的传到左数组,右边的传到右数组
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    // 不断递归重复比较
    return quickSort(left).concat(pivot, quickSort(right))
}
前端开发接口文档模板
前端开发个人总结ppt模板
web前端开发论文模板
赞(0)
前端开发者 » JS排序算法（冒泡，选择，插入，归并，快速）
64K
标签：前端开发者

前端开发者

相关推荐

评论 抢沙发

评论前必须登录！

 

最新评论