搜索
首页web前端js教程学习快速排序算法

快速排序是最有效的算法之一,它使用分治技术对数组进行排序。

快速排序的工作原理

快速排序的主要思想是帮助一次将一个元素移动到未排序数组中的正确位置。这个元素称为枢轴。

:

时,枢轴元素位于正确位置
  1. 其左侧的所有元素都较小
  2. 其右侧的所有元素都较大

左边或右边的数字是否已排序并不重要。重要的是枢轴位于数组中的正确位置。

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

所有这些都是枢轴为 23 的数组的有效输出。

找到枢轴的正确位置

快速排序帮助枢轴找到其在数组中的正确位置。例如,如果枢轴位于数组的开头但不是最小的数字,则快速排序确定需要移动 5 步才能为数组中的 5 个较小元素腾出空间 - 假设有 5 个这样的元素数字。

假设我们有数组:[10, 4, 15, 6, 23, 40, 1, 17, 7, 8],10 是主元:

Learning the Quick Sort Algorithm

此时

  • 数字 10 不知道它是否处于正确的位置,也不知道它需要移动多少步才能到达那里。快速排序首先将 10 与下一个索引处的值进行比较。
  • 当发现 4 较小时,快速排序记录枢轴需要向前移动一步才能让 4 出现在它之前。
  • 因此 numberOfStepsToMove 增加 1

Learning the Quick Sort Algorithm

接下来,在索引 2 处,值为 15,大于 10。由于不需要调整,快速排序保持步数不变并移至数组中的下一个元素。

Learning the Quick Sort Algorithm

在下一个索引处,值为 6,小于 10。快速排序 将步数增加到 2,因为主元现在需要为两个较小的数字腾出空间:4 和 6 .

Learning the Quick Sort Algorithm

现在,6 需要与 15 交换,以保持较小的数字在数组的左侧彼此相邻。我们根据当前索引和 numberOfStepsToMove 值交换数字。

Learning the Quick Sort Algorithm

快速排序继续循环遍历数组,根据小于主元的数字数量增加 numberOfStepsToMove。这有助于确定枢轴需要移动多远才能到达正确位置。

numberOfStepsToMove 不会改变 23 或 40,因为这两个值都大于基准值,并且在数组中不应位于基准值之前:

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

现在,当快速排序循环到索引 6 处的值 1 时,numberOfStepsToMove 增加到 3 并交换索引 3 处的数字:

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

快速排序继续此过程,直到到达数组末尾:

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

现在我们已经到达了数组的末尾,我们知道有 5 个数字小于 10。因此,主元 (10) 必须向前移动 5 步到其正确位置,该位置大于所有数字前面的数字。

Learning the Quick Sort Algorithm

让我们看看代码中的样子:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

现在我们有了一个函数来帮助我们找到放置枢轴的位置,让我们看看 Qucik Sort 如何将数组划分为更小的数组,并利用 getNumberOfStepsToMove 函数来放置所有数组元素。

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i 



<p>快速排序利用递归将数组有效地划分为更小的子数组,确保通过将元素与主元进行比较来对元素进行排序。<br>
</p>

<pre class="brush:php;toolbar:false">function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}
  • 算法递归地对包含小于主元的元素的左子数组进行排序。
  • 当子数组有一个或零个元素时,递归停止,因为它已经排序。

Learning the Quick Sort Algorithm

现在我们需要对数组的右侧执行相同的过程:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Learning the Quick Sort Algorithm

在此示例中,右侧已经排序,但算法不知道这一点,如果没有排序,它也会被排序。

以上是学习快速排序算法的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
JavaScript在行动中:现实世界中的示例和项目JavaScript在行动中:现实世界中的示例和项目Apr 19, 2025 am 12:13 AM

JavaScript在现实世界中的应用包括前端和后端开发。1)通过构建TODO列表应用展示前端应用,涉及DOM操作和事件处理。2)通过Node.js和Express构建RESTfulAPI展示后端应用。

JavaScript和Web:核心功能和用例JavaScript和Web:核心功能和用例Apr 18, 2025 am 12:19 AM

JavaScript在Web开发中的主要用途包括客户端交互、表单验证和异步通信。1)通过DOM操作实现动态内容更新和用户交互;2)在用户提交数据前进行客户端验证,提高用户体验;3)通过AJAX技术实现与服务器的无刷新通信。

了解JavaScript引擎:实施详细信息了解JavaScript引擎:实施详细信息Apr 17, 2025 am 12:05 AM

理解JavaScript引擎内部工作原理对开发者重要,因为它能帮助编写更高效的代码并理解性能瓶颈和优化策略。1)引擎的工作流程包括解析、编译和执行三个阶段;2)执行过程中,引擎会进行动态优化,如内联缓存和隐藏类;3)最佳实践包括避免全局变量、优化循环、使用const和let,以及避免过度使用闭包。

Python vs. JavaScript:学习曲线和易用性Python vs. JavaScript:学习曲线和易用性Apr 16, 2025 am 12:12 AM

Python更适合初学者,学习曲线平缓,语法简洁;JavaScript适合前端开发,学习曲线较陡,语法灵活。1.Python语法直观,适用于数据科学和后端开发。2.JavaScript灵活,广泛用于前端和服务器端编程。

Python vs. JavaScript:社区,图书馆和资源Python vs. JavaScript:社区,图书馆和资源Apr 15, 2025 am 12:16 AM

Python和JavaScript在社区、库和资源方面的对比各有优劣。1)Python社区友好,适合初学者,但前端开发资源不如JavaScript丰富。2)Python在数据科学和机器学习库方面强大,JavaScript则在前端开发库和框架上更胜一筹。3)两者的学习资源都丰富,但Python适合从官方文档开始,JavaScript则以MDNWebDocs为佳。选择应基于项目需求和个人兴趣。

从C/C到JavaScript:所有工作方式从C/C到JavaScript:所有工作方式Apr 14, 2025 am 12:05 AM

从C/C 转向JavaScript需要适应动态类型、垃圾回收和异步编程等特点。1)C/C 是静态类型语言,需手动管理内存,而JavaScript是动态类型,垃圾回收自动处理。2)C/C 需编译成机器码,JavaScript则为解释型语言。3)JavaScript引入闭包、原型链和Promise等概念,增强了灵活性和异步编程能力。

JavaScript引擎:比较实施JavaScript引擎:比较实施Apr 13, 2025 am 12:05 AM

不同JavaScript引擎在解析和执行JavaScript代码时,效果会有所不同,因为每个引擎的实现原理和优化策略各有差异。1.词法分析:将源码转换为词法单元。2.语法分析:生成抽象语法树。3.优化和编译:通过JIT编译器生成机器码。4.执行:运行机器码。V8引擎通过即时编译和隐藏类优化,SpiderMonkey使用类型推断系统,导致在相同代码上的性能表现不同。

超越浏览器:现实世界中的JavaScript超越浏览器:现实世界中的JavaScriptApr 12, 2025 am 12:06 AM

JavaScript在现实世界中的应用包括服务器端编程、移动应用开发和物联网控制:1.通过Node.js实现服务器端编程,适用于高并发请求处理。2.通过ReactNative进行移动应用开发,支持跨平台部署。3.通过Johnny-Five库用于物联网设备控制,适用于硬件交互。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热工具

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。