C++程序 选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是从待排序的数列中找到最小的数，将其放到已排序数列的末尾，然后再在剩余数列中找出最小的数，放在已排序数列的末尾，如此重复，直到所有待排序的数列都被排完。

选中排序的优势是交换数据的次数较小，它不需要像交换排序那样频繁的交换数据，而只是在每轮找到最小的值之后，将其放到已排序数列的最后面。

代码实现

我们首先来看选择排序的C++代码实现，代码中包含两个函数，一个是选择排序函数，一个是用于输出数组的函数。

#include <iostream>
using namespace std;

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

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

    // 循环遍历数组
    for (i = 0; i < n - 1; i++)
    {
        // 初始化最小值索引
        min_index = i;

        // 查找未排序部分的最小值
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_index])
                min_index = j;

        // 将最小值放置到数组首部
        swap(&arr[min_index], &arr[i]);
    }
}

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

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

    selectionSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);

    return 0;
}

代码解析

选择排序的实现看起来比较简单，主循环从数组的第一个元素开始，一直遍历到倒数第二个元素为止，内部循环遍历未排序数组中的所有元素，查找最小值。

在每一次内部循环比较中，我们使用 min_index 变量来存储未排序部分的最小值。如果找到了一个更小的元素，我们就将 min_index 的值更新为更小的值的索引。完成内部循环之后，我们使用 swap 函数将找到的最小值放到已排序部分的末尾。

这样选择排序算法在完成所有外部循环之后，就可以将整个数组按升序排列。我们还编写了一个 printArray 函数，用于显示排序后的数组元素。

结论

选择排序虽然是一种比较简单高效的排序算法，但它的时间复杂度为 O(n²)，适用于数据量较小的情况。如果需要处理大量数据，我们需要选择更高效的排序算法，例如基数排序、归并排序或快速排序等。