Python 中的基准排序算法

(对于基准结果和代码向文章底部滚动)

排序问题是不需要介绍的问题,它是您获得长度为 n 的整数组,其元素按未分类顺序排列,输出应与按排序顺序排列的元素相同的阵列 A(通常最少到最大)。
有许多方法可以解决此lem,并且创建许多算法的唯一目的是对数字进行排序。现在,你可能会认为这个问题是微不足道的,从某种意义上说,它毕竟是一个人可以看看设置{5,2,1,6,3},并很容易地将其分类成{1,2,3,5,6}。虽然这是真的,但当阵列大小开始变大时,真正的问题开始出现。
这就是这些算法的用武之地,它们将数组作为输入,并在上面执行一些操作,并整理出阵列。这个解释可能非常简单,为了帮助理解它,我会举一个例子,说明一个这样的算法是如何工作的。
假设我们有阵列 A= [6、 4、 0、 3、 2], 我们要做的第一件事就是找到阵列中最小的元素, 并将其移动到一个开始。因此,最小的元素是 0,因此我们将交换 0 和 6 以获得 A = {0、4、6、3、2},并且您已经可以看到,阵列在开头部分排序为 0。然后,我们在 n-1 的阵列大小上重复此过程,因此我们第一次查看整个阵列,下一次,我们将查看 4 到 2(包括)的阵列,而不是查看 0,因为我们知道它位于其排序位置。
我向您描述的算法称为”选择”,因为它选择阵列中的最低元素并将其放在数组的开头。与选择排序一样,还存在许多其他具有相同目的的排序算法。
其他排序算法的工作方式类似,我会给它们的快速破败,只是为了让你可以掌握它们是如何运作的,但如果你想要一个更好和更全面的解释,GeeksforGeeks是一个伟大的来源。
第一个算法是快速排序,它完全按照名称的含义,快速对阵列进行排序。它通过使用枢轴元素(阵列中的任何元素)工作,并将所有元素置于其左侧,将所有元素置于右侧。如果您一遍又一遍地这样做,则对阵列进行排序。
接下来,我们有 Mergesort,它通过将阵列拆分为左右两部分来工作,并一直这样做,直到左阵或右阵列的大小为 1。然后,它合并了阵列的左右部分,并有效地对它们进行排序。然后,此合并过程一直持续到整个阵列排序。
现在,如果前两种算法对您没有意义,不要担心,因为接下来的 2 算法很容易理解,但我只想告诉你一点关于前 2 个算法所依赖的概念,这个概念称为递归,它涉及通过将问题划分为较小的问题并解决这些问题来解决问题。然后使用这些子问题解决方案来解决原始问题。换句话说,它是在定义一个函数本身。了解更多信息的优秀来源是极客吉克斯和维基百科,以及一些YouTube视频。
下一个算法称为气泡,它的工作原理如下,你选择在阵列中的第一个元素,然后元素后,它(索引i和i +1)。然后,你比较两者,如果第一个小于第二个,你交换他们。然后,您对第二个和第三个元素也这样做,直到您到达最后两个元素。此时,我们有一个部分排序的数组,但我们需要重复此过程,直到我们不必再进行交换,此时算法已完成。
最后,我们有插入项,它首先查看阵列中的第二个元素并将其与第一个元素进行比较,如果它小于它,则将第二个元素放在阵列的开头。然后,您查看数组中的第三个元素,并将其与第二个元素进行比较,如果它较少,则将其放在数组的开头。重复此过程,直到您到达阵列的末尾,然后完成!此算法之所以有效,是因为它对您正在查看的元素背后的所有内容进行排序,而最后一种算法是”选择”,我们已经查看了这些算法。
(现在对于那些一直在等待结果的人)
现在,您知道我已实施哪些算法以及它们如何工作,您应该能够了解基准的结果。唯一需要记住的是,当算法在一定时间内无法完成执行时,其运行时间为 10 秒。

发表评论

后才能评论