JavaScript排序大揭秘:手绘图解6大常见排序算法,一网打尽

前言

 📫 大家好,我是南木元元,热爱技术和分享,欢迎大家交流,一起学习进步!

 🍅 个人主页:南木元元

本文用图解总结梳理了6种常见的排序算法 ,如下👇:

  • 冒泡排序 
  • 选择排序
  • 插入排序
  • 快速排序
  • 归并排序
  • 堆排序

目录

 一.冒泡排序

思路及图解

代码实现

二.选择排序

思路及图解

代码实现

三.插入排序

思路及图解

代码实现

四.快速排序

思路及图解

代码实现

五.归并排序

思路及图解

代码实现

六.堆排序

思路及图解

代码实现

结语


一.冒泡排序

思路及图解

  • 基本思路

冒泡排序的基本思路:比较相邻的两个元素,将较大的元素交换到后面。通过多次遍历和两两比较,使得每一轮遍历都能确定一个当前未排序元素的最终位置,直至所有元素有序。

  • 冒泡排序图解

时间复杂度:O(n^2);空间复杂度:O(1)

代码实现

下面是用 JavaScript 实现的冒泡排序代码:

function bubbleSort(arr) {
  //外循环控制比较次数:n-1次
  for (let i = 0; i < arr.length - 1; i++) {
    // 内循环控制比较元素
    for (let j = 0; j < arr.length - 1 - i; j++) {
      // 如果前一个元素比后一个元素大,则交换它们的位置
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; 
      }
    }
  }
  return arr;
}

// 测试
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr));
// 输出:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  • 优化版

如果在某一轮比较中没有发生元素交换,则说明数组已经有序,可以提前结束排序过程。

function bubbleSort(arr) {
  let flag; // 标记位
  for (let i = 0; i < arr.length; i++) {
    flag = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = true; // 发生了交换
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
    if (!flag) break; // 如果一轮比较后没有发生交换,说明已经有序
  }
  return arr;
}

二.选择排序

思路及图解

  • 基本思路

选择排序的基本思路:每次从未排序的部分中选择最小(或最大)的元素,然后将其与未排序部分的第一个元素交换位置,直到整个数组排序完成。

  • 选择排序图解

时间复杂度:O(n^2);空间复杂度:O(1) 

代码实现

下面是用 JavaScript 实现的选择排序代码:

function selectSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i; // 假设当前位置是最小值的位置
    // 在未排序部分找到最小元素的索引 
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 如果当前循环的索引不是最小数的索引,交换它们
    if(i !== minIndex) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

// 测试
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(selectSort(arr));
// 输出:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

三.插入排序

思路及图解

  • 基本思路

基本思想:将待排序的数组分成已排序区间和未排序区间,初始时已排序区间只有一个元素,然后逐步将未排序区间的元素插入到已排序区间的合适位置,直到整个数组排序完成。

整个过程就像打扑克牌,从牌堆顶取一张牌,找到合适的位置插入到已有牌的顺序中。

  • 插入排序图解 

时间复杂度:O(n^2);空间复杂度:O(1) 

代码实现

下面是用 JavaScript 实现的插入排序代码:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // 当前待插入的元素
    let current = arr[i]; 
    let j = i - 1;
    // 将大于当前元素的元素都向后移动
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    // 找到合适的位置插入当前元素
    arr[j + 1] = current; 
  }
  return arr;
}

// 测试
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(insertionSort(arr));
// 输出:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

四.快速排序

思路及图解

  • 基本思路

快排采用分治的思想,选择一个基准元素,将数组分割成两个子数组,小于基准元素的放在左边,大于基准元素的放在右边,然后对这两个子数组进行递归排序,直到左右两部分只剩下一个数。

  • 快速排序图解

时间复杂度:O(nlogn);空间复杂度:O(logn)

代码实现

下面是用 JavaScript 实现的快速排序代码:

function quickSort(arr) {
  //递归出口,如果数组长度小于等于1,直接返回数组,无需排序
  if (arr.length <= 1) {
    return arr; 
  }
  // 选取数组的第一个元素作为基准元素
  const pivot = arr[0]; 
  // 用于存放小于等于基准元素的部分
  const left = []; 
  // 用于存放大于基准元素的部分
  const right = []; 

  // 将小于等于基准元素的数放入 left 数组,大于基准元素的放入 right 数组
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i]); 
    } else {
      right.push(arr[i]);  
    }
  }

  // 递归地对左右两个部分进行排序
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 测试
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(arr));
// 输出:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

五.归并排序

思路及图解

  • 基本思路

归并排序是一种经典的分治算法,核心思想是将待排序数组分成若干个子序列,分别进行排序,然后将已排序的子序列合并成更大的有序序列,直到整个数组排序完成。

  • 归并排序图解

 时间复杂度:O(nlogn);空间复杂度:O(n)

代码实现

下面是用 JavaScript 实现的归并排序代码:

function mergeSort(arr) {
  // 如果数组长度小于 2,不需要排序,直接返回
  if (arr.length < 2) {
    return arr;
  }
  let mid = Math.floor(len / 2);
  // 将数组从中间位置分为左右两个子数组
  let l = arr.slice(0, mid);
  let r = arr.slice(mid);
  // 递归调用mergeSort对左右两个子数组进行排序,并将结果合并
  return merge(mergeSort(l), mergeSort(r));
}

function merge(left, right) {
  let arr = [];
  // 排序并合并两个数组
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      arr.push(left.shift());
    } else {
      arr.push(right.shift());
    }
  }
  // 合并左右子数组中剩余的元素
  return arr.concat(left, right); 
}

// 测试
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(mergeSort(arr));
// 输出:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

六.堆排序

思路及图解

  • 基本思路

堆排序的基本思路:先将待排序的数组构建成一个最大堆(或最小堆),然后依次将堆顶元素与堆尾元素交换并重新调整堆,重复这个过程直到整个数组排序完成。

1.构建最大堆。将待排序的数组视为完全二叉树,从最后一个非叶子节点开始,依次向前调整节点,使得每个节点都满足父节点的值大于或等于子节点的值。

2.交换并调整堆。将堆顶元素(即当前最大的元素)与堆尾元素交换,然后重新调整剩余的元素,使得剩余元素重新构成一个最大堆。重复这个过程,直到所有元素都被排序完成。

  • 堆排序图解

 时间复杂度:O(nlogn);空间复杂度:O(1)

代码实现

下面是用 JavaScript 实现的堆排序代码:

// 调整堆,使得剩余元素重新构成最大堆
function heapify(arr, n, i) {
  let l = i * 2 + 1;
  let r = i * 2 + 2;
  let max = i;
  // 找出左右子节点和当前节点中的最大值
  if (l < n && arr[l] > arr[max]) {
    max = l;
  }
  if (r < n && arr[r] > arr[max]) {
    max = r;
  }
  // 如果最大值不是当前节点,交换节点并继续调整堆
  if (max !== i) {
    [arr[max], arr[i]] = [arr[i], arr[max]];
    heapify(arr, n, max);
  }
}
// 堆排序
function heapSort(arr) {
  let len = arr.length;
  // 建立大根堆,从最后一个非叶子节点开始
  let last = Math.floor((len - 2) / 2);
  for (let i = last; i >= 0; i--) {
    heapify(arr, len, i);
  }
  // 每次把堆顶的数与最后一个数交换,并重新调整堆
  for (let i = 0; i < len; i++) {
    [arr[0], arr[len - 1 - i]] = [arr[len - 1 - i], arr[0]];
    heapify(arr, len - 1 - i, 0);
  }
  return arr;
}

// 测试
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(heapSort(arr));
// 输出:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

结语

🔥如果此文对你有帮助的话,欢迎💗关注、👍点赞、⭐收藏、✍️评论,支持一下博主~ 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

地理空间分析中的深度学习应用

深度学习与地理信息系统 (GIS) 的结合彻底改变了地理空间分析和遥感的格局。这种结合将遥感和地理空间分析领域带到了全球研究人员和科学家的前沿。 深度学习是机器学习的一个复杂子集&#xff08;更多关于机器学习的内容&#xff0c;请参阅我的其他文章&#xff09;&#xff0…

Qt5 编译oracle数据库驱动

库文件 1、Qt源码目录&#xff1a;D:\Qt5\5.15.2\Src\qtbase\src\plugins\sqldrivers\oci 2、oracle客户端SDK: https://www.oracle.com/database/technologies/instant-client/winx64-64-downloads.html 下载各版本中的如下压缩包&#xff0c;一定要版本相同的 将两个压缩包…

如何通过WordPress发送电子邮件

本周有一个客户&#xff0c;购买Hostease的HK Basic Linux虚拟主机&#xff0c;询问我们的在线客服&#xff0c;WordPress发送电子邮件不成功。我们为用户提供教程&#xff0c;用户很快完成了设置。在此&#xff0c;我们分享这个操作教程&#xff0c;希望可以对您有帮助。 Host…

github上的软件许可证是什么?如何合并本地的分支德语难学还是俄语更加难学?站在一个中国人的立场上,德语难学还是俄语更加难学?俄语跟德语有什么样的显著差别?

目录 github上的软件许可证是什么&#xff1f; 如何合并本地的分支 德语难学还是俄语更加难学&#xff1f; 站在一个中国人的立场上&#xff0c;德语难学还是俄语更加难学&#xff1f; 俄语跟德语有什么样的显著差别&#xff1f; github上的软件许可证是什么&#xff1f; …

深入剖析Tomcat(二) 实现一个简单的Servlet容器

现在开始《深入剖析Tomcat》第二章的内容&#xff0c;第一章中&#xff0c;我们编码实现了一个能正常接收HTTP请求并返回静态资源的Web容器&#xff0c;这一章开始引入Servlet的概念&#xff0c;使我们的服务能根据请求动态返回内容。 Servlet是什么&#xff1f; 这是首先要弄…

Linux基础|线程池Part.1|线程池的定义和运行逻辑

线程池的定义和运行逻辑 多线程的问题&#xff1a; 如果并发的线程数量很多&#xff0c;并且每个线程都是执行一个时间很短的任务就结束了&#xff0c;这样频繁创建线程就会大大降低系统的效率&#xff0c;因为频繁创建线程和销毁线程需要时间。 那么一个很自然的想法就出现了…

杂货铺 | Linux虚拟机Ubuntu操作系统下设置共享文件夹(以及找不到hgfs文件夹怎么办)

文章目录 &#x1f4da;步骤一&#xff1a;配置共享文件夹&#x1f4da;步骤二&#xff1a;配置挂载环境&#x1f4da;步骤三&#xff1a;解决权限问题&#x1f4da;步骤四&#xff1a;解决重启失效问题 &#x1f4da;步骤一&#xff1a;配置共享文件夹 建立本地共享文件夹&…

Mysql的事务隔离级别以及事务的四大特性。

MySQL 的事务隔离级别是数据库管理系统中的一个重要概念&#xff0c;它决定了事务如何隔离和影响其他并发事务。MySQL 支持四种事务隔离级别&#xff0c;分别是&#xff1a;读未提交&#xff08;READ UNCOMMITTED&#xff09;、读已提交&#xff08;READ COMMITTED&#xff09;…

Qt QStyle详解

1.简介 QStyle类是 Qt 框架中用于控制应用程序界面元素外观的一个抽象基类。这个类提供了一种方式来定制窗口部件&#xff08;widgets&#xff09;的绘制和行为&#xff0c;可以通过改变主题或风格来更改应用程序的外观&#xff0c;而无需修改窗口部件本身的代码。 Qt包含一组…

一种基于OpenCV的图片倾斜矫正方法

需求描述&#xff1a; 对倾斜的图片进行矫正&#xff0c;返回倾斜角度和矫正后的图片。 解决方法&#xff1a; 1、各种角度点被投影到一个累加器阵列中&#xff0c;其中倾斜角度可以定义为在最大化对齐的搜索间隔内的投影角度。 2、以不同的角度旋转图像&#xff0c;并为每…

Excel文件解析

在此模块的学习中&#xff0c;我们需要一个新的开源类库---Apahche POI开源类库。这个类库的用途是&#xff1a;解析并生成Excel文件(Word、ppt)。Apahche POI基于DOM方式进行解析&#xff0c;将文件直接加载到内存&#xff0c;所以速度比较快&#xff0c;适合Excel文件数据量不…

学习经验分享【32】本科/硕士开题报告、中期报告等写作经验分享

本科/硕士阶段首先就是要写开题报告&#xff0c;然后中期报告&#xff0c;这篇博文就是分享一下写报告的经验&#xff0c;避免被老师打回来。本人有丰富的写报告经验&#xff0c;有需要的朋友可添加文末联系方式与我联系。 一、本科开题报告的提纲 课题来源及研究的目的和意义…

js性能优化(五)

第五章开始啦~~~~~~~~~~~~~ 防抖和节流之前自己有学过一次&#xff0c;包括几种方式怎么实现&#xff0c;代码如何写花了两天有写过&#xff0c;这次算是更系统的一个复习加填补 十七、防抖与节流 为什么需要防抖和节流&#xff1a; 在一些高频率事件触发的场景下我们不希望…

51单片机

STC89C52 一.定时器 1.介绍 2.计时 2.定时器寄存器  2.1 定时器控制寄存器TCON  2.2 定时器模式寄存器TMOD  2.3 定时器如何定时10毫秒  2.4 定时器寄存器配置    2.4.1 TCON    2.4.2 TMOD    2.4.3 实现    2.4.5 按位操作 3.定时器中断  3.1 定…

d盘无法格式化说另一个正在使用怎么办

在日常生活和工作中&#xff0c;我们经常会遇到需要对电脑硬盘进行格式化的情况。然而&#xff0c;有时在尝试格式化D盘时&#xff0c;会遇到一个常见的错误提示&#xff1a;“另一个程序正在使用此文件&#xff0c;因此无法进行操作”。这个提示可能会让许多人感到困惑&#x…

《自动机理论、语言和计算导论》阅读笔记:p172-p224

《自动机理论、语言和计算导论》学习第 8 天&#xff0c;p172-p224总结&#xff0c;总计 53 页。 一、技术总结 1.Context-Free Grammar(CFG) 2.parse tree (1)定义 p183&#xff0c;But perhaps more importantly, the tree, known as a “parse tree”, when used in a …

C语言基础入门案例(1)

目录 第一题&#xff1a;实现大衍数列的打印 第二题&#xff1a;生成所有由1、2、3、4组成的互不相同且无重复数字的三位数&#xff0c;并计算总数 第三题&#xff1a;整数加法计算器 第四题&#xff1a;实现一个范围累加和函数 第五题&#xff1a;编写一个函数计算整数的阶…

Vue3基础笔记(3)高级绑定

一.Class绑定 数据绑定的一个常见需求场景师操纵元素的CSS class列表&#xff0c;因为class是attribute&#xff0c;我们可以和其他attribute一样使用v-bind将他们和动态的字符串绑定&#xff0c;但是在处理较为复杂的绑定时&#xff0c;拼接字符串容易出现错误。因此Vue专门为…

ZJJ-2A直流绝缘监视继电器额定电流3.1mA额定电压110VDCJOSEF约瑟

系列型号 JJJ-1绝缘监视继电器&#xff1b; ZJJ-1/A绝缘监视继电器&#xff1b; ZJJ-1A绝缘监视继电器&#xff1b; ZJJ-2型直流绝缘监视继电器 ZJJ-2直流绝缘监视继电器&#xff1b; ZJJ-2B直流绝缘监视继电器&#xff1b; ZJJ-2AC直流绝缘监视继电器&#xff1b; 用途…

【基础物理实验】【AFM虚拟实验】基于AFM的物质表面微观结构及力学性质表征仿真实验(上)【北京航空航天大学】

基于AFM的物质表面微观结构及力学性质表征仿真实验 说明&#xff1a; 本次实验为本科生《基础物理实验》课程中的虚拟实验部分&#xff0c;在虚拟实验平台中进行。 一、实验目的&#xff1a; 1. 掌握AFM的基本成像原理及系统结构&#xff1b; 2. 掌握AFM的基本操作技巧及操…