对数组进行排序
本节阅读量:
排序的案例
对数组排序是按特定顺序排列数组中所有元素的过程。在许多不同的情况下，对数组进行排序都很有用。例如，电子邮件程序通常按接收时间的顺序显示邮件，因为最近的邮件通常更值得关注。当您打开联系人列表时，姓名通常按字母顺序排列，因为这样更容易找到要查找的姓名。这两个例子都涉及在展示之前对数据进行排序。
对数组进行排序可以使搜索数组更有效，不仅对人类，对计算机也是如此。例如，考虑这样一种情况，即我们希望知道名称是否出现在名称列表中。为了查看名称是否在列表中，我们必须检查数组中的每个元素，以查看名称是否出现。对于具有多个元素的数组，搜索所有元素可能会非常昂贵。
然而，现在假设我们的名称数组已经按字母顺序排序。在这种情况下，如果从头遍历到某个名称时，它的字母顺序已经比我们要查找的名称更靠后，而此时仍没有找到目标名称，那么就能知道目标名称不可能存在于数组的其余部分中，因为后续所有名称的字母顺序都只会更靠后！
事实证明，还有更好的算法可以搜索排序数组。使用一个简单的算法，我们只需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的内容。
习题
问题 1
手工演示选择排序在数组{ 30, 60, 20, 50, 40, 10 }上的执行过程。写出每一次交换之后数组的状态。
查看答案
- 初始：30 60 20 50 40 10
- 第1次交换：
10 60 20 50 40 30（把10与30交换）
- 第2次交换：10
20 60 50 40 30（把20与60交换）
- 第3次交换：10 20
30 50 40 60（把30与60交换）
- 第4次交换：10 20 30
40 50 60（把40与50交换）
- 第5次：10 20 30 40
50 60（自己与自己交换）
- 第6次：10 20 30 40 50
60（自己与自己交换）
（最后两次交换的两个元素本来就处于正确位置，属于「自交换」。）
问题 2
把上面选择排序的代码改写成降序排序（大的数字在前面）。这看起来可能很复杂，实际上却出乎意料地简单。
查看答案
只要把
1
|
if (array[currentIndex] < array[smallestIndex])
|
改成：
1
|
if (array[currentIndex] > array[smallestIndex])
|
同时最好把smallestIndex改名为largestIndex。
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
|
#include <iostream>
#include <iterator> // 用于 std::size
#include <utility>
int main()
{
int array[]{ 30, 50, 20, 10, 40 };
constexpr int length{ static_cast<int>(std::size(array)) }; // C++17
// constexpr int length{ sizeof(array) / sizeof(array[0]) }; // 不支持 C++17 时可改用这一行
// 遍历数组中除最后一个元素之外的每个元素
for (int startIndex{ 0 }; startIndex < length - 1; ++startIndex)
{
// largestIndex 是到目前为止遇到的最大元素的下标。
int largestIndex{ startIndex };
// 从 startIndex + 1 开始搜索每个元素
for (int currentIndex{ startIndex + 1 }; currentIndex < length; ++currentIndex)
{
// 如果当前元素比之前找到的最大值更大
if (array[currentIndex] > array[largestIndex])
// 这就是本次迭代新的最大值
largestIndex = currentIndex;
}
// 把起始元素与最大元素交换
std::swap(array[startIndex], array[largestIndex]);
}
// 现在打印排序后的数组，证明它能正常工作
for (int index{ 0 }; index < length; ++index)
std::cout << array[index] << ' ';
std::cout << '\n';
return 0;
}
|
问题 3
这道题会有点难，打起精神来。
另一种简单的排序叫「冒泡排序」。冒泡排序的做法是比较相邻的两个元素，如果满足条件就交换它们，从而让元素「冒泡」到数组末尾。虽然冒泡排序有很多优化方式，但本题我们使用未优化的版本，因为它最简单。
未优化的冒泡排序按下列步骤把数组从小到大排序：
A) 比较下标0和下标1的元素。如果下标0的元素更大，就把它与下标1的元素交换。
B) 对下标1和2，以及之后每一对相邻元素做同样的操作，直到数组末尾。此时数组中最后一个元素已经排好序了。
C) 重复前两步，直到数组完全有序。
请按上述规则编写代码，对下面这个数组进行冒泡排序：
1
|
int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 };
|
在程序末尾打印排序后的数组元素。
提示：如果每次迭代能够排好一个元素，就意味着大致需要迭代「数组元素个数」那么多次，才能保证整个数组有序。
提示：比较相邻元素时，注意数组下标的范围。
查看答案
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
|
#include <iostream>
#include <iterator> // 用于 std::size
#include <utility>
int main()
{
int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 };
constexpr int length{ static_cast<int>(std::size(array)) }; // C++17
// constexpr int length{ sizeof(array) / sizeof(array[0]) }; // 不支持 C++17 时可改用这一行
// 遍历数组的每个元素（最后一个除外，轮到它时它已经排好序了）
for (int iteration{ 0 }; iteration < length-1; ++iteration)
{
// 搜索到数组末尾前一个元素为止
// 最后一个元素没有可以比较的相邻元素
for (int currentIndex{ 0 }; currentIndex < length - 1; ++currentIndex)
{
// 如果当前元素比它后面的元素更大，就交换它们
if (array[currentIndex] > array[currentIndex+1])
std::swap(array[currentIndex], array[currentIndex + 1]);
}
}
// 现在打印排序后的数组，证明它能正常工作
for (int index{ 0 }; index < length; ++index)
std::cout << array[index] << ' ';
std::cout << '\n';
return 0;
}
|
问题 4
为你在上一题中编写的冒泡排序算法添加两项优化：
- 注意冒泡排序每迭代一次，剩余元素中最大的那个就会被「冒泡」到数组末尾。第一次迭代后，最后一个数组元素已经有序；第二次迭代后，倒数第二个元素也有序了，依此类推……每次迭代都不需要再检查那些已知有序的元素。请修改循环，不再重复检查已经有序的元素。
- 如果某次迭代过程中一次交换都没有发生，那么数组显然已经有序。请加入一项检查，判断本次迭代是否发生过交换，如果没有则提前结束循环。如果循环是提前结束的，请打印排序在第几次迭代时提前结束。
输出应与下面一致：
Early termination on iteration 6
1 2 3 4 5 6 7 8 9
查看答案
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
40
41
42
43
44
45
46
47
48
49
|
#include <iostream>
#include <iterator> // 用于 std::size
#include <utility>
int main()
{
int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 };
constexpr int length{ static_cast<int>(std::size(array)) }; // C++17
// constexpr int length{ sizeof(array) / sizeof(array[0]) }; // 不支持 C++17 时可改用这一行
// 遍历数组中除最后一个元素之外的每个元素
for (int iteration{ 0 }; iteration < length-1; ++iteration)
{
// 考虑到每迭代一次，末尾就多一个元素已经排好序
// 因此数组「提前」结束一个元素
int endOfArrayIndex{ length - iteration };
bool swapped{ false }; // 记录本次迭代是否交换过元素
// 搜索到数组末尾前一个元素为止
// 最后一个元素没有可以比较的相邻元素
for (int currentIndex{ 0 }; currentIndex < endOfArrayIndex - 1; ++currentIndex)
{
// 如果当前元素比它后面的元素更大
if (array[currentIndex] > array[currentIndex + 1])
{
// 交换它们
std::swap(array[currentIndex], array[currentIndex + 1]);
swapped = true;
}
}
// 如果本次迭代没有交换任何元素，就可以提前结束
if (!swapped)
{
// 迭代从 0 开始计数，而数迭代次数是从 1 开始，因此这里加 1 修正。
std::cout << "Early termination on iteration: " << iteration+1 << '\n';
break;
}
}
// 现在打印排序后的数组，证明它能正常工作
for (int index{ 0 }; index < length; ++index)
std::cout << array[index] << ' ';
std::cout << '\n';
return 0;
}
|
