如果你是一名编程老师，你必须选择一种排序算法来教你的学生，你会选择哪一种？我只要求一个，因为我只想介绍排序的概念。应该是冒泡排序还是选择排序？我注意到这两个是最常教的。是否有另一种类型的排序可以以更容易理解的方式解释排序？
Johan
问问题
8572 次
33 回答
31
我不确定我能不能成为一名计算机科学老师，只教一种排序算法。
至少应向学生教授每种主要排序类型中的至少一种，即交换排序、选择排序、插入排序和合并排序。除了这些类型中的一种之外，我还将介绍属于分区排序标题下的快速排序。
至于我将涵盖的每种类型的具体种类：
- 冒泡排序作为交换排序类别的一个例子，因为它是最简单的排序类型之一，而且他们可能已经看到或偶然发现了一种。如果他们必须为简单的事情自己动手，这也是他们最有可能最常使用的那种，所以他们理解它是有意义的。
- 来自选择排序类别的堆排序。这可能是仅次于快速排序的最令人困惑的排序，但一旦他们了解它如何设置他们以理解快速排序算法。
- 将介绍作为插入排序类别示例的插入排序，因为它也是一种简单的排序，可以大量使用。因为他们可能会遇到需要将两个列表合并在一起的情况，所以知道这个是有道理的。
- 合并排序在某种程度上是一种专门的排序，因此您不会经常看到它，但它非常擅长它的作用，并且在您需要对以零碎方式获得的数据进行排序的情况下仍然有用。
如果我必须将事情缩小到我可以教的一种，但我有时间确保学生准确理解发生了什么，那么我会教 Quicksort。虽然不容易掌握，但绝大多数框架都将它用于排序算法，因此了解它的工作原理对于使用该框架进行开发很有用。此外，如果有人能够理解快速排序，那么他们很可能应该能够自己学习冒泡排序和插入排序。
于 2008-10-17T13:25:08.010 回答
23
让你的学生决定。
在介绍任何排序算法之前，先给每个学生一些扑克牌，大概 10 张左右。然后让他们对卡片进行分类。让他们写下他们采取的步骤，这基本上就是他们的算法。他们可能会发现插入或选择排序。你也可以让他们估计如果他们有 100 或 1000 张卡片，他们的排序会采取多少步，这很好地引导到大 O 符号。
PS - 有人认为他们会发现冒泡排序吗？
于 2009-12-03T06:32:16.587 回答
21
不管教的是什么排序算法，如果学生不学习bogosort，他们就会错失良机，而且老师正在失去吸引观众的明显方式:)
于 2008-10-17T13:14:59.140 回答
14
如果你想教排序，那么冒泡排序可能是最容易理解的。如果你想教授排序算法，那么你真的应该教授快速排序、归并排序、插入排序，甚至可能是堆排序，以便学生能够感受各种排序方法之间的权衡。
于 2008-10-17T13:14:47.360 回答
6
我将从显示插入排序开始。每个整理过牌的人（基本上是每个人）都知道这种分类。另外，它没有冒泡排序的糟糕表现。
于 2008-10-17T13:32:19.103 回答
5
我首先学习了冒泡排序——我认为如果你只做一个，你可能需要做一个 O(n^2) 算法，因为它们更容易理解。
有很多排序可视化工具可以帮助快速显示比较：
于 2008-10-17T13:18:00.770 回答
3
我会在一般排序算法上建议选择和合并排序。与他们的朋友相比，两者都相对直截了当。但是如果你只能教一个并且人们可以处理它，我会选择合并排序。因为归并排序是高效、稳定的，并且教授了几个重要的概念（合并、分治）。
选择排序：
找到最小值/最大值并将其放在适当的位置，然后在列表的其余部分上再次执行...这非常直观。对我来说，选择甚至比冒泡排序更直观。你可能会在很短的时间内教这个。而且实现这个的人会有成就感……虽然Bubble和Insertion可以提前退出，不会在排序列表上浪费时间。选择可能是最容易做到的。插入可能是最难实现的。
MergeSort：
这将教授如何合并（这很重要，因为通过将两个排序列表合并在一起可以获得大量加速）以及如何将问题划分为更小的子问题（对于处理层次结构和也很重要）用于快速排序）。快速排序虽然更快，但更难理解。您需要两个扫描变量，一个数据透视项目等......合并更直接，合并对于排序以外的事情会派上用场（比如将两个在字段上排序的记录连接在一起）......
合并的基本概念是直观的。从排序列表中取出较小的项目并将其放入最终列表中。划分归并排序问题也很直观。
合并排序（前半部分） 合并排序（后半部分）
合并（前半部分，后半部分）
如果您只能教授一种并且必须快速完成（或者观众根本不感兴趣），我会倾向于选择，因为这更难并且可以快速教授选择。但如果观众更有动力，那么我会做 Merge，因为它教了很多额外的基本概念。
在更有效的排序中，这种排序比快速排序和堆排序要容易得多。尽管快速排序在实践中可能是最快的（只要你有足够的内存）并且堆可能能够对最大的列表进行排序（如果非递归实现）。
桶排序：
我会谈到这一点，因为它也很直观并且代表了另一种类型的排序算法。在许多情况下，这是合适的，而且 O(n) 时间非常有吸引力。
计数排序：
它有它的用途。在某些情况下，这是非常有效的......它也相对容易。
于 2008-10-17T15:07:18.023 回答
3
选择排序可能是最容易教授和最容易掌握的排序算法。这也是为什么简单的解决方案并不总是最好的一个很好的例子，这可能会引发对更有趣和更快的排序的讨论，比如合并排序和快速排序。
于 2008-10-17T13:18:25.013 回答
3
我认为排序方法是算法的一个很好的例子。但是，当您比较各种方法时，它只会成为一个很好的例子。如果你只能教一个，我不确定它是否值得。
实际上，我们在某些框架中调用 sort 方法。所以如果你不能有效地教授排序算法，那可能不值得花时间。
再也没有人需要编写排序方法了，但它仍然是算法影响的一个很好的例子。
于 2008-10-17T13:18:30.443 回答
2
我会教“调用框架”排序。
教授和学习这种方法会很有效。学生在实施这种分类时会有很高的成功率和很低的错误率。
编辑：关于我的单分类课程的质量，这个答案有很多批评性评论。这些批评适用于这个问题的任何答案，即——“如果你是一名编程老师，你必须选择一种排序算法来教你的学生会是哪一种？”
于 2008-10-17T13:16:45.673 回答
2
这将是基数排序。因为它非常简单，但并不明显。像这样的东西只能教。
于 2008-10-17T14:58:27.823 回答
2
嗯...排序算法确实是一种直观、具体的方法，可以教授一些关于大 O 表示法、优化、常识和计算机科学的好课程，也许是“冒泡排序”+“选择排序”+“合并排序”方法可能有用，用于比较。我认为最直观（在许多情况下也是有效的）是选择排序。
于 2008-10-17T13:19:01.707 回答
2
我认为只教一种是残废的。请记住，对于 Small n 来说，一切都很快，因此在教授排序方面，这不是性能问题，而是理解算法。
我认为介绍应该是冒泡排序来介绍这个概念，但至少要引入另一种排序来让学生思考执行任务的其他方法。确保他们了解性能和代码复杂性之间的权衡，并确保针对不同情况有不同的工具。
于 2008-10-17T13:54:16.377 回答
1
冒泡排序是经典，很容易理解它为什么起作用。
但除非这是一门非常介绍性的课程，否则它应该包括对其他排序算法的概述，因为这是迄今为止展示算法设计中所涉及的权衡和解释最佳情况、最坏情况和平均行为（运行时和内存）的最佳方式）。
于 2008-10-17T13:17:03.457 回答
1
如果你想教授排序的概念，那么我相信你必须至少教授两种不同的排序方式——否则学生会认为排序只是你教给他们的一种方式。
我认为学生将从学习经典的 O(n^2) 算法（最好是插入或选择排序，但请不要冒泡排序，它没有理由在实际应用中使用）中获得最大价值，以及分治法，O(nlogn) 算法，例如快速排序或归并排序。
如果您担心这些课程太难教您的学生，请查看Computer Science Unplugged中的这些活动，这些活动是为小学生设计的。
于 2008-10-22T21:51:40.543 回答
1
让每个人都带上一副牌，然后挑出一套花色。分成两人一组。一个人将 13 张牌洗牌，然后将它们面朝下连续放置。合作伙伴可以指向其中两张牌。另一个把它们捡起来，看着它们，要么说“按顺序”，要么“按顺序”，然后对方可以告诉他交换它们，然后再放下它们（面朝下）
合作伙伴的工作是按顺序对卡片进行分类（您需要预先定义）。
当伙伴认为他们已排序时，他会说“停止”。另一个将牌面朝上，然后他们过牌。
完成后，讨论对每个人都有效的方法。然后说说BUBBLE SORT vs SELECTION sort
然后谈谈快速排序。
让他们用他们的纸牌试一试。
于 2008-10-17T16:16:41.580 回答
1
我认为选择排序是最容易理解的，而 IMO 最好是引入排序。
我认为不教他们至少一种 O(nlog(n)) 排序算法以及对大 O 表示法的解释是愚蠢的。
于 2008-10-17T13:21:16.787 回答
0
我参加过的关于算法的最佳讲座将所有算法演示为通过 Java 小程序绘制的条形图。然后，您还可以看到排序模式以及 O(N) 特征......
教泡泡，因为它非常简单，其余的可能会显示为动画？
于 2008-10-17T13:18:11.770 回答
0
应该首先要求他们实现自己的排序算法 - 从头开始，而不事先参考任何现有算法。这样做将教会他们排序方式，而不是告诉他们一种算法，他们不知道它是如何派生的。
于 2009-01-07T14:54:41.927 回答
0
我会比较和对比一个 o(n-squared)，比如选择排序和 ao(n log n) 排序，比如快速排序。
但是，如果他们不是计算机科学人员并且不一定打算成为，那么只需显示一种易于理解的类型，例如选择或气泡。
于 2008-10-17T14:47:14.367 回答
0
上周我刚刚和我的孩子一起做了这个，我让他想出他们自己的排序算法，并询问使用他的方法对一副纸牌进行排序需要多长时间。然后我向他展示了Bubble Sort（最容易向孩子解释）“这是一个泡沫！” 又让他数步数。他意识到这更容易，更快捷。
然后如果你想你可以教更高级的（快速排序是最令人惊讶的），理想情况下你应该至少教三个不同的（不是相同的变化）
于 2008-10-17T16:08:49.193 回答
0
我认为 30 年前制作的电影Sorting Out Sorting仍然是一个很好的指导帮助，可以更好地理解排序算法。这是 12 倍速版本
于 2009-12-03T06:47:13.703 回答
0
冒泡排序是初学者最容易理解的一种，它也是一个很好的例子，说明了为什么简单的解决方案可能很昂贵。可能是一种进入渐近复杂性和大 O 符号的好方法吗？
于 2008-10-17T13:19:03.920 回答
0
如果我只能选择一个，我会教冒泡排序，因为它更容易掌握（我认为）。然而，我从研究各种排序算法中得到的最有价值的东西是，有不止一种方法可以做到这一点（最终导致我使用 Perl，但这是另一回事），每种方法都有优点和缺点。因此，学习单一的排序算法可能会错过整个事情的关键方面。
于 2008-10-17T13:19:51.890 回答
0
快速排序绝对是另一种非常易于理解的排序算法，实现它很容易。它有就地和“不合时宜”的版本，想想就很有趣。而且很快。
至少对你来说够快了，老头。
于 2008-10-17T13:20:53.450 回答
0
呃，你应该给他们一个 O(n^2) 和一个 O(n log n) 排序。泡沫和堆将是我的选择。
于 2008-10-17T13:25:09.197 回答
0
无论您选择哪种实际算法，我都建议您展示两种算法（而不是一种）并解释它们所做的权衡（在内存、执行速度等方面）。
然后你应该坚持认为，没有理想的排序算法可以盲目地应用于任何任务。然而，也有很好的候选人。在这一点上，向他们展示快速排序和自省排序（作为家庭作业）并认为您的任务已完成 :)
于 2008-10-17T13:27:52.280 回答
0
请记住，您的学生可能永远不必自己编写排序代码，所以问题真的应该由“学习这种算法的价值是什么？”来决定。而不是“这个算法是做什么的？”
换句话说，你的学生应该学习各种不同的算法——它们是否用于排序、搜索、压缩等在很大程度上是无关紧要的。
于 2008-10-17T13:31:34.753 回答
0
一旦学生学会了快速排序和堆排序，IntroSort 也是一种很好的教学算法。IntroSort（Introspective sort 的缩写）从 QuickSort 开始，如果递归深度超过基于被排序元素数量的对数的级别，则切换到 HeapSort。
总的来说，你得到了最好的快速和堆排序世界和O ( n log n ) 的最坏情况运行时间。
维基百科上的介绍排序
于 2008-10-17T13:42:14.670 回答
0
如果您最终只能教授一种算法，我认为选择排序更容易教授（并实现恕我直言）作为 BubbleSort 。它可能效率极低，但每个人都会明白它的概念，每个有一点编程知识的人都可以阅读它的代码，并且有一件事使 SelectionSort 在所有排序算法中相当独特：它只需要 n - 1 次交换即可获得 n 的列表条目 :-) 不仅它不需要进行超过 n - 1 次交换，它实际上需要恰好 n - 1 次交换。执行的交换次数是 100% 确定的，甚至在开始之前就知道。我认为这不适用于任何其他就地排序算法（尽管人们可以在评论中自由地纠正我）。
否则我会投票给 BubbleSort 和 SelectionSort，它们最容易理解并展示了排序的简单方法（这些很简单，学生实际上可能在没有听说过任何排序算法的情况下提出这些解决方案）有时不是很有效。相比之下，我将展示 QuickSort 和 MergeSort，它们是非常好的分而治之的算法，而且速度也非常快。
我不会使用的算法是 ShellSort、RadixSort、HeapSort 和 BucketSort，因为它们的概念更难理解。它们也相当特殊（通常仅在对某种数据进行排序或对排序有一定限制时才使用它们）。
你可能会提到 ShellSort 的小妹妹 InsertionSort（它基本上是一种步长最终达到 1 的 shell 排序），但这只是因为许多 QuickSort 实现使用 InesrtionSort 作为后备排序，一旦递归变得太深（或递归排序的剩余数据集太小了）......但在这里它开始变得非常复杂，你不应该让它太复杂。
于 2008-10-21T22:28:01.610 回答
0
不要忘记意大利面条排序......为量子计算做好准备:-)
于 2010-06-07T14:39:03.437 回答
0
从 insertSort 开始，然后继续使用 mergeSort、quickSort 和 heapSort，避免使用 bubbleSort（有大量研究表明 insertSort 并不难理解/实现，并且与 bubbleSort 相比，它具有实际用途（更快比合并排序小的数组，例如）。
于 2010-01-29T11:38:27.300 回答
0
我会避免谈论冒泡排序，因为虽然它有效，但它在理论上并不是很优雅。此外，它在实践中从未在任何地方使用过。有一大堆算法依赖于选择排序（例如就地合并）或插入排序（如疯狂的快速内引排序），所以这些可能是很好的开始。我个人最喜欢插入排序，因为从教学的角度来看，它是一座金矿。最坏情况下为 O(n^2)，最好情况下为 O(n)，因此为讨论最坏情况/最佳情况分析提供了一个很好的测试平台。它是一种就地排序，因此您可以使用它来讨论原位排序与非原位排序，并且可以通过谈论它所体现的基本思想将其概括为堆排序。
于 2010-11-09T21:08:24.937 回答