希尔排序

希尔排序算法采用了一种不同于其他排序方法的途径，其名称来源于算法的发明者。它是已经介绍过的插入排序的一种变体。该算法执行h排序，以排序由距离等于h的元素组成的虚拟子数组，使用插入排序。起初，h被设置为数组长度的一半，并在每次迭代中除以2，直到它等于1。这个描述可能看起来有点复杂，但它是一个出人意料地高效的算法，实现起来非常简单。

首先，让我们来看一个图表，它应该会使这个话题比单纯的文本更简单、更容易理解：

由于源数组包含7个元素，初始的h值被设置为3。所以现在，是时候进行3排序了。

你创建了虚拟子数组，其中元素的索引相差3。这意味着使用了以下索引：(0, 3, 6)，(1, 4)和(2, 5)。第一个虚拟子数组由(-11, -15, -13)组成，

所以你对其进行排序，得到(-15, -13, -11)。第二个是(12, -4)，排序后形成(-4, 12)。最后一个子数组是(13, -9)，排序后变成(-9, 13)。

当3排序完成后，你计算下一个h值，简单地将当前值除以2。结果是1，这也是最后一次h排序迭代，即1排序。现在，你执行一个简单的插入排序。

插图和描述看起来很简单，不是吗？让我们写一些C#代码来实现Shell排序算法，如下所示:

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

实现包含三个循环。第一个for循环用于计算h的适当值，从数组（a）长度的一半开始。每次迭代后，它会再除以2，最后一个可接受的值是1。

接下来的for循环计算i索引，从h开始，并增加它直到达到数组的末尾。这部分用于对虚拟子数组执行插入排序。

在循环内，你可以使用ai变量来存储当前i索引处元素的值，以便稍后用另一个值替换它。然后，使用while循环来移动虚拟子数组中的元素，以找到ai的正确位置。最后，你将ai变量存储在j变量指示的位置。

正如你所见，实现非常简短且相当简单。更重要的是，这个算法效率高，可用于排序大量数据集，正如你将在本章后面看到的。但是时间复杂度如何呢？在最坏的情况下，它是O(n^2)。然而，其平均时间复杂度大约是O(n log(n))。

快速排序

本书描述的第六种排序算法是快速排序。它是分治法这一流行算法组中的一个，它将问题划分为一组更小的问题。它是如何工作的？

该算法选择某个值（例如，从数组的最后一个元素中）作为基准。然后，它以这样的方式重新排列数组：比基准小的值被放置在它前面（形成下部分数组），而大于或等于基准的值被放置在它后面（形成上部分数组）。这样的过程称为分区。接下来，算法递归地对每个上述子数组进行排序。每个子数组进一步被划分为下两个子数组，如此类推。当子数组中有一个或零个元素时，递归调用停止，因为在这样的情况下，没有东西需要排序。

前面的描述可能听起来有点复杂。然而，下面的图示和算法的实现应该会消除任何疑问。

以下图表展示了快速排序算法如何对包含九个元素（-11, 12, -42, 0, 1, 90, 68, 6, 和 -9）的一维数组进行排序：

在我们的案例中，假设选择的枢轴值是当前正在排序的子数组的最后一个元素的值。在步骤1中，选择了-9作为枢轴。然后，需要将12与-42交换（步骤1），以及将12与-9交换（步骤2），以确保只有小于枢轴的值（-11, -42）在下部子数组中，而大于或等于枢轴的值（0, 1, 90, 68, 6, 12）被放置在上部子数组中（步骤3）。然后，对上述两个子数组递归调用算法，即（步骤4中的-11, -42）和（步骤7中的0, 1, 90, 68, 6, 12），以便它们像输入数组一样被处理。

例如，步骤7显示选择12作为枢轴。分区后，子数组被分为两个其他子数组，即（0, 1, 6）和（90, 68）。对于这两个子数组，选择其他枢轴元素，即6和68。对数组的所有剩余部分执行这些操作后，你将得到步骤16中显示的结果。

值得一提的是，在该算法的其他实现中，枢轴的选择方式可以有所不同。现在你已经理解了算法的工作原理，让我们继续进行其实现。它并不比之前展示的例子更复杂，它使用递归调用子数组的排序方法。主要代码如下：

排序方法只接受一个参数，即应该被排序的数组。它仅仅调用了SortPart方法，这使得可以指定下限和上限索引，这些索引指示了应该对数组的哪一部分进行排序。SortPart方法的代码如下所示：

首先，该方法检查数组（或子数组）是否至少有两个元素，通过比较 l（下标）和 u（上标）变量的值。如果否，你将从这个方法中返回。否则，你将执行分区阶段。

在这里，选择数组（或子数组）中的最后一个元素作为枢轴值，并将其存储为枢轴变量的值。然后，使用 for 循环通过比较和交换元素来重新排列数组。你需要执行这个阶段以确保将小于枢轴的值放在它前面，而大于或等于枢轴的值放在它后面。

最后，你将枢轴值的新索引存储为 p，并执行交换以将其放置在那里。p 变量还用于计算子数组的下界和上界，即 (l, p-1) 和 (p+1, u)。这样的范围随后用于递归调用 SortPart 方法对下部和上部进行排序。就这样！

时间复杂度如何呢？它的平均时间复杂度为 O(n log(n))，尽管最坏情况下的时间复杂度为 O(n^2)。这看起来像希尔排序吗？如果是的话，你是对的！你正越来越接近本章的结尾，在那里你将看到对各种排序算法进行性能测试的结果。

堆排序

我们将要介绍的最后一种方法基于一个有趣的数据结构，称为二叉堆。为了给你一个简短的介绍，它是一个基于树的结构，其中每个节点包含零个、一个或两个子节点。你将在本书后面学习更多关于树及其变体的知识。

你不会感到惊讶，排序解决方案被称为堆排序。首先，算法从数组构建一个最大堆（堆化操作）。然后，它重复执行几个步骤，直到堆中只剩下一个元素：

1. 将第一个元素（具有最大值的根）与最后一个元素交换。

2. 从堆中移除最后一个元素（当前是最大值）。

3. 再次构建最大堆。

通过执行这些操作，你将有效地获得排序后的数组。

由于必须在这里引入一个新的数据结构，让我们看看二叉堆是什么样子，以及算法是如何操作以对示例数组进行排序的：

输入数组包含六个元素，分别是-11、12、-42、0、90和-9。你可以通过将第一个元素作为根节点，然后添加它的两个子节点：12和-42来构建一个二叉堆。在这个堆的这一层，你没有更多的空间，所以让我们将数组中的接下来两个元素（0和90）作为子节点添加到值为12的节点上。数组中的最后一个元素被留下。你必须将它作为值为-42的节点的子节点。正如你所见，你可以很容易地将一个数组映射到二叉堆数据结构，并且可以使用数组作为数据结构来存储二叉堆的数据。

二叉堆的有趣属性

记住，在二叉堆中，根节点由数组表示，位于array[0]。如果你需要访问第i个元素的父节点的数据，你可以从array[(i-1)/2]获取。第i个元素的左子节点和右子节点分别可以在array[(2*i)+1]和array[(2*i)+2]中找到。

在堆排序算法中扮演重要角色的下一个操作被称为堆化（heapify）。它看起来可能有点复杂，但在简短的解释后应该会变得清晰。这个操作的目标是将二叉堆转换成最大堆。这意味着每个节点只能包含其值小于或等于节点值的子节点。以图中第一行为例，通过使用堆化操作，90被定位为根节点。它包含12和-9作为子节点。带有12的节点包含更小值的子节点，即0和-11。带有-9的节点只包含一个元素，这个元素也比它小，即-42。

Max-堆不是唯一的选择

你也可以使用堆化操作来形成Min-堆。这与Max-堆类似，

但每个节点需要满足的条件是其子节点的值大于或等于父节点的值。

让我们继续看前面图形的第二行。这里，数组的最后一个元素（90）已经排序。

这是将根节点（之前是90）与数组中的最后一个元素（之前是-42）交换的结果。

然后，你必须执行另一个堆化操作，并得到以12为根的Max-堆。上述动作重复进行，直到堆中只剩下一个元素。

最后，你得到排序后的数组，如前面图形右下角所示。

此时，你应该准备好分析C#语言中的实现代码：

排序方法包含两个for循环。第一个执行初始堆化操作以准备最大堆。你可以通过多次调用Heapify方法来实现，具体来说是逆序调用，并且是在每一个非叶子节点上进行。然后，你将得到一个数据形成的最大堆数组。

第二个for循环一直执行到堆中至少还有一个元素。在每次迭代中，它会将根元素（索引等于0）与最后一个元素交换，该元素的索引等于i。然后，你需要恢复最大堆属性，这可以通过调用Heapify方法来完成，针对的是堆受影响的部分。

现在，让我们来看一下Heapify方法的代码：

它需要三个参数，即一个数组（a），堆中元素的数量（n），以及一个元素的索引（i），该元素是应该被堆化的一个子树的根。首先，你得到最大元素的索引（根，作为max），以及它的左右子节点（分别用l和r表示）。你可以根据之前给出的公式计算索引，即2*i+1和2*i+2。

在接下来的两行中，你检查左子节点索引（l）是否仍在堆内（l<n）以及具有该索引的元素（a[l]）是否大于当前根值（a[max]）。如果是这样，你需要更新根索引（max）。同样的方式，你检查右子节点并根据需要调整max变量。

在下一行中，你检查在上述操作过程中根索引是否发生了变化。如果是这样，这意味着当前根不是最大值，你需要在数组中交换两个元素，即表示根（i索引）和最大值（max索引）。接下来，你递归地对受影响的子树执行堆化操作，即以新根值的树。

在这详细的解释之后，值得一提的是时间复杂度。在这个情况下它非常重要，因为这个方法效率高，可以在排序大量数据集时成功使用。时间复杂度是O(n log(n))。

尽管我们已经学习了七种不同的排序算法，但请记住还有许多其他的算法，包括块排序、树排序、立方排序、链排序和循环排序。如果你对这个话题感兴趣，我强烈建议你自己去了解一下它们。与此同时，让我们比较一下本章中我们已经讨论过的算法。