前端的排序算法总结

栏目: 编程工具 · 发布时间: 5年前

内容简介:典型的排序方法,命名来自鱼呼吸时吹出的气泡,上层的气泡总是最大的。思路:两层循环,内层循环对比相邻两个数据(j,j+1),假设j > j + 1则交换元素位置。

参考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)

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Adobe Dreamweaver CS5中文版经典教程

Adobe Dreamweaver CS5中文版经典教程

Adobe公司 / 陈宗斌 / 人民邮电 / 2011-1 / 45.00元

《Adobe Dreamweaver CS5中文版经典教程》由Adobe公司的专家编写,是AdobeDreamweavelCS5软件的官方指定培训教材。全书共分为17课,每一课先介绍重要的知识点,然后借助具体的示例进行讲解,步骤详细、重点明确,手把手教你如何进行实际操作。全书是一个有机的整体,它涵盖了Dreamweavercs5的基础知识、HTML基础、CSS基础、创建页面布局、使用层叠样式表、使......一起来看看 《Adobe Dreamweaver CS5中文版经典教程》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具