金点网络-全网资源,一网打尽
  • 网站首页
    • 金点部落
    • 小游戏
    • OpenAPI
    • 设计资产导航
    • 升级会员
  • 技能学习
    • 体育运动
    • 办公教程
    • 口才演讲
    • 小吃技术
    • 建站教程
    • 摄影教程
    • 棋牌教程
    • 网赚教程
      • 爆粉引流
      • 自媒体
      • 贴吧引流
  • 网站源码
    • 商城/淘客/交易
    • 小说/漫画/阅读
    • 影视/音乐/视频
    • 微信/微商/微擎
    • 理财/金融/货币
    • 模板/主题/插件
  • 游戏源码
    • 精品网单
    • 端游源码
    • 手游源码
    • 页游源码
  • 素材资料
    • 电子文档
    • 综合资料
    • 考研资料
    • 设计素材
    • 音频讲座
      • 人文艺术
      • 名师讲座
      • 说书小说
  • 软件工具
    • Windows软件
    • MacOS软件
    • Android软件
  • 寄售资源
    • 游戏源码
    • 网站源码
    • 软件源码
  • 公益服
登录/注册
  • 专享大神特权
立即开通开通会员抄底价

JavaScript·排序算法初探

作者 : jamin 本文共3647个字,预计阅读时间需要10分钟 发布时间: 2020-10-18 共1035人阅读

排序算法初探

冒泡排序

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

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

  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)
}
Javascript 前端
本站所提供的部分资源来自于网络,版权争议与本站无关,版权归原创者所有!仅限用于学习和研究目的,不得将上述内容资源用于商业或者非法用途,否则,一切后果请用户自负。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源。如果上述内容资对您的版权或者利益造成损害,请提供相应的资质证明,我们将于3个工作日内予以删除。本站不保证所提供下载的资源的准确性、安全性和完整性,源码仅供下载学习之用!如用于商业或者非法用途,与本站无关,一切后果请用户自负!本站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。如有侵权、不妥之处,请联系站长以便删除!
金点网络-全网资源,一网打尽 » JavaScript·排序算法初探

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用?
本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
是否提供免费更新服务?
持续更新,永久免费
是否经过安全检测?
安全无毒,放心食用
jamin

jamin 大神

下一篇
网络协议-组播介绍

相关推荐

JavaScript·JavaScript 正则技巧

JavaScript·JavaScript 正则技巧

前端 实战项目·神奇的 Document.designMode

前端 实战项目·神奇的 Document.designMode

Vue·动态可响应对象

Vue·动态可响应对象

CSS·Position 定位

CSS·Position 定位

JavaScript·JavaScript 秘密花园

JavaScript·JavaScript 秘密花园

标签云
Android Atom ExecutorService ForkJoin GM GM后台 GM授权后台 H5 Java Javascript Linux手工服务端 pipbestcom Python ReentrantLock synchronized ThreadLocal volatile Win一键即玩服务端 一键端 传奇 写作 创业 单机 后台 商业端 外网 安卓 安卓苹果双端 工具 手工端 手游 搭建教程 教程 数据分析 文案 游戏源码 端游 经典 网单 职场 自媒体 视频教程 详细搭建教程 运营后台 页游

近期文章

  • 回合手游【逍遥西游之繁华西游】最新整理单机一键既玩镜像服务端_Linux手工端_GM后台_教程
  • 最新整理精品回合制手游【天书奇谈3D混沌完整版】VM一键单机版_linux手工外网端_隐盟视频教程_授权GM后台_双端
  • 典藏修真页游【诸仙列传OL】最新整理Win系服务端_GM工具_详细外网搭建教程
  • MT3换皮MH【浮生若梦尊享挂机修复版】最新整理单机一键即玩镜像端_Linux手工服务端_安卓苹果双端_GM后台_详细搭建教程
  • 大话回合手游【最新引擎之缥缈西游渡劫版】最新整理Linux手工服务端_安卓苹果双端_管理后台_CDK后台_详细搭建教程_视频教程

分类

  • | wordpress插件 |
  • | wordpress模板 |
  • | 其它模板 |
  • | 帝国模板 |
  • | 织梦插件 |
  • | 织梦模板 |
  • A5源码
  • Android软件
  • APP引流
  • E语言
  • H5
  • LUA
  • QQ营销
  • SEO推广
  • Windows软件
  • 体育运动
  • 信息数据
  • 创业专题
  • 办公教程
  • 口才演讲
  • 名师讲座
  • 商城/淘客/交易
  • 小吃技术
  • 小说/漫画/阅读
  • 建站教程
  • 引流脚本
  • 影视/音乐/视频
  • 影视资源
  • 微信/微商/微擎
  • 微信小程序
  • 微信营销
  • 微擎模块
  • 手游源码
  • 技能学习
  • 抖音课程
  • 摄影教程
  • 棋牌教程
  • 模板/主题/插件
  • 游戏源码
  • 爆粉引流
  • 理财/金融/货币
  • 生活老师
  • 电商客
  • 电子文档
  • 电脑教程
  • 社群营销
  • 站长工具
  • 精品网单
  • 系统工具
  • 素材资料
  • 综合资料
  • 编程经验
  • 网站源码
  • 网络安全
  • 网赚教程
  • 网赚源码
  • 考研资料
  • 脚本/AI/智能
  • 自媒体
  • 英语学习
  • 营销软件
  • 设计素材
  • 说书小说
  • 贴吧引流
  • 软件工具
  • 软文营销
  • 逆向软件
  • 音频讲座
  • 页游源码

提供最优质的资源集合

立即加入 友好社区
金点网络-全网资源,一网打尽

新一代全网资源综合门户网(www.pipbest.com-金点网络)专注服务于互联网,提供各类最新最全的免费源码下载(PHP、ASP、JSP、.NET),更提供免费工具,免费源码下载,软件下载,素材下载,赚钱教程下载,交流论坛等网站运营相关的一切内容,为网友搜罗最有价值的网站源码下载与技术教程等服务!

服务目录
  • 金点OpenAPI
  • 金点云
  • 金点支付
友情链接
  • 数媒派
  • 国家电网
快速搜索

本站由Nice强力驱动

声明: 本站部分内容属于原创转载请注明出处 如有侵权行为请严格参照本站【版权声明】与我们联系,我们将在48小时内容进行处理!

本站部分内容属于原创转载请注明出处 如有侵权行为请严格参照本站【版权声明】与我们联系,我们将在48小时内容进行处理!
© 2016-2023 PipBest.Com - 金点网络 & 金点部落. All rights reserved 京ICP备2022005359号-1
  • 关注有礼
  • 签到
  • 客服
    官方QQ群 常见问题 FAQ

    在线客服

    点我联系

    直接说出您的需求!
    切记!带上资源连接与问题!

    工作时间: 9:30-21:30

  • 暗黑
    模式
  • 全屏
  • 投稿
    赚钱
  • 首页

  • 签到

  • 切换

  • 客服

金点网络-全网资源,一网打尽
  • 登录
  • 注册
or
or
忘记密码?
金点网络-全网资源,一网打尽
  • 网站首页 ►
    • 金点部落
    • 小游戏
    • OpenAPI
    • 设计资产导航
    • 升级会员
  • 技能学习 ►
    • 体育运动
    • 办公教程
    • 口才演讲
    • 小吃技术
    • 建站教程
    • 摄影教程
    • 棋牌教程
    • 网赚教程 ►
      • 爆粉引流
      • 自媒体
      • 贴吧引流
  • 网站源码 ►
    • 商城/淘客/交易
    • 小说/漫画/阅读
    • 影视/音乐/视频
    • 微信/微商/微擎
    • 理财/金融/货币
    • 模板/主题/插件
  • 游戏源码 ►
    • 精品网单
    • 端游源码
    • 手游源码
    • 页游源码
  • 素材资料 ►
    • 电子文档
    • 综合资料
    • 考研资料
    • 设计素材
    • 音频讲座 ►
      • 人文艺术
      • 名师讲座
      • 说书小说
  • 软件工具 ►
    • Windows软件
    • MacOS软件
    • Android软件
  • 寄售资源
    ►
    • 游戏源码
    • 网站源码
    • 软件源码
  • 公益服
×
u3** 刚刚下载了 爆款吸金文案训练

    全网资源·一网打尽

  • 金点出品,必属精品!
  • 发布原创内容,获取高额提成!
  • 我们与你共创美好数字生态!
  • 无特殊说明密码默认:pipbest.com