在JavaScript中如何选择高效且合适的排序算法

作者 : IT 大叔 本文共2399个字,预计阅读时间需要6分钟 发布时间: 2020-10-15

在计算机科学中,很少有工具像搜索算法那样经常使用。程序员和工程师每天都依靠它们筛选数据,并且几乎以一种或另一种方式将它们构建到几乎每种现代编程语言中。

尽管使用语言的内置搜索功能可以完成大多数日常工作,但重要的是要了解幕后工作情况,不同的搜索算法实际上在做什么以及为什么它们按照自己的方式工作。尽管它可能不会经常出现,但总是有机会要求您在技术面试环境中实施或解释搜索算法,这正是本文为您准备的内容!

今天,我们将研究选择排序,这是计算机科学中的另一种基本搜索算法。

什么是选择排序?

维基百科选择排序页面描述了这样的算法:

选择排序是就地比较排序算法。
...
该算法将输入列表分为两部分:从左到右在列表的前部(左侧)建立的项目排序子列表,以及占据列表其余部分的其余未排序项目的子列表。

最初,已排序的子列表为空,未排序的子列表为整个输入列表。该算法通过在未排序的子列表中找到最小(或最大,取决于排序顺序)元素,将其与最左边的未排序元素交换(交换)(按排序顺序排列),并将子列表边界向右移动一个元素来进行。

如果没有可视化效果,这可能会有些混乱,因此以下是一个动画,可以帮助您将其全部透视(我建议您观看几次以了解正在发生的事情):

在JavaScript中如何选择高效且合适的排序算法插图

当我们在初始循环中遍历数组时,我们同时在嵌套循环中使用第二个指针向前推进数组,将每个值与起始值进行比较(从第一个循环的初始索引开始)。较低的值,我们将该新值设置为要与之进行比较的新最低值,然后继续推动。

这样,我们确保每次遍历数组时,总会找到下一个最小值。当我们到达第二个循环的末尾时,我们将最小值与我们的第一个初始索引的值交换,然后进行下一步。

如果我们有兴趣从最高到最低排序,也可以通过搜索最大值以相反的顺序进行。这是你的选择!

有效率吗?

选择排序虽然相对容易理解和实现,但遗憾的是落后于其他排序算法,例如快速排序,堆排序和合并排序

但是,由于选择排序功能就位且不需要辅助内存,因此与其他一些更复杂的算法相比,它确实具有空间优势。

一般而言,尽管选择排序对于作为程序员和计算机科学家了解和理解仍然很重要,但是插入排序可能是一种性能更高的替代方法。

选择排序具有最佳情况最坏情况平均情况下的运行时复杂度O(n ^ 2),这意味着它本质上始终是二次方的。

我们如何实施呢?

这就是乐趣的开始!

由于我们正在JavaScript中实现插入排序,因此我们将使用现代ES6 +语法来处理数组中的交换元素,这将有助于保持我们需要写下的代码行数。

最终的算法如下所示:

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }     
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

让我们逐步分解。


首先,让我们声明函数,其返回值(排序后的数组)以及将要执行所有逻辑的初始循环:

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

  }
  return array;
}

您可能想知道为什么我们要告诉我们的循环停止在array.length - 1而不是正常array.length。这是因为在下一个循环中,我们将从与数组i中的邻居进行比较开始i + 1。这意味着我们需要停止比整个数组长度短的初始循环一个索引。

下一步,我们将宣布,将持有的变量指标我们目前的最小元素minIndex以及第二循环,将尽我们的比较工作:

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {

    }

  }
  return array;
}

如您所见,此循环始于i + 1,将值分配给指针j。该minIndex变量仅设置i为临时度量,因为可能会在此循环中对其进行更改。然而,存在的机会i 实际上是在阵列的未分类的部分次小值,只会留在哪里。

最后但并非最不重要的一点是,我们将在嵌套循环中添加核心比较逻辑,以及在循环完成后交换两个值的ES6交换:

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }     
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

当我们回到本教程的顶部时,“选择排序”的核心思想是选择下一个最小值并一直跟踪它,直到到达数组的末尾,然后将其与已排序的右边界交换。数组的一部分(我们的初始i索引。)

我们在这里通过评估是否这样做array[j] < array[minIndex]。如果是的话,这意味着j应该将其交换到已排序部分的末尾(除非找到更低的值。)我们可以通过设置minIndex = j

该循环完成后,我们将在数组的未排序部分中找到下一个最小值,并将使用ES6[a, b] = [b, a]语法将其交换到正确的位置。

就是这样!我们已经成功地在JavaScript中实现了选择排序算法。hoo!

在这一点上,值得回顾一下动画,它可以直观地表示我们在代码中所做的一切:

在JavaScript中如何选择高效且合适的排序算法插图


如果您走了这么远,非常感谢您的阅读!我希望这对任何学习排序算法,JavaScript或一般编程基础的人来说都是有用的教程。

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 在JavaScript中如何选择高效且合适的排序算法

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论