0


前端必须掌握的五种排序算法,你会几种?

文章目录

前言

在前端开发中,对数据进行排序是一项基本且常见的任务。掌握排序算法不仅可以帮助我们更有效地处理数据,还能提升代码的执行效率。本文将介绍五种基础且常用的排序算法:

冒泡排序、选择排序、插入排序、快速排序和归并排序

。通过理解这些算法的原理和逻辑,我们可以更好地选择合适的排序方法来优化应用性能。


在这里插入图片描述

正文开始

如果觉得文章对您有帮助,请帮我三连+订阅,谢谢

💖💖💖


1. 冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

原理和逻辑:

  • 比较相邻的两个元素,如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码实现

// 1. 冒泡排序let arr =[2,5,8,1,3,9,6,7];constbubbleSort=(arr)=>{let len = arr.length;for(let i =0; i < len; i++){for(let j =0; j < len - i -1; j++){if(arr[j]> arr[j +1]){let tmp = arr[j];
        arr[j]= arr[j +1];
        arr[j +1]= tmp;}}}return arr;};
console.log("bubbleSort:",bubbleSort(arr));//bubbleSort: [1, 2, 3, 5, 6, 7, 8, 9]

2. 选择排序(Selection Sort)

选择排序是一种简单直观的排序算法。它的工作原理是首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

原理和逻辑:

  • 从未排序序列中找到最小(大)元素,存放到排序序列的起始位置;
  • 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;
  • 重复第二步,直到所有元素均排序完毕。

代码实现

// 2. 选择排序let arr =[2,5,8,1,3,9,6,7];constselectSort=(arr)=>{let len = arr.length;for(let i =0; i < len -1; i++){let maxIndex = i;for(let j = i +1; j < len; j++){if(arr[j]> arr[maxIndex]){
        maxIndex = j;}}let tmp = arr[i];
    arr[i]= arr[maxIndex];
    arr[maxIndex]= tmp;}return arr;};
console.log("selectSort:",selectSort(arr));//selectSort: [1, 2, 3, 5, 6, 7, 8, 9]

3. 插入排序(Insertion Sort)

插入排序的工作方式是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

原理和逻辑:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤1~5。

代码实现

// 3. 插入排序let arr =[2,5,8,1,3,9,6,7];constinsertSort=(arr)=>{let len = arr.length;for(let i =1; i < len; i++){let current = arr[i];let prev = i -1;while(prev >=0&& current < arr[prev]){
      arr[prev +1]= arr[prev];
      prev--;}
    arr[prev +1]= current;}return arr;};

console.log("insertSort:",insertSort(arr));//insertSort: [1, 2, 3, 5, 6, 7, 8, 9]

4. 快速排序(Quick Sort)

快速排序是一种分而治之的算法,它通过一个基准值将数据分为两部分,其中一部分的所有数据都比另外一部分的所有数据要小,然后再递归地对这两部分数据分别进行快速排序。

原理和逻辑:

  • 选择一个基准值,通常选择第一个元素或者中间元素;
  • 重新排序数组,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数组的中间位置;
  • 递归地(recursive)把小于基准值元素的子数组和大于基准值元素的子数组排序。

代码实现

// 4. 快速排序let arr =[2,5,8,1,3,9,6,7];functionquickSort(arr){if(arr.length <2)return arr
  let first = arr[0]let left =[], right=[]for(let i =1; i <arr.length; i++){if(first > arr[i]){
      right.push(arr[i])}else{
      left.push(arr[i])}}return[...quickSort(left), first ,...quickSort(right)]} 

console.log('quickSort:',quickSort(arr));//quickSort: [1, 2, 3, 5, 6, 7, 8, 9]

5. 归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

原理和逻辑:

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

代码实现

// 5. 归并排序let arr =[2,5,8,1,3,9,6,7];functionmergeSort(arr){if(arr.length <2)return arr;let middle = Math.floor(arr.length /2);let left = arr.slice(0, middle);let right = arr.slice(middle, arr.length);returnmerge(mergeSort(left),mergeSort(right));}functionmerge(left, right){let result =[];while(left.length && right.length){if(left[0]< right[0]){
      result.push(left.shift());}else{
      result.push(left.shift());}}// 这也可以采用 whileif(left.length){
    result.push(...left);}if(right.length){
    result.push(...right);}return result;}

console.log("mergeSort:",mergeSort(arr));//mergeSort: [1, 2, 3, 5, 6, 7, 8, 9]

本文转载自: https://blog.csdn.net/cdns_1/article/details/142059796
版权归原作者 子羽bro 所有, 如有侵权,请联系我们删除。

“前端必须掌握的五种排序算法,你会几种?”的评论:

还没有评论