对数组进行排序

排序的案例

对数组排序是按特定顺序排列数组中所有元素的过程。在许多不同的情况下，对数组进行排序都很有用。例如，电子邮件程序通常按接收时间的顺序显示邮件，因为最近的邮件通常更值得关注。当您打开联系人列表时，姓名通常按字母顺序排列，因为这样更容易找到要查找的姓名。这两个例子都涉及在展示之前对数据进行排序。

对数组进行排序可以使搜索数组更有效，不仅对人类，对计算机也是如此。例如，考虑这样一种情况，即我们希望知道名称是否出现在名称列表中。为了查看名称是否在列表中，我们必须检查数组中的每个元素，以查看名称是否出现。对于具有多个元素的数组，搜索所有元素可能会非常昂贵。

然而，现在假设我们的名称数组已经按字母顺序排序。在这种情况下，如果从头遍历到某个名称时，它的字母顺序已经比我们要查找的名称更靠后，而此时仍没有找到目标名称，那么就能知道目标名称不可能存在于数组的其余部分中，因为后续所有名称的字母顺序都只会更靠后！

事实证明，还有更好的算法可以搜索排序数组。使用一个简单的算法，我们只需20次比较就可以搜索包含1000000个元素的排序数组！当然，缺点是对数组进行排序相对昂贵，除非需要多次搜索，否则通常不值得为了快速搜索而先对数组排序。

在某些情况下，对数组进行排序可能会使搜索变得不必要。考虑另一个例子，我们希望找到最好的分数。如果数组未排序，我们必须遍历数组中的每个元素，以找到最大的分数。如果列表被排序，最好的分数将在第一个或最后一个位置（取决于我们是按升序还是降序排序），因此根本不需要搜索！

排序的工作原理

排序通常通过重复比较成对的数组元素来执行，并在它们满足某些预定义标准时交换它们。根据使用的排序算法，比较元素的顺序会有所不同，同时也取决于列表的排序方式（例如升序或降序）。

要交换两个元素，可以使用C++标准库中的std::swap()函数，该函数在<utility>头文件中定义。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <iostream>
#include <utility>

int main()
{
    int x{ 2 };
    int y{ 4 };
    std::cout << "Before swap: x = " << x << ", y = " << y << '\n';
    std::swap(x, y); // 交换 x 和 y
    std::cout << "After swap:  x = " << x << ", y = " << y << '\n';

    return 0;
}

该程序打印:

1
2

Before swap: x = 2, y = 4
After swap:  x = 4, y = 2

请注意，在交换之后，x和y的值已经互换！

选择排序

有许多方法可以对数组进行排序。选择排序可能是最容易理解的排序算法，这使它很适合用于教学，尽管它是较慢的排序算法之一。

选择排序执行以下步骤，以从最小到最大对数组进行排序:

换句话说，我们将找到数组中最小的元素，并将其交换到第一个位置。然后我们要找到下一个最小的元素，并将其交换到第二个位置。将重复此过程，直到元素用完。

下面是该算法在5个元素上工作的示例。让我们从一个示例数组开始:

{30、50、20、10、40}

首先，我们找到最小的元素，从索引0开始:

{30、50、20、10、40}

然后将其与索引0处的元素交换:

{10、50、20、30、40}

现在第一个元素已经排序，我们可以忽略它。现在，我们找到最小的元素，从索引1开始:

{10、50、20、30、40}

并与索引1中的元素交换:

{10、20、50、30、40}

现在我们可以忽略前两个元素。从索引2开始查找最小元素:

{10、20、50、30、40}

并与索引2中的元素交换:

{10、20、30、50、40}

从索引3开始查找最小元素:

{10、20、30、50、40}

并与索引3中的元素交换:

{10、20、30、40、50}

最后，从索引4开始找到最小的元素:

{10、20、30、40、50}

并将其与索引4中的元素交换（该元素不执行任何操作）:

{10、20、30、40、50}

完成！

{10、20、30、40、50}

请注意，最后一次比较总是与自身进行比较（这是冗余的），因此我们实际上可以在数组最后一个元素之前停止比较。

C++实现的选择排序

下面是该算法在C++中的实现方式:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <iterator>
#include <utility>

int main()
{
	int array[]{ 30, 50, 20, 10, 40 };
	constexpr int length{ static_cast<int>(std::size(array)) };

	// 从头遍历
	// 但不处理最后一个位置
	for (int startIndex{ 0 }; startIndex < length - 1; ++startIndex)
	{
		// smallestIndex 是遍历时遇到的最小元素的位置
		// 开始时，暂定起点位置就是最小元素的位置
		int smallestIndex{ startIndex };

		// 然后遍历数组中后续的元素
		for (int currentIndex{ startIndex + 1 }; currentIndex < length; ++currentIndex)
		{
			// 如果发现一个元素比之前的要小
			if (array[currentIndex] < array[smallestIndex])
				// 更换记录的位置
				smallestIndex = currentIndex;
		}

		// smallestIndex 现在保存的就是最小元素的位置
        // 将其与开头的元素进行交换 (意味着将它放到了正确的位置)
		std::swap(array[startIndex], array[smallestIndex]);
	}

	// 现在数组都排序好了，打印验证一下
	for (int index{ 0 }; index < length; ++index)
		std::cout << array[index] << ' ';

	std::cout << '\n';

	return 0;
}

该算法最令人困惑的部分是循环中的循环（称为嵌套循环）。外层循环（startIndex）逐个迭代每个元素。对于外层循环的每次迭代，内层循环（currentIndex）用于查找剩余数组中的最小元素（从startIndex+1开始）。smallestIndex跟踪内层循环找到的最小元素的索引。然后将smallestIndex对应的元素与startIndex对应的元素交换。最后，外层循环（startIndex）前进一个元素，并重复该过程。

提示:如果您在理解上面的程序如何工作时遇到困难，可以在纸上手动推演一个示例。将起始（未排序）数组元素横向写在纸的顶部。绘制箭头，指示startIndex、currentIndex和smallestIndex当前索引的元素。手动跟踪程序，并在索引更改时重新绘制箭头。对于外层循环的每次迭代，另起一行显示数组的当前状态。

排序名称使用相同的算法。只需将数组类型从int更改为std::string，并使用适当的值进行初始化。

std::sort

由于排序数组非常常见，C++标准库包含一个名为std::sort的排序函数，该函数位于<algorithm>头文件中，并且可以在类似这样的数组上调用:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <algorithm> // for std::sort
#include <iostream>
#include <iterator> // for std::size

int main()
{
	int array[]{ 30, 50, 20, 10, 40 };

	std::sort(std::begin(array), std::end(array));

	for (int i{ 0 }; i < static_cast<int>(std::size(array)); ++i)
		std::cout << array[i] << ' ';

	std::cout << '\n';

	return 0;
}

默认情况下，std::sort使用操作符<来比较元素对，并按升序排序，在必要时交换它们（与上面的选择排序示例非常相似）。

我们将在以后的一章中讨论更多关于std::sort的内容。