学习 C++ / 第 18.1 课

使用选择排序对数组排序

18 分钟阅读

为什么需要排序

数组排序就是按特定顺序排列数组中的所有元素。排序有许多用途。例如,邮件程序通常按接收时间显示邮件,因为较新的邮件通常更相关;联系人列表通常按字母顺序排列,便于查找。这两种展示都需要先排序数据。

数组排序可以让人和计算机都更高效地搜索数组。例如,要判断姓名是否在列表中,必须检查数组中的每个元素。对于元素很多的数组,逐个搜索成本很高。

但如果姓名数组已按字母排序,只需搜索到遇到字母顺序更大的姓名为止。此时如果还没找到目标,就知道它不在数组剩余部分,因为剩余姓名一定更大。

搜索排序数组还有更好的算法。使用简单算法,搜索包含 1,000,000 个元素的排序数组只需 20 次比较!当然,排序本身相对昂贵,除非需要多次搜索,否则通常不值得为了加快一次搜索而排序。

在某些情况下,排序甚至可以省去搜索。再看一个例子:我们想找出最高考试分数。 如果数组无序,就必须遍历每个元素才能找出最高分。 如果列表已排序,最高分会位于第一个或最后一个位置(取决于升序还是降序),因此根本不需要搜索!

排序如何工作

排序通常通过反复比较数组元素对,并在满足预设条件时交换它们来完成。比较顺序取决于所使用的排序算法。 比较条件取决于排序方式(例如升序或降序)。

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

C++
#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;
}

程序输出:

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

请注意,交换后 x 和 y 的值互换了!

选择排序

数组排序有很多方法。 选择排序可能是最容易理解的排序方法,虽然速度较慢,却很适合用于教学。

选择排序按以下步骤将数组从小到大排序:

  1. 从数组下标 0 开始,搜索整个数组以找到最小值
  2. 将找到的最小值与下标 0 的值交换
  3. 从下一个下标开始重复步骤 1 和 2

换句话说,先找出最小元素并交换到第一位,再找出下一个最小元素并交换到第二位,如此重复直到处理完所有元素。

下面用包含 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 }

Done!

{ 10, 20, 30, 40, 50 }

请注意,最后一次比较总是元素与自身比较,属于多余操作,因此可以在数组末尾前一个元素处停止。

C++ 中的选择排序

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

C++
#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。 std::sort 位于 <algorithm> 头文件中,可以像下面这样对数组调用:

C++
#include <algorithm> // 用于 std::sort
#include <iostream>
#include <iterator> // 用于 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 使用 operator< 比较元素对,并在需要时交换它们,从而按升序排序(与上面的选择排序示例类似)。

后续章节会进一步介绍 std::sort。

测验时间

问题 #1

手动演示选择排序如何处理以下数组:{ 30, 60, 20, 50, 40, 10 }。写出每次交换后的数组。

显示解答

30 60 20 50 40 10
10 60 20 50 40 30
10 20 60 50 40 30
10 20 30 50 40 60
10 20 30 40 50 60
10 20 30 40 50 60 (自身交换)
10 20 30 40 50 60 (自身交换)

问题 #2

修改上面的选择排序代码,使其按降序排序(最大值在前)。这看起来可能复杂,但实际上非常简单。

显示解答

只需修改:

C++
        if (array[currentIndex] < array[smallestIndex])

to:

C++
        if (array[currentIndex] > array[smallestIndex])

smallestIndex 也应该改名为 largestIndex。

C++
#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) 重复前两步,直到数组完成排序。

按照上述规则编写代码,对下面的数组进行冒泡排序:

C++
int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 };

在程序末尾打印排序后的数组元素。

提示:如果每次迭代能排好一个元素,就需要迭代大约与数组元素数量相同的次数,才能保证整个数组有序。
提示:比较元素对时,要注意数组的范围。

显示解答
C++
#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 迭代{ 0 }; 迭代 < length-1; ++迭代)
    {
        // 搜索数组中直到倒数第二个元素的所有元素
        // 最后一个元素没有可供比较的配对元素
        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

为上一道测验题编写的冒泡排序算法添加两个优化:

  • 注意,在冒泡排序的每次迭代中,剩余的最大值都会移动到数组末尾。第一次迭代后,数组最后一个元素已经有序;第二次迭代后, 倒数第二个数组元素也已排好序,以此类推。每次迭代时,我们不必重新检查已经确定有序的元素。请修改循环,使其不再检查这些元素。
  • 如果完整迭代一次都没有交换,就说明数组已经有序。 添加检查,判断本次迭代是否发生交换;如果没有交换,就提前终止循环。 如果循环提前终止,请输出排序在哪次迭代提前结束。

输出应如下:

第 迭代 次提前结束 6
1 2 3 4 5 6 7 8 9

显示解答
C++
#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 迭代{ 0 }; 迭代 < length-1; ++迭代)
    {
        // 注意最后一个元素在每次后续迭代中都已经排好序
        // 因此数组会提前一个元素“结束”
        int endOfArrayIndex{ length - 迭代 };

        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 << "第 迭代 次提前结束: " << 迭代+1 << '\n';
            break;
        }
    }

    // 打印排序后的数组以验证结果
    for (int index{ 0 }; index < length; ++index)
        std::cout << array[index] << ' ';

    std::cout << '\n';

    return 0;
}

最后更新