【算法与数据结构】JavaScript实现十大排序算法(一)

文章目录

  • 关于排序算法
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 希尔排序
  • 归并排序

关于排序算法

在这里插入图片描述

稳定排序: 在排序过程中具有相同键值的元素,在排序之后仍然保持相对的原始顺序。意思就是说,现在有两个元素a和b,a排在b的前面,且a==b,排序之后a仍然在b的前面,这就是稳定排序。

非稳定排序: 在排序过程中具有相同键值的元素,在排序之后可能会改变它们的相对顺序。意思是说,现在有两个元素a和b,在原始序列中a排在b前面,排序之后a可能会出现在b后面,它们的相对位置可能会发生变化。

原地排序: 在排序过程中不需要申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。这意味着在原地排序中,排序操作会直接修改原始数据,而不需要创建新的数据结构来存储排序后的结果。

非原地排序: 在排序过程中需要申请额外的存储空间来存储临时数据或排序结果,而不直接在原始数据上进行修改。

冒泡排序

基本思路: 通过相邻元素之间的比较和交换,将排序码小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底下的气泡一样逐渐向上冒,因此称为冒泡排序。

操作步骤:

  • 比较相邻的两个元素。如果第一个元素比第二个元素大,就交换这两个元素;
  • 重复上述步骤,直到数组末尾;
  • 重复上述两个步骤,直到完成排序。
    在这里插入图片描述

例题:

a=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48] 进行从小到大排序。

  <script>function BubbleSort(arr) {for (let i in arr) {// 每次循环都能找到一个最大的数放在最右边for (let j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {let temp = arr[j]arr[j] = arr[j + 1]arr[j + 1] = temp}}}console.log(arr);return arr}let a = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]BubbleSort(a)</script>

总结: 稳定排序,需要开辟极少的空间,空间复杂度为O(1),时间复杂度为O(n²)。

选择排序

基本思路: 首先在未排序序列中找到最小(大)元素,存放到排序的起始位置,接着再从剩余末排序元素中继续寻找最小(大)元素,放到已排序序列的起始位置。以此类推,直到所有的元素均已排序完毕。

操作步骤:

  • 在数列范围内找到最小(大)元素,与起始位置元素进行交换;
  • 除已经排序过的元素外,在剩余数列范围内找到最小(大)元素,与剩余数列的起始位置元素进行交换。
    在这里插入图片描述
    例题:

a=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48] 进行从小到大排序。

  <script>function SelectionSort(arr) {for (let i in arr) {// 声明一个变量,用来接收当前最小值的下标let min = ifor (let j = i; j < arr.length; j++) {if (arr[j] < arr[min]) {min = j}}let temp = arr[i]arr[i] = arr[min]arr[min] = temp}console.log(arr);return arr}let a = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]SelectionSort(a)</script>

分析: 不稳定排序,需要开辟极少的空间,空间复杂度为O(1),时间复杂度为O(n²)。

插入排序

基本思路: 将数组分为两部分,一部分是已排序的,一部分是未排序的。初始时,已排序部分只包含数组的第一个元素,然后依次将未排序部分的元素插入已排序部分,使得已排序部分仍然保持有序。

操作步骤:

  • 将第一个数作为基准,取出第二个数与其进行比较,如果比它大就放右边,比它小就放左边;
  • 取出第三个数,与前一个数进行比较,比它大就放右边,比它小就再往前一个数进行比较,直到遇到一个比它小的数;
  • 一直重复上述步骤
    在这里插入图片描述
    例题:

a=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48] 进行从小到大排序。

  <script>function InsertionSort(arr) {// 以第一个数作为基准for (let i = 1; i < arr.length; i++) {let temp = arr[i]let j;// 如果遍历的元素大于取出的元素,则遍历过的元素都需要后移一位for (j = i - 1; j >= 0 && a[j] > temp; j--) {arr[j + 1] = arr[j]}arr[j + 1] = temp}console.log(arr);}let a = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]InsertionSort(a)</script>

分析: 稳定排序,需要开辟极少的空间,空间复杂度为O(1),时间复杂度为O(n²)。

希尔排序

基本思路: 它是插入排序的一种改进版本,通过将原始数组分成多个子序列,利用插入排序对子序列进行排序,最终合并成一个有序序列。

操作步骤:

  • 选择一个增量序列(间隔序列),通常初始增量为数组长度的一半,然后逐渐减小增量;
  • 按照增量将原始数组分成多个子序列。每个子序列可以视为一个小型数组;
  • 对每个子序列应用插入排序算法,将子序列中的元素进行排序;
  • 逐渐缩小增量,重复上述步骤,直到增量为 1;
  • 最后一次增量为 1 时,整个数组被视为一个序列,再次应用插入排序。

在这里插入图片描述

例题:

a=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48] 进行从小到大排序。

  <script>function ShellSort(arr) {// 选择初始的增量(gap)为数组长度的一半Math.floor(arr.length / 2)for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {// 对每个子序列进行插入排序for (let i = gap; i < arr.length; i++) {const temp = arr[i]let j;for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {arr[j + gap] = arr[j]}arr[j + gap] = temp}}console.log(arr);}let a = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]ShellSort(a)</script>

分析: 不稳定排序,需要开辟极少的空间,空间复杂度为O(1),时间复杂度为O(nlog(n))。

归并排序

基本思路: 它是一种基于分治策略的排序算法,通过将待排序的数组分割成若干个子序列,分别排序后再合并这些子序列,以达到整体有序的目的。归并排序的主要步骤包括分割、排序和合并三个阶段。

操作步骤:

  • 分割:将待排序的数组分成两个大致相等的子数组,递归地对这两个子数组进行排序;
  • 排序:递归地对每个子数组进行排序,直到子数组的长度为1(只有一个元素),此时认为它是有序的;
  • 合并:将排好序的子数组合并成一个新的有序数组,这一步的关键是将两个有序的子数组合并成一个更大的有序数组。
    在这里插入图片描述
    例题:

a=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48] 进行从小到大排序。

  <script>function MergeSort(arr) {if (arr.length <= 1) return arr;// 分割数组const middle = Math.floor(arr.length / 2)const left = arr.slice(0, middle)const right = arr.slice(middle)// 递归分割+排序const leftSort = MergeSort(left)const rightSort = MergeSort(right)return SequencSort(leftSort, rightSort)}function SequencSort(left, right) {let result = []let leftIndex = 0;let rightIndex = 0;// 合并两个有序数组while (leftIndex < left.length && rightIndex < right.length) {if (left[leftIndex] < right[rightIndex]) {result.push(left[leftIndex])leftIndex++} else {result.push(right[rightIndex])rightIndex++}}// 将剩余的元素添加到结果中return result.concat(left.slice(leftIndex), right.slice(rightIndex))}let a = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]MergeSort(a)</script>

分析: 稳定排序,空间复杂度为O(n),时间复杂度为O(nlog(n))。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/144477.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

十九,镜面IBL--BRDF积分贴图

再回顾下镜面部分的分割求和近似法 现在关注第二部分 最后可化为 也就是说&#xff0c;这两部分积分可以获得F0的系数和F0的偏差。 这两个值可以存储到BRDF积分贴图的RG部分。void main() { vec2 integratedBRDF IntegrateBRDF(TexCoords.x, TexCoords.y); FragColor …

图扑软件受邀亮相 IOTE 2023 国际物联网展

IOTE 2023 国际物联网展&#xff0c;作为全球物联网领域的盛会&#xff0c;于 9 月 20 日 - 22 日在中国深圳拉开帷幕。本届展会以“IoT构建数字经济底座”为主题&#xff0c;由深圳市物联网产业协会主办&#xff0c;打造当前物联网最新科技大秀。促进物联网与各行业深度融合&a…

ALM物联网管理平台助力中台上云 数字化转型让展示更直观清晰

支持移动浏览、支持大屏显示等功能&#xff0c;能够为设备厂家提供数据依据&#xff0c;方便厂家的售后以及产品的维护、为运维等相关公司提供运维管理等相关功能。 ALM物联网云平台是基于以往的物联网产品&#xff0c;以及目前市场上的各种云平台优点&#xff0c;研精心打造的…

排序:基数排序算法分析

1.算法思想 假设长度为n的线性表中每个结点aj的关键字由d元组 ( k j d − 1 , k j d − 2 , k j d − 3 , . . . , k j 1 , k j 0 ) (k_{j}^{d-1},k_{j}^{d-2},k_{j}^{d-3},... ,k_{j}^{1} ,k_{j}^{0}) (kjd−1​,kjd−2​,kjd−3​,...,kj1​,kj0​)组成&#xff0c; 其中&am…

缓存一致性(cache coherency)解决方案:MESI 协议状态转换详解

MESI 协议 一&#xff0c;MESI状态释义二&#xff0c;MESI状态转换1 Invalid after Reset2, Invalid > Exclusive3, Exclusive > Modified4 Modified > Shared, Invalid > Shared5 Shared > Invalid, Shared > Modified 三&#xff0c;状态转换场景总结Inval…

Linux常见指令2

Linux常见指令[2] 一.Linux常见指令1.man补充知识:nano 2.cp3.mv4.cat补充知识:echo输出重定向追加重定向回到catcat其他用法 5.less和more补充内容回到less 6.head和tail补充知识:命令行管道 一.Linux常见指令 前言:为了方便我们在Linux中写指令 介绍一下: 1.clear指令: 清屏…

【每日一题】2769. 找出最大的可达成数字

2769. 找出最大的可达成数字 - 力扣&#xff08;LeetCode&#xff09; 给你两个整数 num 和 t 。 如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等&#xff0c;则称其为 可达成数字 &#xff1a; 每次操作将 x 的值增加或减少 1 &#xff0c;同时可以选择将 …

红黑树是如何实现的?

文章目录 一、红黑树的概念二、红黑树的性质三、红黑树和AVL树对比四、红黑树的插入1. 红黑树的结点定义2. 父亲的颜色3. 叔叔的颜色为红色4. 叔叔不存在5. 叔叔存在且为黑6. 插入的抽象图 五、红黑树的验证1. 检查平衡2. 计算高度与旋转次数3. 验证 六、 红黑树与AVL树的比较 …

基于SSM+Vue的医院住院综合服务管理系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用Vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

ROS系统读取USB相机图像数据

ROS系统读取USB相机图像数据 前言usb_cam 功能包下载与编译摄像头选择连接摄像头可配置参数 前言 usb_cam功能包简介 为了丰富机器人与外界的交互方式&#xff0c;已经增加了与机器人的语音交互方式&#xff0c;不仅使机器人能够说话发声&#xff0c;还能听懂我们说的话&#…

Windows中实现将bat或exe文件作为服务_且实现命令行安装、配置、启动、删除服务

一、背景描述 在Windows环境下进行日常的项目开发过程中&#xff0c;有时候需要将bat文件或exe文件程序注册为Windows的服务实现开机自己运行&#xff08;没有用户登陆&#xff0c;服务在开机后也可以照常运行&#xff09;、且对于那些没有用户交互界面的exe程序来说只要在后台…

STL upper_bound和lower_bound函数

声明&#xff1a; 首先包含头文件#include<algorithm> 这里的两个函数所运用的对象必须是非递减的序列&#xff08;也就是数组&#xff0c;数组必须是非递减的&#xff09;&#xff0c;只有这样才可以使用upper_bound和lower_bound这两个函数。 还有一点&#xff0c;就…

Python入门教程48:Pycharm永久镜像源的pip配置方法

国内几个好用的Python镜像服务器地址&#xff1a; 清华大学镜像站&#xff1a;https://pypi.tuna.tsinghua.edu.cn/simple/阿里云镜像站&#xff1a;https://mirrors.aliyun.com/pypi/simple/中科大镜像站&#xff1a;https://pypi.mirrors.ustc.edu.cn/simple/中国科技大学镜…

HTML5福利篇--使用Canvas画图

目录 一.Canvas元素 1.Canvas元素定义 2.使用JavaScript获取页面中的Canvas对象 二.绘制图形 1.绘制直线 2.绘制矩形 &#xff08;1&#xff09;rect() &#xff08;2&#xff09;strokeRect() &#xff08;3&#xff09;fillRect()和clearRect()函数 3.绘制圆弧 4.…

ElementUI之首页导航+左侧菜单->mockjs,总线

mockjs总线 1.mockjs 什么是Mock.js 前后端分离开发开发过程当中&#xff0c;经常会遇到以下几个尴尬的场景&#xff1a; - 老大&#xff0c;接口文档还没输出&#xff0c;我的好多活干不下去啊&#xff01; - 后端小哥&#xff0c;接口写好了没&#xff0c;我要测试啊&#x…

opencv: 解决保存视频失败的问题

摘要&#xff1a;opencv能读取视频&#xff0c;但保存视频时报错。 一、首先要确保已经下载了openh264.dll文件&#xff0c;否则保存的视频无法打开&#xff0c;详细可以浏览这个&#xff1a;opencv&#xff1a;保存视频。 二、保存视频时出现一下问题&#xff1a; OpenCV:…

COCO 数据集 人体关键点格式

图片与标注数据在 COCO官网 均提供下载 标注格式 COCO 的标注中包含 4 个部分/字段&#xff0c;"info" 描述数据集&#xff0c;"licenses" 描述图片来源&#xff0c;"images" 和 "annotations" 是主体部分 "images" 部分…

一文带你全面解析postman工具的使用

写在前面&#xff1a;本文转自今日头条作者雨滴测试&#xff0c;感兴趣可点击下方链接查看原文 基础篇效率篇高级篇 一文带你全面解析postman工具的使用 文章目录 一文带你全面解析postman工具的使用基础篇一、postman安装说明1.下载与安装2.界面导航说明3.发送第一个请求 二、…

3 OpenCV两张图片实现稀疏点云的生成

前文&#xff1a; 1 基于SIFT图像特征识别的匹配方法比较与实现 2 OpenCV实现的F矩阵RANSAC原理与实践 1 E矩阵 1.1 由F到E E K T ∗ F ∗ K E K^T * F * K EKT∗F∗K E 矩阵可以直接通过之前算好的 F 矩阵与相机内参 K 矩阵获得 Mat E K.t() * F * K;相机内参获得的方式…

87、Redis 的 value 所支持的数据类型(String、List、Set、Zset、Hash)---->List相关命令

本次讲解要点&#xff1a; List相关命令&#xff1a;是指value中的数据类型 启动redis服务器&#xff1a; 打开小黑窗&#xff1a; C:\Users\JH>e: E:>cd E:\install\Redis6.0\Redis-x64-6.0.14\bin E:\install\Redis6.0\Redis-x64-6.0.14\bin>redis-server.exe redi…