C++实现选择性排序（SelectionSort）

C++实现选择性排序（SelectionSort）

选择性排序（Selection Sort）是计算机科学中一种简单直观的排序算法。它的工作原理是：首先在未排序的数列中找到最小（大）的元素，然后将其存放到数列的起始位置，接着再从剩余的未排序元素中继续寻找最小（大）的元素，然后放到已排序序列的末尾。以此类推，直到所有元素均被排序完毕。

具体的实现步骤如下：

1. 在未排序的数列中找到最小元素。
2. 将其存放到数列的起始位置。
3. 从剩余未排序的元素中继续寻找最小元素。
4. 将其存放到已排序序列的末尾。
5. 以此类推，直到所有元素均被排序完毕。

以下是C++代码实现以及相关注释：

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // 依次遍历数组元素
    for (i = 0; i < n - 1; i++) {

        // 找到未排序区域中最小元素的下标
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // 将未排序区域中最小元素放到已排序序列的末尾
        swap(arr[min_idx], arr[i]);
    }
}

int main() {
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // 调用选择排序函数
    selectionSort(arr, n);

    // 打印排序后的数组
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

在本示例中，我们定义了一个名为 selectionSort() 的排序算法函数来进行选择排序，并将完整的未排序数组作为函数实参传递，以及数组中的元素数目 n。

使用两个循环来实现选择排序的算法。通过第一个循环遍历数组中的每个未排序元素，通过第二个循环遍历未排序区域中的元素，并找到最小元素的下标。然后将未排序区域中的最小元素放到已排序序列的末尾，以达到排序的目的。

以下是示例，更具体地展示了本算法的工作原理：

示例1：

假设输入的未排序数组为 {64, 25, 12, 22, 11}。在第一次循环之后，我们可以通过找到最小的元素（11）并将其放置在数组的开头位置时得到以下结果：

11 25 12 22 64

示例2：

在第二次循环后，我们可以找到最小元素（12）并将其放置在索引 1 的位置，以下是本次循环的结果：

11 12 25 22 64

继续执行以上步骤，直到所有元素都被排序完成，得到如下排序后的数组：

11 12 22 25 64

希望这个C++实现选择性排序（SelectionSort）的教程对你有所帮助。