数据结构之排序算法--------JavaScript篇

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构之排序算法--------JavaScript篇，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2399字，纯文字阅读大概需要4分钟。

内容图文

文章目录

• 排序算法
• 简单排序算法
• 冒泡排序
• 选择排序
• 插入排序
• 高级排序
• 希尔排序
• 快速排序

排序算法

简单排序算法

冒泡排序

像可乐里面的气泡一样,每一个数都自行的向上比较,如果符合就停下,不符合就继续冒泡

对未排序的元素从头到尾依次与相邻元素比较,如果不符合条件则调换位置,符合则进行下一个元素比较

时间复杂度($n^2$n2),空间复杂度($1$1),稳定

 function bubbleSort (arr) {
     for(let i = 0;i<arr.length;i++) {
       for(let j = 0;j<arr.length;j++) {
           if(arr[j-1] > arr[j]) {
               let curren = arr[j-1]
               arr[j-1] = arr[j]
               arr[j] = curren 
           } else {
   
           }
       }
   }
 }

效率：10万数组

选择排序

每次循环找到最小(大)值,放到最前面的位置,依次类推

对于冒泡排序比较,减少交换次数,每次找到最值,避免多余的交换次数

时间复杂度($n^2$n2),空间复杂度($1$1),不稳定

function selectSort(arr) {
    let len = arr.length
    for(let i = 0; i< len; i++) {
        let curren = i
        for(let j = 0; j< len; j++ ) {
            if(arr[j] < arr[i]) {
                curren = j
            }
        }
        if(curren!= i) {
            let item = arr[i]
            arr[i] = arr[curren]
            arr[curren] = item
        }
            
    }
   	return arr
}

效率测试：10万数组

插入排序

简单排序中效率最高

从头到尾开始遍历,每一个元素都需要与左边的所有元素注意比较,如果符合条件就插入,不符合继续向前遍历

时间复杂度($n^2$n2),空间复杂度($1$1),稳定

function insetSort(arr) {
       let index = 0
    for(var i = 1; i < arr.length; i++) {
     	index = i-1
        let curren = arr[index + 1]
        while(index >= 0&& arr[index] > curren ) {
            // 每次判断左边所有元素是否符合条件,不符合就调换位置
            arr[index +1] = arr[index]
            index--
        }
        arr[index + 1] = curren
    }
    return arr
}

效率测试：10万数组

高级排序

希尔排序

插入排序高配版,只不过插入排序是对整个数组直接排序,而希尔是通过间隔而不是相邻元素插入排序

时间复杂度($n^{1.25}$n1.25),空间复杂度($1$1),不稳定

选择适合的增量:

1. HIBBARD增量:奇数增量
2. sedgewick增量:$94^i -9*2^i +1或者4^i-32^i +1$94i?9?2i+1或者4i?32i+1

function shellSort(arr) {
    let gap = Math.floor(arr.length /2)
    let temp ;
    while(gap >= 1) {
        // 这里对每一个分组进行插入排序
        for(var i = gap;i<arr.length;i++) {
			let j = i
       		temp = arr[i]
            while(arr[j - gap] > temp && j > gap -1) {
                arr[j] = arr[j-gap]
                j -= gap
            }
        }
        arr[j] = temp
        gap = Math.floor(gap/2)
    }
  
}

效率测试：100万的长度数组

快速排序

冒泡的高配版

选择一个标记,将所有大于这个标记放在左边.所有大于这个标记放在右边

时间复杂度($nlgn$nlgn),空间复杂度($nlgn$nlgn),不稳定

function quickSort(arr){
    if(arr.length <=1) return arr
    let right =[]
    let left = []
    let point = arr.shift()
    for(var i = 0; i < arr.length;i++) {
        if(arr[i] > point ) {
            right.push(arr[i])
        } else {
            left.push(arr[i])
        }
    }

    return quickSort(left).concat([point],quickSort(right))
}

效率测试:1千万的长度

内容总结

以上是互联网集市为您收集整理的数据结构之排序算法--------JavaScript篇全部内容，希望文章能够帮你解决数据结构之排序算法--------JavaScript篇所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端