关于前端:面试必备前端常见的排序算法

37次阅读

共计 5929 个字符，预计需要花费 15 分钟才能阅读完成。

前言

算法对于前端程序员来说可能并没有后端程序员利用的多，但咱们也得把握一些根本算法的思维，这无论是对咱们找工作还是平时工作都有极大的帮忙，当初越来越多的公司都会考查前端程序员的算法能力了，所以咱们有必要去学习一下前端常见算法的根本思维。

如果这篇文章有帮忙到你，❤️关注 + 点赞❤️激励一下作者，文章公众号首发，关注 前端南玖 第一工夫获取最新的文章～

文章收录于 github, 欢送 star

冒泡排序

算法形容

冒泡排序 置信对于很多同学来说并不生疏，它应该是咱们最经典的算法了，无论学什么语言，都能见到它的身影。根本思维：反复遍历要排序的数组，每次比拟两个元素的大小，如果程序谬误就替换两个元素的程序。遍历数组反复进行比拟直到排序实现。

算法实现

根本步骤

  • 比拟相邻的两个元素。如果第一个比第二个大，则替换地位；
  • 对每一对相邻元素反复第一个步骤，从开始第一对到结尾的最初一对，这样在最初的元素应该会是最大的数；
  • 针对所有的元素反复以上的步骤，除了最初一个；
  • 反复步骤 1~3，直到排序实现。

动画演示

代码实现

/**
 * 外循环管制须要比拟的元素，比方第一次排序后，最初一个元素就不须要比拟了，内循环则负责两两元素比拟，将元素放到正确地位上
*/
function bubbleSort(arr) {
    const len = arr.length
    for(let i=0; i<len; i++) {for(let j=0;j<len-1-i; j++) {
          // 留神边界值
            if(arr[j] > arr[j+1]){[arr[j],arr[j+1]] = [arr[j+1],arr[j]] // 替换地位
            }
        }
    }
    return arr
}

console.log(bubbleSort([3,44,15,36,26,27,2,46,4,19,50,48]))
//[2,3,4,15,19,26,27,36,44,46,48,50]

工夫复杂度：O(n^2)

疾速排序

算法形容

疾速排序 ，是一种对冒泡排序改良的算法，它是解决大数据最快的排序算法之一了。 根本思维：它是一种分而治之的算法，找出一个参考值，通过递归的形式将数据顺次合成为蕴含较小元素和较大元素的不同子序列。该算法一直反复这个步骤直至所有数据都是有序的。

算法实现

根本步骤

  • 抉择一个参考元素，将列表宰割成两个子序列；
  • 对列表从新排序，将所有小于基准值的元素放在基准值后面，所有大于基准值的元素放在基准值的前面；
  • 别离对较小元素的子序列和较大元素的子序列反复步骤 1 和 2

动画演示

代码实现


function quickSort(arr) {if(arr.length<=1) return arr
    const left = [],right = [],current = arr.splice(0,1)
    for(let i=0; i<arr.length; i++) {if(arr[i]<current) {
            // 小于参考值放右边
            left.push(arr[i]) 
        }else{
            // 否则放左边
            right.push(arr[i])
        }
    }
    // 递归上述步骤
    return quickSort(left).concat(current,quickSort(right))
}

console.log(quickSort([3,44,15,36,26,27,2,46,4,19,50,48]))
//[2,  3,  4, 15, 19, 26, 27, 36, 44, 46, 48, 50]

工夫复杂度：O(nlogn)

插入排序

算法形容

插入排序 是一种简略直观的排序算法。根本思维：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应地位并插入。插入排序在实现上，通常采纳 in-place 排序（即只需用到 O(1)的额定空间的排序），因此在从后向前扫描过程中，须要重复把已排序元素逐渐向后挪位，为最新元素提供插入空间。

算法实现

根本步骤

  • 从第一个元素开始，该元素能够认为曾经被排序；
  • 取出下一个元素，在曾经排序的元素序列中从后向前扫描；
  • 如果该元素（已排序）大于新元素，将该元素移到下一地位；
  • 反复步骤 3，直到找到已排序的元素小于或者等于新元素的地位；
  • 将新元素插入到该地位后；
  • 反复步骤 2~5。

动画演示

代码实现


/** 双层循环，外循环管制未排序的元素，内循环管制已排序的元素，将未排序元素设为标杆，与已排序的元素进行比拟，小于则替换地位，大于则地位不动
*/
function insertSort(arr) {
    let tem
    for(let i=0; i<arr.length; i++) {tem = arr[i]
        for(let j=i; j>=0; j--){if(arr[j-1] > tem){arr[j] = arr[j-1]
            }else {arr[j] = tem
                break
            }
        }
    }
    return arr
}
console.log(insertSort([3,44,15,36,26,27,2,46,4,19,50,48]))
//[2,  3,  4, 15, 19, 26, 27, 36, 44, 46, 48, 50]

工夫复杂度 O(n^2)

抉择排序

算法形容

抉择排序 是一种简略直观的排序算法，根本思维：首先在待排序序列中选出最小或最大值，寄存在排序序列起始地位，而后再从残余未排序元素中持续寻找最小或最大元素，放到已排序序列开端。以此类推，直到所有元素均排序结束。

算法实现

根本步骤

  • 初始状态：无序区为 R[1..n]，有序区为空；
  • 第 i 趟排序 (i=1,2,3…n-1) 开始时，以后有序区和无序区别离为 R[1..i-1]和 R(i..n）。该趟排序从以后无序区中 - 选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R 替换，使 R[1..i]和 R[i+1..n)别离变为记录个数减少 1 个的新有序区和记录个数缩小 1 个的新无序区；
  • n- 1 趟完结，数组有序化了。

动画演示

代码实现

/**
 * 先假如第一个元素为最小的，而后通过循环找出最小元素，* 而后同第一个元素替换，接着假如第二个元素，反复上述操作即可
 */

function selectSort(arr) {
    let len = arr.length, minIndex, tem
    for(let i=0; i<len-1; i++) {
        minIndex = i // 最小值下标
        for(let j=i+1; j<len; j++) {if(arr[j] < arr[minIndex]){
                // 找出最小值
                minIndex = j // 更换最小值下标
            }
        }
        // 替换地位
        tem = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = tem
    }
    return arr
}

console.log(selectSort([3,44,15,36,26,27,2,46,4,19,50,48]))
//[2,  3,  4, 15, 19, 26, 27, 36, 44, 46, 48, 50]

工夫复杂度 O(n^2)

归并排序

算法形容

归并排序 是一种借助“归并”进行排序的办法，归并的含意是将两个或两个以上的有序序列归并成一个有序序列的过程。根本思维：将若干有序序列逐渐归并，最终归并为一个有序序列。和抉择排序一样，归并排序的性能不受输出数据的影响，但体现比抉择排序好的多，因为始终都是 O(n log n） 的工夫复杂度。代价是须要额定的内存空间。

算法实现

根本步骤

  • 把长度为 n 的输出序列分成两个长度为 n / 2 的子序列；
  • 对这两个子序列别离采纳归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列。

动画演示

代码实现

// 将数组始终等分，而后合并
function merge(left, right) {let tem = []
    while(left.length && right.length) {if(left[0] < right[0]) {tem.push(left.shift())
        }else{tem.push(right.shift())
        }
    }
    return tem.concat(left,right)
}
function mergeSort(arr) {
    const len = arr.length
    if(len<2) return arr
    let mid = Math.floor(len / 2), left = arr.slice(0,mid), right = arr.slice(mid)
    return merge(mergeSort(left),mergeSort(right))
}
console.log(mergeSort([3,44,15,36,26,27,2,46,4,19,50,48]))
// [2,  3,  4, 15, 19, 26, 27, 36, 44, 46, 48, 50]

工夫复杂度 O(nlogn)

希尔排序

算法形容

希尔排序 是插入排序的一种。也称放大增量排序，是间接插入排序算法的一种更高效的改良版本。希尔排序是非稳固排序算法。根本思维：是把记录按下标的肯定增量分组，对每组应用间接插入排序算法排序；随着增量逐步缩小，每组蕴含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

算法实现

根本步骤

  • 抉择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
  • 按增量序列个数 k，对序列进行 k 趟排序；
  • 每趟排序，依据对应的增量 ti，将待排序列宰割成若干长度为 m 的子序列，别离对各子表进行间接插入排序。仅增量因子为 1 时，整个序列作为一个表来解决，表长度即为整个序列的长度。

动画演示

代码实现


function shellSort(arr) {
    var len = arr.length;
    for(var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {for(var i = gap; i < len;i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

console.log(shellSort([50,70,60,80,61,84,83,88,87,99]))
//[50, 60, 61, 70, 80, 83, 84, 87, 88, 99]

工夫复杂度：O(nlogn)

计数排序

算法形容

计数排序 是一种稳固的排序算法。根本思维：应用一个额定的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。而后依据数组 C 来将 A 中的元素排到正确的地位。它只能对整数进行排序。

算法实现

根本步骤

  • 找出待排序的数组中最大和最小的元素；
  • 统计数组中每个值为 i 的元素呈现的次数，存入数组 C 的第 i 项；
  • 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
  • 反向填充指标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1。

动画演示

代码实现

function countingSort(arr) {let len = arr.length, b = [], c = [], min = max = arr[0]
    for(let i=0; i<len; i++) {min = min <= arr[i] ? min : arr[i]
        max = max >= arr[i] ? max : arr[i]
        c[arr[i]] = c[arr[i]] ? c[arr[i]] + 1 : 1 // 计数
    }

    for(let i=min; i< max; i++) {c[i+1] = (c[i+1] || 0) + (c[i] || 0)
    }

    for(let i=len-1; i>=0; i--) {b] - 1] = arr[i]
        c[arr[i]]--
    }
    return b
}
console.log(countingSort([2,3,8,7,1,2,2,2,7,3,9,8,2,1,4]))
//[1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 7, 7, 8, 8, 9]

工夫复杂度：O(n+k)，k 示意输出的元素是 n 个 0 到 k 之间的整数

基数排序

算法形容

基数排序 也是非比拟的排序算法，根本思维：依照低位先排序，而后收集；再依照高位排序，而后再收集；顺次类推，直到最高位。有时候有些属性是有优先级程序的，先按低优先级排序，再按高优先级排序。最初的秩序就是高优先级高的在前，高优先级雷同的低优先级高的在前。基数排序基于别离排序，别离收集，所以是稳固的。

算法实现

根本步骤

  • 获得数组中的最大数，并获得位数；
  • arr 为原始数组，从最低位开始取每个位组成 radix 数组；
  • 对 radix 进行计数排序（利用计数排序实用于小范畴数的特点）；

动画演示

代码实现

function radixSort(arr, maxDigit) {let counter = [], mod = 10, dev = 1;
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {for(let j = 0; j < arr.length; j++) {let bucket = parseInt((arr[j] % mod) / dev)
            if(counter[bucket]==null) {counter[bucket] = []}
            counter[bucket].push(arr[j])
        }
        let pos = 0
        for(let j = 0; j < counter.length; j++) {
            let value = null
            if(counter[j]!=null) {while ((value = counter[j].shift()) != null) {arr[pos++] = value
                }
          }
        }
    }
    return arr;
}
console.log(radixSort([3,44,15,36,26,27,2,46,4,19,50,48],2))
// [2,  3,  4, 15, 19, 26, 27, 36, 44, 46, 48, 50]

工夫复杂度：O(n*k)，k 示意输出的元素是 n 个 0 到 k 之间的整数

总结

排序算法 均匀工夫复杂度 最坏工夫复杂度 空间复杂度 是否稳固
冒泡排序 O(n^2) O(n^2) O(1) 是
疾速排序 O(nlogn) O(n^2) O(long) 不是
插入排序 O(n^2) O(n^2) O(1) 是
抉择排序 O(n^2) O(n^2) O(1) 不是
归并排序 O(nlogn) O(nlogn) O(n) 是
希尔排序 O(nlogn) O(n^1.5) O(1) 不是
计数排序 O(n+k) O(n+k) O(n+k) 是
基数排序 O(n*k) O(n*k) O(k) 是

举荐浏览

  • 前端常见的平安问题及防范措施
  • 为什么大厂前端监控都在用 GIF 做埋点？
  • 前端人员不要只晓得 KFC，你应该理解 BFC、IFC、GFC 和 FFC
  • Promise、Generator、Async 有什么区别？
  • 2022 年了你还不理解箭头函数与一般函数的区别吗？
  • 从如何应用到如何实现一个 Promise
  • 超具体解说页面加载过程

原文首发地址点这里，欢送大家关注公众号 「前端南玖」，如果你想进前端交换群一起学习，请点这里


我是南玖，咱们下期见！！！

正文完
前端
发表至： 前端
2022-03-11
 0
关于前端:TCP协议-保证页面文件完整送达浏览器
关于前端:Sass速成课
关于前端:PWA-技术诞生的前世今生漫谈
关于前端:Joomla-431-错误修复发布