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

前端开发 js常用排序算法

2018-07-24 分类：JavaScript 阅读(706) 评论(0)

web前端开发都干什么的|java前端开发工程师|云浮web前端开发工程师

1.冒泡排序

javascript 代码

var bubbleSort = function(arr) {
    var flag = true
    var len = arr.length
    for (var i = 0; i < len – 1; i++) {
        flag = true
        for (var j = 0; j < len – 1 – i; j++) {
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
                flag = false
            }
        }
        if (flag) {
            break
        }
    }
}

2.选择排序

javascript 代码

var selectSort = function(arr) {
    a
    var min
    for (var i = 0; i < arr.length – 1; i++) {
        min = i
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j
            }
        }
        if (i != min) {
            swap(arr, i, min)
        }
        console.log(i + 1, ‘: ‘ + arr)
    }
}
function swap(arr, index1, index2) {
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

3.插入排序

javascript 代码

var insertSort = function(arr) {
    var len = arr.length,
        key
    for (var i = 1; i < len; i++) {
        var j = i
        key = arr[j]
        while (–j > -1) {
            if (arr[j] > key) {
                arr[j + 1] = arr[j]
            } else {
                break
            }
        }
        arr[j + 1] = key
    }
}

4.希尔排序

javascript 代码

var shellSort = function(arr) {
    var gaps = [5, 3, 1]
    for (var g = 0; g < gaps.length; ++g) {
        for (var i = gaps[g]; i < arr.length; ++i) {
            var temp = arr[i]
            for (var j = i; j >= gaps[g] && arr[j – gaps[g]] > temp; j -= gaps[g]) {
                arr[j] = arr[j – gaps[g]]
            }
            arr[j] = temp
        }
    }
}

5.归并排序

javascript 代码

function mergeSort(arr) {
    if (arr.length < 2) {
        return
    }
    var step = 1
    var left, right
    while (step < arr.length) {
        left = 0
        right = step
        while (right + step <= arr.length) {
            mergeArrays(arr, left, left + step, right, right + step)
            left = right + step
            right = left + step
        }
        if (right < arr.length) {
            mergeArrays(arr, left, left + step, right, arr.length)
        }
        step *= 2
    }
}
function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    var rightArr = new Array(stopRight – startRight + 1)
    var leftArr = new Array(stopLeft – startLeft + 1)
    k = startRight
    for (var i = 0; i < rightArr.length – 1; ++i) {
        rightArr[i] = arr[k]
        ++k
    }
    k = startLeft
    for (var i = 0; i < leftArr.length – 1; ++i) {
        leftArr[i] = arr[k]
        ++k
    }
    rightArr[rightArr.length – 1] = Infinity // 哨兵值
    leftArr[leftArr.length – 1] = Infinity // 哨兵值
    var m = 0
    var n = 0
    for (var k = startLeft; k < stopRight; ++k) {
        if (leftArr[m] <= rightArr[n]) {
            arr[k] = leftArr[m]
            m++
        } else {
            arr[k] = rightArr[n]
            n++
        }
    }
}

6.快速排序

javascript 代码

var quickSort = function(arr, left, right) {
    var i, j, t, pivot
    if (left >= right) {
        return
    }
    pivot = arr[left]
    i = left
    j = right
    while (i != j) {
        while (arr[j] >= pivot && i < j) {
            j–
        }
        while (arr[i] <= pivot && i < j) {
            i++
        }
        if (i < j) {
            t = arr[i]
            arr[i] = arr[j]
            arr[j] = t
        }
    }
    arr[left] = arr[j]
    arr[j] = pivot
    quickSort(arr, left, i – 1)
    quickSort(arr, i + 1, right)
}

总结：算法效率比较：

排序方法 平均情况 最好情况 最坏情况
冒泡排序 O(n²) O(n) O(n²)
选择排序 O(n²) O(n²) O(n²)
插入排序 O(n²) O(n) O(n²)
希尔排序 O(nlogn)~O(n²) O(n^1.5) O(n²)
归并排序 O(nlogn) O(nlogn) O(nlogn)
快速排序 O(nlogn) O(nlogn) O(n²)

web前端开发工程师所需技能|前端开发工程师对应专业|js前端开发用什么软件

赞(0)
前端开发者 » 前端开发 js常用排序算法
64K
标签：前端开发者

前端开发者

相关推荐

评论 抢沙发

评论前必须登录！

 

最新评论