搜索
首页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中替换字符串字符Mar 11, 2025 am 12:07 AM

JavaScript字符串替换方法详解及常见问题解答 本文将探讨两种在JavaScript中替换字符串字符的方法:在JavaScript代码内部替换和在网页HTML内部替换。 在JavaScript代码内部替换字符串 最直接的方法是使用replace()方法: str = str.replace("find","replace"); 该方法仅替换第一个匹配项。要替换所有匹配项,需使用正则表达式并添加全局标志g: str = str.replace(/fi

自定义Google搜索API设置教程自定义Google搜索API设置教程Mar 04, 2025 am 01:06 AM

本教程向您展示了如何将自定义的Google搜索API集成到您的博客或网站中,提供了比标准WordPress主题搜索功能更精致的搜索体验。 令人惊讶的是简单!您将能够将搜索限制为Y

示例颜色json文件示例颜色json文件Mar 03, 2025 am 12:35 AM

本文系列在2017年中期进行了最新信息和新示例。 在此JSON示例中,我们将研究如何使用JSON格式将简单值存储在文件中。 使用键值对符号,我们可以存储任何类型的

10个jQuery语法荧光笔10个jQuery语法荧光笔Mar 02, 2025 am 12:32 AM

增强您的代码演示:开发人员的10个语法荧光笔 在您的网站或博客上共享代码片段是开发人员的常见实践。 选择合适的语法荧光笔可以显着提高可读性和视觉吸引力。 t

构建您自己的Ajax Web应用程序构建您自己的Ajax Web应用程序Mar 09, 2025 am 12:11 AM

因此,在这里,您准备好了解所有称为Ajax的东西。但是,到底是什么? AJAX一词是指用于创建动态,交互式Web内容的一系列宽松的技术。 Ajax一词,最初由Jesse J创造

8令人惊叹的jQuery页面布局插件8令人惊叹的jQuery页面布局插件Mar 06, 2025 am 12:48 AM

利用轻松的网页布局:8个基本插件 jQuery大大简化了网页布局。 本文重点介绍了简化该过程的八个功能强大的JQuery插件,对于手动网站创建特别有用

10 JavaScript和JQuery MVC教程10 JavaScript和JQuery MVC教程Mar 02, 2025 am 01:16 AM

本文介绍了关于JavaScript和JQuery模型视图控制器(MVC)框架的10多个教程的精选选择,非常适合在新的一年中提高您的网络开发技能。 这些教程涵盖了来自Foundatio的一系列主题

什么是这个&#x27;在JavaScript?什么是这个&#x27;在JavaScript?Mar 04, 2025 am 01:15 AM

核心要点 JavaScript 中的 this 通常指代“拥有”该方法的对象,但具体取决于函数的调用方式。 没有当前对象时,this 指代全局对象。在 Web 浏览器中,它由 window 表示。 调用函数时,this 保持全局对象;但调用对象构造函数或其任何方法时,this 指代对象的实例。 可以使用 call()、apply() 和 bind() 等方法更改 this 的上下文。这些方法使用给定的 this 值和参数调用函数。 JavaScript 是一门优秀的编程语言。几年前,这句话可

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无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具

VSCode Windows 64位 下载

VSCode Windows 64位 下载

微软推出的免费、功能强大的一款IDE编辑器

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器