前端的排序算法总结

xioqua 发布于2019-08-23 18:15 / 3065人阅读

摘要：参考冒泡排序典型的排序方法，命名来自鱼呼吸时吹出的气泡，上层的气泡总是最大的。时间复杂度，属于不稳定的算法特殊情况下会是空间复杂度辅助空间是，所以空间复杂度为

参考lianjie

冒泡排序

典型的排序方法，命名来自鱼呼吸时吹出的气泡，上层的气泡总是最大的。

思路：两层循环，内层循环对比相邻两个数据（j,j+1），假设j > j + 1则交换元素位置。
外层循环为长度限制，在内层第一次循环完成后减少长度1（因为最后一个泡已经固定，为这个数组的最大值）

function bubbleSort(arr){
  for(let i = 0; i < arr.length - 1; i++){
    let flag = false;
    for(let j = 0; j < arr.length - i - 1; j++){
      if(arr[j] > arr[j + 1]){
          let temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;;
          flag = true;
      }
    }
    if(!flag){
      break;
    }
  }
  return arr;
}

加一个标志位flag，如果没有进行交换，将标志位置为false，表示排序完成。

时间复杂度O(n^2)，最优情况下是O(n)

空间复杂度O(1)

选择排序

顾名思义，每次都选择最小的，然后交换位置

思路：两层循环，内层循环为选取第一个位置的值，然后将它与剩下的值作对比，得到比它小的则交换位置。外层循环为控制第一位值的固定（一次循环后，第一位则为该数组最小的值，下一次循环不必带上）。

function selectionSort(arr){
  for(let i = 0; i < arr.length - 1; i++){
    let index = i;
    for(let j = i+1; j < arr.length; j++){
    //判断是否有小于当前值，有则交换位置
      if(arr[index] > arr[j]){
        index = j;
      }
    }
      let temp = arr[i];
      arr[i] = arr[index ];
      arr[index] = temp;
  }
  return arr;
}

时间复杂度：O(n^2)，属于不稳定的算法（每次交换之后，它都改变了后续数组的顺序）

空间复杂度：O(1)

快速排序

思路：二分法，先找一个基数，分隔出以基数为界的左右两个数组，然后递归重复这个步骤，直到分组剩余一个数，则我们认为已经排列完成。

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

时间复杂度：O(n*logn)，属于不稳定的算法,特殊情况下会是O(n^2)

空间复杂度：辅助空间是logn，所以空间复杂度为O(logn)

GPU云服务器云服务器排序算法总结字母的排序算法最好的排序算法选择排序的算法过程

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104911.html

前端排序算法总结

摘要：前言排序算法可能是你学编程第一个学习的算法，还记得冒泡吗当然，排序和查找两类算法是面试的热门选项。本篇将会总结一下，在前端的一些排序算法。函数的性能相信对于排序算法性能来说，时间复杂度是至关重要的一个参考因素。前言排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较你和一个连快排都不会写的人的时...

happen 2019-08-21 16:40 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

aaron 2019-08-01 17:38 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

ARGUS 2019-08-21 16:43 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

April 2019-08-30 15:53 评论0 收藏0
前端中经常出现的算法总结

摘要：在一段时间的学习之后，我总结罗列了前端中常见见的几个算法一排序算法排序算法是比较开发的算法之一，方法种类较多，在此列举两种简单的排序算法冒泡排序和快速排序。虽说我们很多时候前端很少有机会接触到算法，但对算法的理解和掌握是一个优秀工程师的评价标准之一，而且当我们面对较为复杂的问题，这些基础知识的积累可以帮助我们更好的优化解决思路。在一段时间的学习之后，我总结罗列了前端中常见见的几个算法...

noONE 2019-08-20 12:12 评论0 收藏0
Deep in JS - 收藏集 - 掘金

摘要：今天同学去面试，做了两道面试题全部做错了，发过来给道典型的面试题前端掘金在界中，开发人员的需求量一直居高不下。排序算法 -- JavaScript 标准参考教程（alpha） - 前端 - 掘金来自《JavaScript 标准参考教程（alpha）》，by 阮一峰目录冒泡排序简介算法实现选择排序简介算法实现 ... 图例详解那道 setTimeout 与循环闭包的经典面...

enali 2019-08-20 16:36 评论0 收藏0