排序算法

许多算法使用数组来应对广泛的应用。然而，最常见的任务之一是排序数组，以将其中的元素按照正确的顺序排列，无论是升序还是降序。

当然，你也可以对各种类型的数据进行排序，包括数字、字符串，甚至是用户定义类的实例。但是，为了使事情简单一些，这里我们只专注于排序整数值。

想象一下排序算法

在你的日常生活中，你经常从排序过程中受益！例如，你的收件箱按照发送日期降序排列，以便首先显示最新的消息；你的日程表按照事件开始时间升序排列，展示一天的计划；以及你的任务列表按照优先级降序显示，从最重要到最不重要。这还不是全部——在工作中，你按照发行日期对文件进行排序，然后从按到达目的地时间排序的路线中选择一条回家的路；到了晚上，你使用遥控器根据频道的预定义顺序更换电视节目。

排序算法涉及许多方法，并且也是研究的热门主题。有许多种排序类型，包括选择排序、插入排序、冒泡排序、归并排序、Shell排序、快速排序和堆排序。这些将在本章详细解释。然而，这些并不是所有可用的方法。各种类型在性能结果上有所不同，这是你在选择排序实现时应该考虑的最重要的方面之一。本章末尾将分析这个话题，以在这个领域为你提供一些建议。

选择排序

让我们从选择排序开始，这是最简单的排序算法之一。该算法将数组分为两个部分，即已排序和未排序。起初，已排序的部分是空的。在接下来的迭代中，算法在未排序的部分找到最小的元素，并将其与未排序部分的第一个元素交换。因此，已排序的部分增加了一个元素。听起来相当简单，对吧？

为了更好地理解选择排序算法，让我们通过以下迭代来观察一个包含九个元素的数组（-11, 12, -42, 0, 1, 90, 68, 6, 和 -9），如下图所示:

粗体线条用于展示数组中已排序和未排序部分之间的边界。首先（步骤1），边界位于数组的顶部，这意味着已排序部分为空。此时，算法在未排序部分找到最小值（即-42），并将其与这部分的第一个元素（-11）交换。结果如步骤2所示，已排序部分包含一个元素（-42），而未排序部分由八个元素组成。接下来，算法在未排序部分找到-11作为最小值，并将其与未排序部分的第一个元素12交换。结果是，已排序部分包含两个元素，即-42和-11，而未排序部分只剩下七个元素，如步骤3所示。上述步骤重复进行，直到未排序部分只剩下一个元素。最终结果如步骤9所示。

通过这些，你就了解了选择排序算法是如何工作的，但是左侧图表中显示的i和m指示器是什么作用呢？它们与实现该算法时使用的变量有关。所以，现在是时候看看C#语言中的代码了！

实现是在Sort方法中创建的，该方法接受数组a作为参数，并使用选择排序对其进行排序:

void Sort(int[] a)
{
    for (int i = 0; i < a.Length - 1; i++)
    {
        int minIndex = i;
        int minValue = a[i];
        for (int j = i + 1; j < a.Length; j++)
        {
            if (a[j] < minValue)
            {
                minIndex = j;
                minValue = a[j];
            }
        }
        (a[i], a[minIndex]) = (a[minIndex], a[i]);
    }
}

A for循环用于迭代元素，直到未排序部分只剩下一个项目。

因此，循环的迭代次数等于数组长度减一（a.Length - 1）。

在每次迭代中，另一个for循环用于在未排序部分找到最小值（minValue，从i + 1索引到数组末尾），以及存储最小值的索引（minIndex，上图中称为m指示器）。

最后，将未排序部分的最小元素（其索引等于minIndex）与未排序部分的第一个元素（i索引）交换。

就这样！让我们使用以下代码测试选择排序算法的实现：

int[] array = [-11, 12, -42, 0, 1, 90, 68, 6, -9];
Sort(array);
Console.WriteLine(string.Join(" | ", array));

在前面的代码中，声明并初始化了一个数组。然后，调用了Sort方法，并将数组作为参数传递。最后，通过用“|”分隔数组元素来创建字符串值。结果在控制台中显示：

-42 | -11 | -9 | 0 | 1 | 6 | 12 | 68 | 90

由于我们在讨论各种算法，其中一个最重要的主题是计算复杂度，特别是时间复杂度。以选择排序为例，最坏情况和平均时间复杂度都是O(n^2)。为什么呢？让我们通过查看代码来回答这个问题。有两个嵌套的for循环，每个循环都遍历数组中的许多元素，该数组包含n个元素。因此，复杂度被表示为O(n^2)。

关于计算复杂度的一个小提示

在上一章中，你已经学习了计算复杂度。作为快速提醒，有几个变体，例如对于最坏或平均情况。这种复杂度可以解释为根据输入大小（n）需要由算法执行的基本操作数量。时间复杂度可以使用大O表示法来指定——例如，作为O(n)、O(n^2)、O(n log(n))或O(1)。例如，O(n)表示法表明操作数量随着输入大小（n）线性增加。

通过这个，你已经了解了选择排序。如果你对排序的另一种方法感兴趣，继续阅读下一节，那里介绍了插入排序。

插入排序

插入排序是另一种可以简单地对一维数组进行排序的算法。这里，数组被分为两个部分，即已排序和未排序。然而，在开始时，第一个元素被包含在已排序的部分。在每次迭代中，算法从未排序的部分取出第一个元素，并将其放置在已排序部分的适当位置，以保持已排序部分的正确顺序。这样的操作重复进行，直到未排序部分为空。

举个例子，让我们通过一个示例来了解如何使用插入排序对一个包含九个元素的数组（-11, 12, -42, 0, 1, 90, 68, 6, 和 -9）进行排序：

首先，只有一个元素（即-11）位于已排序部分（步骤1）。然后，你从未排序部分取出第一个元素（12）。在这种情况下，这个元素的位置不需要改变，所以已排序部分增加到两个元素，即-11和12。接着，你取-42作为未排序部分的第一个元素，并将其移动到已排序部分的正确位置。为此，你需要执行两次交换操作，如步骤2所示。因此，已排序部分的长度增加到三个元素，即-42、-11和12。在步骤3中，你取0作为未排序部分的第一个元素，并执行一次交换操作将其放置在正确的位置，就在12之前，如步骤4所示。同时，已排序部分的大小增加到四个已排序的元素，即-42、-11、0和12。重复这样的操作，直到未排序部分为空（步骤9）。

插入排序算法的实现代码非常简单：

void Sort(int[] a)
{
    for (int i = 1; i < a.Length; i++)
    {
        int j = i;
        while (j > 0 && a[j] < a[j - 1])
        {
            (a[j], a[j - 1]) = (a[j - 1], a[j]);
            j--;
        }
    }
}

for循环用于遍历未排序部分的所有元素。因此，变量i的初始值设置为1而不是0，因为在开始时未排序部分包含一个元素。在for循环的每次迭代中，都会执行一个while循环，通过交换将数组未排序部分的第一个元素（其索引等于i）移动到排序部分的正确位置。最后，值得一提的是插入排序算法的时间复杂度。与选择排序的情况类似，最坏和平均时间复杂度都是O(n^2)。如果你查看代码，你会看到两个循环（for和while）嵌套在一起，这可能会根据输入大小（n）多次迭代。

冒泡排序

我们将要介绍的第三个排序算法是冒泡排序。它的操作方式非常简单。算法只是遍历数组并比较相邻的元素。如果它们的顺序不正确，就交换它们的位置。听起来很简单，对吧？不幸的是，这个算法效率不高，使用它对大型数据集进行排序可能会导致性能问题。

为了更好地理解算法的工作原理，让我们来看一下下面的图示，它展示了算法在对一个包含九个元素（-11, 12, -42, 0, 1, 90, 68, 6, 和 -9）的一维数组进行排序时是如何操作的：

在每一步中，算法都会比较数组中相邻的两个元素，并在必要时进行交换。

例如，在第一步中，比较了-11和12。它们已经按正确顺序排列，因此没有必要交换这样的元素。在第二步中，比较了接下来的相邻元素（即12和-42）。这次，这些元素没有按正确顺序排列，因此它们被交换了。上述操作会执行很多次。最终，数组被排序，如第72步所示。

这个算法看起来非常简单，但它的实现呢？也简单吗？幸运的是，是的！你只需要使用两个循环，比较相邻的元素，并在必要时进行交换。就这样！让我们来看看下面的代码片段：

void Sort(int[] a)
{
    for (int i = 0; i < a.Length; i++)
    {
        for (int j = 0; j < a.Length - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                (a[j], a[j + 1]) = (a[j + 1], a[j]);
            }
        }
    }
}

这里使用了两个for循环，配合比较和交换操作。如前所述，这个算法效率不高，其应用可能会引起与性能相关的问题，特别是在处理大量数据集时。然而，通过引入一个简单的修改，可以使用一个稍微高效一点的冒泡排序算法版本。它是基于这样一个假设：当在一次遍历数组过程中没有发现任何变化时，应该停止比较。代码如下：

void Sort(int[] a)
{
    for (int i = 0; i < a.Length; i++)
    {
        bool isAnyChange = false;
        for (int j = 0; j < a.Length - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                isAnyChange = true;
                (a[j], a[j + 1]) = (a[j + 1], a[j]);
            }
        }
        if (!isAnyChange) { break; }
    }
}

通过引入这样一个简单的修改，步骤的数量可以减少。在前面的例子中，它从72步减少到了56步。

在继续讨论下一个排序算法之前，值得一提的是冒泡排序算法的时间复杂度。正如你可能已经猜到的，最坏情况和平均情况与选择排序和插入排序算法的情况相同——即O(n^2)。

合并排序

第四种排序算法的操作方式与之前介绍的三种有显著的不同。

这种算法被称为合并排序。该算法递归地将数组分成两半，直到数组中只剩下一个元素，这个元素是已排序的。

然后，算法将已经排序的子数组（从只有一个元素的子数组开始）合并成一个已排序的数组。

最后，整个数组被排序，算法停止运行。

为了更好地理解合并排序算法，让我们通过以下迭代来观察一个包含六个元素的数组（-11, 12, -42, 0, 90, 和 -9）的例子：

首先（步骤1），你有一个未排序的整个数组，将其分为两部分，即（-11, 12, -42）和（0, 90, -9），如步骤2所示。接下来，每个子数组进一步被分割成（-11）、（12, -42）、（0）和（90, -9）。在步骤4中，整个数组被划分为每个只有一个元素的子数组，即（-11）、（12）、（-42）、（0）、（90）和（-9）。然后，你需要将这些子数组合并，并进行排序。因此，在步骤5中，你有三个子数组——即（-11, 12）、（-42, 0）和（-9, 90）。请记住，这些子数组已经是排序好的。在步骤6中，你需要进一步合并并排序它们成（-42, -11, 0, 12）和（-9, 90）。最后，你得到了整个数组排序完成，即（-42, -11, -9, 0, 12, 90）。

这看起来比仅仅阅读算法的文字描述更简单吗？如果是的话，让我们继续进行它的实现：

void Sort(int[] a)
{
    if (a.Length <= 1) { return; }
    int m = a.Length / 2;
    int[] left = GetSubarray(a, 0, m - 1);
    int[] right = GetSubarray(a, m, a.Length - 1);
    Sort(left);
    Sort(right);
    int i = 0, j = 0, k = 0;
    while (i < left.Length && j < right.Length)
    {
        if (left[i] <= right[j]) { a[k] = left[i++]; }
        else { a[k] = right[j++]; }
        k++;
    }
    while (i < left.Length) { a[k++] = left[i++]; }
    while (j < right.Length) { a[k++] = right[j++]; }
}

排序方法被递归地调用，并接受一个需要排序的数组作为参数，命名为a。为了防止这个方法无限递归调用，你必须在开始时指定停止条件。它简单地检查数组的大小是否不大于1。这基于一个假设，即你不能进一步分割只有一个元素的数组，因为它已经是排序好的了。

接下来，你计算中间元素的索引，并将其存储为m的值。在接下来的两行中，你调用了辅助的GetSubarray方法，该方法创建了一个新的数组，只包含部分元素，要么是左侧（索引从0到m-1，存储为left），要么是右侧（从m到数组长度减1，存储为right）。你会在排序方法的解释之后看到它的实现。回到排序方法的解释，然后你递归地调用排序方法，传递左右子数组。

代码的剩余部分与将子数组合并成整个排序好的数组有关。当然，这个过程是逐步进行的，将子数组合并成越来越大的子数组，直到整个数组排序完成。你使用一个while循环来遍历左右子数组。你使用三个辅助变量，即i作为左数组当前分析元素的索引，j作为右数组的索引，k作为a数组的索引。最初，它们都被设置为0，这样你就可以关注左、右和a数组的第一个元素。

在while循环内，你检查左数组（i索引）的当前元素是否不比右数组（j索引）的当前元素大。如果是这样，你将左数组的当前元素作为a数组的第一个元素。你还需要增加i索引，这意味着左数组的第二个元素是当前的。如果这个条件不满足——也就是说，右数组的当前元素比左数组的当前元素小——你使用右数组的当前元素作为a数组的第一个元素，并增加j索引。最后，你增加k索引以关注a数组的第二个元素。当左或右数组越界时，while循环结束。

当左侧或右侧数组中的一些元素尚未被分析时怎么办？为了处理这种情况，你需要使用两个额外的while循环。这些循环允许你将左侧或右侧数组中剩余的元素放置到a数组中剩余的位置。正如你所见，Sort方法配备了一种非常简单的方式，可以将两个数组合并为一个，并且同时进行排序。

在解释算法实现时，提到了GetSubarray辅助方法。因此，让我们展示它的代码，以及一个简短的解释：

int[] GetSubarray(int[] a, int si, int ei)
{
    int[] result = new int[ei - si + 1];
    Array.Copy(a, si, result, 0, ei - si + 1);
    return result;
}

这种方法使用Array类的Copy静态方法来复制源数组（a）的一部分到在此声明并初始化的目标数组（result）中。为了完成这个任务，你需要取正确数量的元素，即ei - si + 1。这里，ei代表结束索引，si代表起始索引。你需要从源数组（a）的si索引开始复制元素，并将它们存储在目标数组（result）的从0索引开始的位置。

当然，你可以以不同的方式填充子数组，比如使用for循环，它遍历元素并相应地复制它们。如果你想的话，你可以自己准备一个替代的实现，然后在本章后面你会看到的性能测试中进行比较。

时间复杂度如何呢？与我之前介绍的其他排序算法相比，指定归并排序算法的时间复杂度并不容易。然而，它的性能要好得多，可以表示为O(n log(n))，适用于平均情况和最坏情况。在分析性能结果时，你会看到这意味着什么。

不过，你仍然有一些算法要学习，所以让我们继续下一个。