JS排序算法(冒泡,选择,插入,归并,快速)

前端开发设计模板
前端开发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前端开发论文模板
» 本文来自:前端开发者 » 《JS排序算法(冒泡,选择,插入,归并,快速)》
» 本文链接地址:https://www.rokub.com/6135.html
» 您也可以订阅本站:https://www.rokub.com
赞(0)
64K

评论 抢沙发

评论前必须登录!