使用选择排序对数组进行排序

排序的必要性

排序数组是将数组中所有元素按特定顺序重新排列的过程。排序在众多场景中都极为有用。例如，电子邮件客户端通常按接收时间顺序显示邮件，因为新近邮件往往更具相关性；通讯录中的姓名则按字母顺序排列，以便快速查找。这些展示方式都依赖于事先对数据排序。

对数组排序不仅能提升人类检索效率，也能提高计算机检索效率。假设我们要查询某个名字是否出现在名单中。若名单无序，只能逐一比对每个元素；当元素数量庞大时，代价极高。而一旦名单已按字母顺序排序，我们只需顺序查找，直到遇到比目标名字更大的条目即可；此时若仍未找到，即可确定其余元素均大于目标，名字必不存在于后续部分。

事实上，存在更高效的算法可在有序数组中搜索。例如，简单算法即可在含 100 万个元素的有序数组中仅用 20 次比较完成查找！但代价是排序本身较为耗时，除非需要多次搜索，否则仅为加速搜索而排序未必划算。

在某些场景下，排序甚至可完全省去搜索。例如，若需找出最高分，无序数组必须遍历全部元素；若数组已排序，最高分必在首尾之一（取决于升序或降序），直接取得即可，无需搜索。

排序原理

排序通常通过反复比较并交换相邻元素实现。比较顺序取决于所选算法；交换准则则取决于排序方式（升序或降序）。交换两个元素可使用 头文件中的 std::swap：

#include <iostream>
#include <utility>

int main()
{
    int x{2}, y{4};
    std::cout << "交换前：x = " << x << ", y = " << y << '\n';
    std::swap(x, y);
    std::cout << "交换后：x = " << x << ", y = " << y << '\n';
    return 0;
}

输出：

交换前：x = 2, y = 4
交换后：x = 4, y = 2

选择排序

选择排序（Selection Sort）易于理解，尽管速度并非最优，却适合教学。该算法将数组从小到大排序，步骤如下：

1. 从下标 0 开始，遍历整个数组找出最小值；
2. 将找到的最小值与下标 0 元素交换；
3. 从下标 1 开始重复步骤 1 和 2，直至处理完所有元素。

简言之，每次都把剩余部分的最小值放到当前已排序区间的末尾。以下示例展示了对 5 个元素的排序过程：

初始：{ 30, 50, 20, 10, 40 }

• 本轮：找到最小值 10，与下标 0 交换 → { 10, 50, 20, 30, 40 }
• 本轮：从下标 1 开始，找到最小值 20，与下标 1 交换 → { 10, 20, 50, 30, 40 }
• 本轮：从下标 2 开始，找到最小值 30，与下标 2 交换 → { 10, 20, 30, 50, 40 }
• 本轮：从下标 3 开始，找到最小值 40，与下标 3 交换 → { 10, 20, 30, 40, 50 }
• 本轮：与自身交换，结果不变。

注意到最后一轮比较冗余，故可在到达倒数第二个元素时终止。

选择排序的 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)
    {
        int smallestIndex{ startIndex }; // 当前轮次最小值索引

        // 内层循环在剩余部分找最小值
        for (int currentIndex{ startIndex + 1 }; currentIndex < length; ++currentIndex)
        {
            if (array[currentIndex] < array[smallestIndex])
                smallestIndex = currentIndex;
        }

        std::swap(array[startIndex], array[smallestIndex]);
    }

    // 打印有序数组
    for (int index{ 0 }; index < length; ++index)
        std::cout << array[index] << ' ';
    std::cout << '\n';

    return 0;
}

算法的关键在于嵌套循环：外层 startIndex 逐一推进，内层 currentIndex 在剩余区间寻找最小值，并记录于 smallestIndex，随后交换。将过程用纸笔模拟可加深理解。

排序字符串时，只需将数组类型改为 std::string 并赋予相应初值即可。

std::sort

因排序极为常用，C++ 标准库在 <algorithm> 中提供了 std::sort：

#include <algorithm>
#include <iostream>
#include <iterator>

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 } 的过程，每次交换后写出数组状态。
（答案略）

问题 2
改写上述选择排序代码，使其按降序排列（大数在前）。
（答案略）

问题 3
实现未优化的冒泡排序，对数组 int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 }; 排序并输出结果。
（答案略）

问题 4
在上题冒泡排序基础上加入两项优化：

1. 每轮结束后，下一轮不再检查已沉底的有序部分；
2. 若某轮未发生任何交换，则提前终止，并输出提前终止的轮次。
   示例输出：Early termination on iteration 6
   （答案略）