性能分析

为了执行一些测试，你需要配置你的环境。那么，让我们开始准备代码，以便使用相同的输入数组运行各种排序算法。

你还记得本章中介绍的每个实现都涉及Sort方法，只接受一个参数（即a数组）吗？现在，你可以利用这个假设，创建一个名为AbstractSort的抽象类，要求你在继承这个类时实现这个方法。

抽象类的代码如下：

那么，你需要根据以下模板为每种排序算法（如选择排序或堆排序）准备一个单独的类：

由于所有代表排序算法的类都派生自基础抽象类（AbstractSort），你可以轻松创建一个包含它们实例的列表：

代码中最有趣的部分展示如下：

在这里，你使用一个for循环来选择合适的n值，n是用于排序的输入数组的长度。你从一个元素数量为零的数组开始（n = 0），一直到数十万的元素（n = 100000），每次迭代增加10000的大小。n的值将是0, 10000, 20000, 30000，一直到100000。

在每次迭代中，你都会创建一个新的列表实例（毫秒）。它的每个元素存储一个包含两个元素的元组，即排序算法类的类型（Type）和执行耗时（毫秒）。然后，你使用另一个for循环来执行这样的测试5次。在每次测试中，通过调用GetRandomArray函数获取一个给定大小的随机数组（array），该数组将用作每个测试的模板。接下来，你声明并初始化输入数组（input）。

接下来的部分涉及一个foreach循环，它遍历所有从AbstractSort派生的类的实例。对于每一个实例，你通过从array复制元素到input来创建输入数组。然后，你启动计时器并调用Sort方法。一旦它运行完成，你就停止计时器并将结果添加到毫秒列表中。

代码的最后一部分与计算每种排序算法的平均结果及其在控制台中的展示有关。为此，你使用了一些扩展方法，如GroupBy、Select和Average，以及一个foreach循环。

之前提到的GetRandomArray方法，让我们来看一下它：

它使用Random类来获取一个在<-100,000, 100,000)范围内的随机整数值。

整个数组被填充了这样的随机值。

此时，你的环境已经准备就绪，你可以进行测试了！所以，让我们运行代码并查看结果。我收到了以下值：

除了桌子和它的数据，让我们来看看图表：

如你所见，冒泡排序得到的结果最差，其次是插入排序和选择排序算法。对于包含100,000个元素的数组，它们分别需要近33秒（冒泡排序）、近14秒（插入排序）和超过5秒（选择排序）。与归并排序、Shell排序、快速排序和堆排序的结果相比，这些值看起来非常高。这些算法只需要12到28毫秒！这看起来令人惊讶吗？如果你记得时间复杂度，那么这并不应该令人惊讶。让我们回忆一下提到的算法的平均时间复杂度：

? O(n^2): 选择排序、插入排序和冒泡排序

? O(n log(n)): 归并排序、希尔排序、快速排序和堆排序

哦，看来这样的时间复杂度确实很重要呢！ ;-) 如果你之前有任何疑问，

现在是时候关注你在应用程序中使用的算法了。你应该仔细选择它们，并优化解决方案以处理需要处理的各种数量的数据。

不要忘记性能

维护性能对于排序很重要，但同样重要的是，对于你在移动应用程序、网络应用程序、API和长时间运行的后台服务中执行的所有操作也是如此。让我们尝试编写高效的代码，并通过满足功能要求以及照顾到非功能性的要求（如与性能相关的）来测试它。

在上一个图表中，你几乎看不到任何关于时间复杂度为O(n log(n))的算法的数据，所以让我们准备另一组测试。现在，你可以只选择这些算法，并将n的最大值增加到一百万！你可以在下面的图表中看到我的结果:

这里存在一些差异，特别是快速排序与其他排序算法之间，即希尔排序、归并排序和堆排序。然而，这些变化只有在相当大的输入规模下才可见，并且可能是由实现细节引起的。所有具有O(n log(n))时间复杂度的排序算法都是排序的好方法，并且可以处理各种数量的数据。同样值得注意的是，这些结果是在我的设备上获得的，所以你可能会得到不同的结果。但是，收到的经过的毫秒数之间的关系应该是连贯的。

总结

数组是开发各种应用程序时最常用的数据结构之一，例如移动、网页或分布式应用程序。然而，这个话题并不像看起来那么简单，因为即使是数组也可以分为几个变体，即一维和多维，如二维和三维，以及所谓的锯齿数组，也称为数组的数组。

在谈论数组时，不要忘记排序算法，这是与这种数据结构一起使用的最流行的算法之一。存在许多不同的排序算法，它们在概念、应用、实现细节和性能结果上都有所不同。在本章中，你了解了七种不同的排序算法，即选择排序、插入排序、冒泡排序、归并排序、希尔排序、快速排序和堆排序。每种算法都进行了描述，通过图形进行了可视化，并用C#代码编写。

在本章的最后，你看到了时间复杂度的重要性以及它对使用具有不同计算复杂度的算法（如O(n^2)和O(n log(n))）时性能结果的影响有多大。你学会了如何准备一个简单的环境进行性能测试并运行它们以获得结果。这些结果后来在表格中以及图表中展示，并附有解释。

你准备好学习其他数据结构了吗？如果是的话，请继续阅读下一章，你将学习到各种列表的变体，包括简单列表、泛型列表、排序列表，以及单链表、双链表和循环链表。你将看到它们的实现以及如何在现实世界中使用它们的几个例子。