当前位置: 首页 > news >正文

数据结构与算法之排序: 归并排序 (Javascript版)

排序

  • 排序:把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)

归并排序

  • 该排序属于 分治 策略
  • 将一个问题分解为两个问题来计算,计算完成之后,就会得到子任务的解,这些解不是最终问题的解,还需要merge起来

算法实现

// 归并排序
Array.prototype.mergeSort = function() {// 递归自身拆分const rec = (arr) => {let len = arr.length;if(len === 1) {return arr;}let m = Math.floor(len / 2); // 取中值let l = arr.slice(0, mid);let r = arr.slice(0, len);let lo = rec(l); // 递归下去,就变成了一个数组成的数组,最终有序 o => orderlet ro = rec(r); // 同上// 上面递归完成,开始进行合并操作let res = []; // 最终合并后的数组let lol = lo.length; // 左边数组长度let lor = ro.length; // 右边数组长度while(lol || lor) {if(lol && lor) {res.push(lo[0] < ro[0] ? lo.shift() : ro.shift())} else if(lol) {res.push(lo.shift())} else if(rol) {res.push(ro.shift())}}return res;}// 获取递归结果const r = rec(this);// 将有序数组拷贝到this上r.forEach((n, i) => {this[i] = n;});
}let arr = [5,4,3,2,1]
arr.insertionSort()
console.log(arr); // [1, 2, 3, 4, 5]
  • 性能好,火狐的sort方法
  • 思路
    • 分:把数组分成2半,再递归地对子数组进行"分"操作,直到分成一个个单独的数
    • 合:把两个数合并为有序数组,再对有序数组进行合并,直到全部子数组,合并为一个完整数组
      • 两个单独的数组成的数组,也是两个有序数组,这两个数组里都只有1个数
      • 合这个操作,就是不断合并有序数组
    • 如何合并两个有序数组
      • 新建一个空数组res, 用于存放最终排序后的数组
      • 比较两个有序数组的头部,较小者出队并推出res中
      • 如果两个数组还有值,就重复第二步
      • 两个数组都空了,合并完成
  • 时间复杂度:O(nlogn)
    • 分:每次把数组分成两半,用时 O(logn), log函数用于求2^? = n, 自然要?=log_2 n, 即 O(logn)
      • 注意,凡是分的操作,基本都是logn
    • 合:O(n), 一个while循环体

相关文章:

数据结构与算法之排序: 归并排序 (Javascript版)

排序 排序&#xff1a;把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例) 归并排序 该排序属于 分治 策略将一个问题分解为两个问题来计算&#xff0c;计算完成之后&#xff0c;就会得到子任务的解&#xff0c;这些解不是最终问题的解&#xff0c;还需要merge起来…...

Java练习题2021-2

"某地大数据防疫平台记录了往来的所有防疫相关信息&#xff0c;包括 本地或外地人员、健康码颜色、接种疫苗情况、最近一次核酸结果、最近一次核酸检测时间等。 该地某区域对于进入人员的要求为&#xff1a; 如果是本地人员&#xff0c;需要绿码和疫苗完全接种方可进入&am…...

深度学习面试题目01

01 什么是神经网络&#xff1f;02 请解释前馈神经网络&#xff08;Feedforward Neural Network&#xff09;的工作原理。03 什么是激活函数&#xff0c;为什么它在神经网络中重要&#xff1f;04 请解释反向传播算法&#xff08;Backpropagation&#xff09;05 什么是过拟合&…...

ESP32网络开发实例-HTTP-POST请求

HTTP-POST请求 文章目录 HTTP-POST请求1、HTTP POST2、软件准备3、硬件准备4、代码实现在本文中,我们将介绍如何使用 ESP32向 ThingSpeak等常用 API 发出 HTTP POST 请求。 1、HTTP POST 超文本传输协议 (HTTP) 用作服务器和客户端之间的请求-响应协议。 它使它们之间的通信顺…...

怎么把成绩发给家长

亲爱的小伙伴们&#xff0c;作为老师&#xff0c;我们经常需要将学生的成绩发送给家长。但是&#xff0c;手动发送成绩不仅效率低&#xff0c;还容易出错。这时候&#xff0c;我们就需要一个强大的工具——成绩查询系统。它不仅可以轻松实现学生成绩的录入、存储和查询&#xf…...

Banana Pi BPI-W3 RK3588开发板基本使用文档

RK3588编译&烧录Linux固件 1、开发环境及工具准备 Rockchip Linux 软件包&#xff1a;linux-5.10-gen-rkr4 主机&#xff1a; 安装VMware搭建虚拟机&#xff0c;版本为Ubuntu 20.04 (硬盘容量大于100G&#xff09;安装远程连接工具MobaXterm&#xff08;可连接虚拟机方…...

源码解析SpringMVC之RequestMapping注解原理

1、启动初始化 核心&#xff1a;得到应用上下文中存在的全部bean后依次遍历&#xff0c;分析每一个目标handler & 目标方法存在的注解RequestMapping&#xff0c;将其相关属性封装为实例RequestMappingInfo。最终将 uri & handler 之间的映射关系维护在类AbstractHand…...

biocParallel学习

我好像做了一个愚蠢的测试 rm(listls()) suppressPackageStartupMessages({library(SingleCellExperiment)library(scMerge)library(scater)library(Matrix) })setwd("/Users/yxk/Desktop/test/R_parallel/") load("./data/exprsMat.RData") load(".…...

AWTK实现汽车仪表Cluster/DashBoard嵌入式GUI开发(六):一个AWTK工程

一个AWTK工程基于C/C++编写,可以分为如下几步: 结合下图,看懂启动的部分。一般一个AWTK工程,需要实现哪些部分,就是其中开始之后白色的部分,比如调用main函数和gui_app_start时会做一些操作,比如asset_init和application_init时要做一些设置,还有退出的函数application…...

MySQL主从复制(基于binlog日志方式)

目录 一、什么是主从复制&#xff1f;二、主从复制原理、存在问题和解决方法2.1.主从复制原理2.2.主从复制存在的问题以及解决办法2.3.主从复制的同步模型2.4.拓展—Mysql并行复制 三、主从复制之基于binlog日志方式3.1.bin-log日志简介3.2.bin-log的使用3.2.1.开启binlog3.2.2…...

计算机网络【CN】介质访问控制

信道划分介质访问控制 FDMTDMWDMCDM【掌握eg即可】 随机介质访问控制 CSMA 1-坚持CSMA 非坚持CSMA p-坚持CSMA 空闲时 立即发送数据 立即发送数据 以概率P发送数据&#xff0c;以概率1-p推迟到下一个时隙 忙碌时 继续坚持侦听 放弃侦听&#xff0c;等待一个随机的时…...

CDR和AI哪个软件更好用?

设计软件市场中&#xff0c;CorelDRAW和Adobe Illustrator&#xff08;简称AI&#xff09;无疑是两大重量级选手。它们各自拥有庞大的用户群和丰富的功能&#xff0c;但究竟哪一个更好用&#xff1f;本文将从多个角度出发&#xff0c;对这两款软件进行全面而深入的比较&#xf…...

保姆级认识AVL树【C++】(精讲:AVL Insert)

目录 前言 一&#xff0c;概念 二&#xff0c;定义 三&#xff0c;insert 1. 插入情况 情况一&#xff1a; 情况二&#xff1a; 情况三&#xff1a; 2. 旋转方法 法一&#xff1a;左单旋法 法二&#xff1a;右单旋法 法三&#xff1a;先左后右双旋法 法四&#xf…...

pinia中使用reactive声明变量,子页面使用时,值未改变,即不是响应式的(解决方法)

reactive赋值无效&#xff01;reactive 不要直接data赋值&#xff01;&#xff01;&#xff01;会丢失响应式的&#xff0c;只能通过obj.属性 属性值赋值 方法一. pinia中直接使用ref定义变量即可 export const useUserStoredefineStore(user,()>{let loginUserreactive({…...

基于springboot零食商城管理系统

功能如图所示 摘要 这基于Spring Boot的零食商城管理系统提供了强大的购物车和订单管理功能。用户可以在系统中浏览零食产品&#xff0c;并将它们添加到购物车中。购物车可以保存用户的选购商品&#xff0c;允许随时查看已选择的商品和它们的数量。一旦用户满意&#xff0c;他们…...

C++程序练习

定义一个类CheckPath&#xff0c;它由两个public方法组成&#xff1a; 1&#xff09; checkPath&#xff1a;检查传入的字符串指定的路径是否存在&#xff0c;存在返回true&#xff0c;否则返回false。 2&#xff09; createFilePath&#xff1a;根据传入的字符串指定的路径&…...

Golang 继承

在面向对象的编程语言中&#xff0c;继承是一种重要的机制&#xff0c;它允许子类继承父类的属性和方法。然而&#xff0c;Go语言在设计时没有直接支持传统意义上的继承&#xff0c;而是提供了一种更为灵活和简洁的方式来实现类似的功能。本文将探讨Golang中实现继承的方法和最…...

棋盘格测距-单目相机(OpenCV/C++)

一、文章内容简述&#xff1a; 1’ 通过cv::findChessboardCorners寻找棋盘格角点 2‘ 用cv::solvePnP计算旋转向量rvec和平移向量tvec 3’ 通过公式计算相机到棋盘格的距离 float distance sqrt(tvec.at<double>(0,0) * tvec.at<double>(0,0) tvec.at<do…...

031-从零搭建微服务-监控中心(一)

写在最前 如果这个项目让你有所收获&#xff0c;记得 Star 关注哦&#xff0c;这对我是非常不错的鼓励与支持。 源码地址&#xff08;后端&#xff09;&#xff1a;mingyue: &#x1f389; 基于 Spring Boot、Spring Cloud & Alibaba 的分布式微服务架构基础服务中心 源…...

vue中使用xlsx插件导出多sheet excel实现方法

安装xlsx&#xff0c;一定要注意版本&#xff1a; npm i xlsx0.17.0 -S package.json&#xff1a; {"name": "hello-world","version": "0.1.0","private": true,"scripts": {"serve": "vue-c…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

李沐--动手学深度学习--GRU

1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...