CHANSHIYU
GITHUBZERO
  • README
  • 時雨
    • 2017
      • 01 网站动态标题的两种方式
      • 02 RN App 外部唤醒踩坑记
    • 2018
      • 01 不一样の烟火
      • 02 Python 之禅
      • 03 Python 文件操作
    • 2019
      • 01 Aurora 食用指南
      • 02 Godaddy 域名找回记事
      • 03 一个接口的诞生
      • 04 SpringMVC 前后端传参协调
      • 05 主题集成友链访问统计
      • 06 Github Style 博客主题
      • 07 字符编码の小常识
      • 08 WSL 安装 Docker 实录
      • 09 Eriri comic reader
      • 10 Aurora 2.0
      • 11 jsDelivr 全站托管
      • 12 两年工作台变迁史
      • 13 春物
      • 14 一种优雅の笔记方式
    • 2020
      • 01 Telegram 电报机器人
      • 02 她的眼里有星辰
      • 03 文心雕龙
      • 04 软萌木子の有趣笔谈
      • 05 Telegram RSS 订阅频道
      • 06 水月雨银色飞船
      • 07 五年前旧照
    • 2021
      • 01 春宵苦短 2020
      • 02 风花
    • 2022
      • 01 小城新貌
      • 02 原神满级纪念
    • 2023
      • 01 2022 逆旅
      • 02 半透明背景图实现
      • 03 新年攒台海景房
  • 前端
    • JavaScript
      • 01 JavaScript 秘密花园
      • 02 JavaScript 正则技巧
      • 03 从浏览器解析 JS 运行机制
      • 04 Canvas 基础用法
      • 05 Blob Url And Data Url
      • 06 函数节流与函数防抖
      • 07 排序算法初探
      • 08 洗牌算法实现数组乱序
      • 09 正则匹配 match 和 exec
      • 10 正则匹配汉字
      • 11 JSX.Element vs ReactElement
      • 12 可选链与空值合并
      • 13 TypeScript 编码规范
      • 14 Typescript 中 interface 和 type 区别
      • 15 TypeScript 高级类型
      • 16 TypeScript 关键字
      • 17 TypeScript 映射类型
    • CSS
      • 01 Flex 弹性布局
      • 02 Position 定位
      • 03 CSS 逻辑属性
    • Node
      • 01 Node Tips
      • 02 七天学会 NodeJS
    • Note
      • 01 Note
      • 02 Code
      • 03 Snippets
      • 04 Git
    • React
      • 01 React Props Children 传值
      • 02 Use a Render Prop!
      • 03 React Hook
      • 04 React Hook 定时器
      • 05 Fetch data with React Hooks
      • 06 React 和 Vue 中 key 的作用
      • 07 useCallback 的正确使用方式
      • 08 useLayoutEffect 和 useEffect 的区别
      • 09 forwardRef 逃生舱
      • 10 React 条件渲染
    • Vue
      • 01 Vue Tips
      • 02 Vue 构建项目写入配置文件
      • 03 Vue 项目引入 SVG 图标
      • 04 Vue 一键导出 PDF
      • 05 动态可响应对象
      • 06 Vue 引入 SCSS
      • 07 Vue 路由权限控制
    • 实战系列
      • 01 WebSocket 心跳重连机制
      • 02 图片加解密二三事
      • 03 优雅实现 BackTop
      • 04 动态加载 JS 文件
      • 05 常用 DOM 方法比较
      • 06 AbortController 中断 fetch
      • 07 计算字符所占字节数
      • 08 Axios 自定义返回值类型
  • 后端
    • Java
      • 01 面向对象基本特征与原则
      • 02 Java 数据类型
      • 03 Java String
      • 04 Java 只有值传递
      • 05 Java final 与 static
      • 06 Java Object 通用方法
      • 07 Java 继承
      • 08 Java 反射
      • 09 Java 异常
      • 10 Java 容器
      • 11 Java 虚拟机
      • 12 Java IO
      • 13 Java HashMap
      • 14 Java List
      • 15 Java Stream
      • 16 Java 枚举
      • 17 Java 日期与时间
      • 18 Java fail fast
      • 19 Java BiFunction 和 BinaryOperator
    • 并发编程
      • 01 Java 并发
      • 02 synchronized
      • 03 volatile
      • 04 ReentrantLock
      • 05 ReadWriteLock
      • 06 StampedLock
      • 07 CompletableFuture
      • 08 ForkJoin
      • 09 ThreadLocal
      • 10 CountDownLatch
      • 11 ThreadPoolExecutor
      • 12 ExecutorService
      • 13 Atom 原子类
      • 14 BlockingQueue
    • 高效编程
      • 01 30 seconds of java8
      • 02 函数式替代 for 循环
      • 03 Java 字符串拼接
      • 04 单例模式的几种实现
      • 05 HashMap 排序
    • 理论概念
      • 01 Java Servlet
      • 02 Java 服务端分层模型
      • 03 经典排序算法
      • 04 LRU 缓存淘汰算法
      • 05 BloomFilter 判断元素存在
      • 06 Java HashMap 面试大全
      • 07 HTTP 状态码详解
      • 08 Cookie 和 Session
      • 09 基于消息队列的分布式事务解决方案
      • 10 微服务之所见
    • 实战系列
      • 01 AES CBC 加解密
      • 02 Magic 魔数获取文件类型
      • 03 获取请求 IP 地址
      • 04 Kaptcha 与数学公式验证码
      • 05 Netty 获取客户端 IP.md
      • 06 高性能无锁队列 Disruptor.md
      • 07 前后端接入阿里云盾
    • Linux
      • 01 Linux 文件权限系统
      • 02 Linux 常用软件安装
      • 03 CentOS 防火墙
    • MySQL
      • 01 MySQL
      • 02 SQL 语句 where 1=1
      • 03 truncate 和 delete
      • 04 事务
      • 05 关系模型
      • 06 Mybatis
      • 07 MySQL 查看数据库表详情
    • Nginx
      • 01 Nginx 指北
      • 02 nginx gzip 压缩
    • Note
      • 01 Vagrant
      • 02 Docker
      • 03 Lombok
      • 04 Swagger
      • 05 Redis
    • Spring
      • 01 Spring Boot
      • 02 Spring Validation
      • 03 Spring Data
      • 04 Spring 容器
      • 05 Spring AOP
      • 06 Spring Transactional 注解
      • 07 Spring Cloud Netflix
      • 08 Spring Cloud Alibaba
      • 09 Spring Security oAuth2
      • 10 Spring Boot 跨域解决方式
      • 11 Spring Boot 请求拦截
      • 12 Spring Boot 异步编程
      • 13 Spring Boot 定时任务
      • 14 Spring Boot 管理 bean
      • 15 Mybatis 逆向代码生成
      • 16 JWT
      • 17 JPA
      • 18 Apache Shiro
      • 19 Spring 异步请求
  • 书斋
    • ES6 标准入门
      • 01 变量声明与解构赋值
      • 02 语法的扩展
      • 03 数据类型与数据结构
      • 04 Proxy 和 Reflect
      • 05 异步编程 Promise
      • 06 Iterator 和 for of 循环
      • 07 Generator 函数
      • 08 Async 函数
      • 09 Class 类
    • JavaScript 设计模式
      • 01 基础知识
      • 02 设计模式(上)
      • 03 设计模式(下)
      • 04 设计原则和编程技巧
  • 纸函
    • 01 Interview
    • 02 Ceph
    • 03 动态规划
    • 04 Document.designMode
    • 2023-01-10
  • 万藏
    • 文档
      • 01 Git 文档
      • 02 Linux 命令大全
      • 03 七天学会 NodeJS
      • 04 Algorithms
    • 工具
      • 01 Nginx Config
      • 02 ProcessOn
      • 03 Flat Icon
      • 04 Regexper
      • 05 TempMail
      • 06 Carbon
由 GitBook 提供支持
在本页
  • 冒泡排序
  • 经典冒泡算法
  • 改进冒泡算法
  • 终极冒泡算法
  • 选择排序
  • 经典选择算法
  • 插入排序
  • 经典插入算法
  • 二分插入算法
  • 归并排序
  • 经典归并算法

这有帮助吗?

  1. 前端
  2. JavaScript

07 排序算法初探

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

  3. 针对所有的元素重复以上的步骤,除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

冒泡排序平均时间复杂度 O(n^2),在最好情况下,即一次排完時复杂度为 O(n),在最坏情况下复杂度为 O(n^2)。

经典冒泡算法

经典冒泡算法:通过双层循环实现排序,外层循环表示当前是第几轮排序,内层循环表示当前轮的第几次排序,通过两两比较交换位置完成排序。

function bubbleSort(nums) {
  const len = nums.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        ;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]] // 交换位置
      }
    }
  }
  return nums
}

改进冒泡算法

改进冒泡算法:设置一标志性变量 pos,用于记录每轮排序中最后一次进行交换的位置。由于 pos 位置之后的记录均已交换到位,故在进行下一轮排序时只要扫描到 pos 位置即可。

function bubbleSort(nums) {
  const len = nums.length
  let i = len - 1
  while (i > 0) {
    let pos = 0
    for (let j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        pos = j // 记录交换時的位置
        ;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]] // 交换位置
      }
    }
    i = pos
  }
  return nums
}

终极冒泡算法

终极冒泡算法:传统冒泡排序中每一轮排序操作只能找到一个最大值或最小值,可以在每趟排序中进行正向和反向两遍冒泡方法一次得到两个最终值(最大者和最小者),从而使排序轮数几乎减少了一半。

function bubbleSort(nums) {
  let low = 0
  let high = nums.length - 1
  let i
  while (low < high) {
    // 正向排序,找出最大值
    for (i = low; i < high; ++i) {
      if (nums[i] > nums[i + 1]) {
        ;[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]] // 交换位置
      }
    }
    --high // 前移一位

    // 反向排序,找出最小值
    for (i = high; i > low; --i) {
      if (nums[i] < nums[i - 1]) {
        ;[nums[i], nums[i - 1]] = [nums[i - 1], nums[i]] // 交换位置
      }
    }
    ++low // 后移一位
  }
  return nums
}

选择排序

选择排序是一种简单直观的排序算法。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序算法的运作如下:

  1. 初始状态:无序区为 R[1..n],有序区为空。

  2. 第 i 轮排序开始时,当前有序区和无序区分别为 R[1..i-1] 和 R[i..n]。然后从当前无序区中选出最小值,将它与无序区的第一个值交换,使得新增一位有序区和减少一位无序区。

  3. n-1 轮排序结束,数组全部变为有序区,从而完成排序。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对 n 个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

选择排序平均时间复杂度稳定在 O(n^2)。

经典选择算法

经典选择算法:将数列分为有序区和无序区两部分,在每轮循环中从无序区选择一个最小值并入有序区,新增一位有序区同时减少一位无序区,n - 1 轮排序后全部变为有序区,从而完成排序。

function selectionSort(nums) {
  const len = nums.length
  let min = 0
  for (let i = 0; i < len - 1; i++) {
    min = i
    for (let j = i + 1; j < len; j++) {
      if (nums[min] > nums[j]) {
        min = j // 保存最小值的索引
      }
    }
    ;[nums[i], nums[min]] = [nums[min], nums[i]] // 交换位置
  }
  return nums
}

插入排序

是一种简单的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序算法的运作如下:

  1. 从第一个元素开始,该元素可以认为已经被排序。

  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描,如果该元素大于新元素,将该元素移到下一位置。

  3. 重复步骤 2,直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置后。

  4. 重复步骤 2~3,直到完成排序。

插入排序平均时间复杂度 O(n^2),在最好情况下复杂度为 O(n),在最坏情况下复杂度为 O(n^2)。

经典插入算法

经典选择算法:将数列分为有序区和无序区两部分,在每轮循环中从无序区选择一个最小值并入有序区,新增一位有序区同时减少一位无序区,n - 1 轮排序后全部变为有序区,从而完成排序。

function insertionSort(nums) {
  const len = nums.length
  for (let i = 1; i < len; i++) {
    let k = nums[i]
    let j = i - 1
    while (j >= 0 && nums[j].num > k.num) {
      nums[j + 1] = num[j]
      j--
    }
    nums[j + 1] = k
  }
  return nums
}

二分插入算法

二分插入算法:查找插入位置时使用二分查找的方式,在插入值之前,先在有序区中找到待插入值需要比较的左边界,在数据长度较大时,可以有效减少每轮排序中的查找插入位置的次数。

function insertionSort(nums) {
  const len = nums.length
  for (let i = 1; i < len; i++) {
    let k = nums[i]
    let left = 0
    let right = i - 1
    while (left <= right) {
      let middle = ~~((left + right) / 2)
      if (k < nums[middle]) {
        right = middle - 1
      } else {
        left = middle + 1
      }
    }
    for (let j = i - 1; j >= left; j--) {
      nums[j + 1] = nums[j]
    }
    nums[left] = k
  }
  return nums
}

归并排序

归并排序是创建在归并操作上的一种有效的排序算法。归并操作也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序时间复杂度为 O(nlogn)。该算法是采用分治法的一个非常典型的应用,且各层分治递归可以同时进行。

归并排序算法的运作如下:

  1. 将长度为 n 的序列每相邻两个数字进行归并操作,形成 n/2 个序列,排序后每个序列包含二或一个元素。

  2. 若此时序列数不是 1 个则将上述序列再次归并,形成 n/4 个序列,每个序列包含三或四个元素。

  3. 重复步骤 2,直到所有元素排序完毕,即序列数为 1,即完成排序。

  4. 归并排序平均时间复杂度稳定在 O(nlogn)。

经典归并算法

经典归并算法:将数列分为两个子序列,如果子序列长度不为一,再将子序列细分,直至子序列长度为一。递归比较两个子序列并排序后,再相互组合成有序数列,最终完成排序。

function mergeSort(nums) {
  const len = nums.length
  if (len <= 1) return nums
  let middle = ~~(len / 2)
  let left = nums.slice(0, middle)
  let right = nums.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
  const result = []
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  return result.concat(left, right)
}
上一页06 函数节流与函数防抖下一页08 洗牌算法实现数组乱序

最后更新于2年前

这有帮助吗?