选择排序C++实现

算法简介

选择排序是一种简单直观的比较排序算法。它的基本思想是：从未排序的部分中选出最小（或最大）元素，存放到已排序部分的末尾。该算法每一步都会产生一个有序序列，在每次迭代中，从剩余未排序元素中找到最小元素，并将其移到当前未排序序列的起始位置。

选择排序的主要步骤如下：

从待排序序列中选出最小（或最大）元素。
将选中的元素放到已排序部分的末尾。
对剩下的未排序元素继续执行上述操作，直到所有元素均排序完毕。

C++实现

下面通过一个简单的C++代码示例来展示如何使用选择排序算法对数组进行排序：

#include <iostream>
using namespace std;

// 选择排序函数定义
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 假设当前索引i是未排序部分的最小元素的位置
        int minIndex = i;
        
        // 遍历剩余未排序部分，寻找实际的最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 如果找到了更小的元素，则交换位置
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

// 用于验证排序正确性的函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前的数组：";
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    cout << "排序后的数组：";
    printArray(arr, n);
    
    return 0;
}

解释

选择排序函数定义：selectionSort 接收一个整数数组 arr 和其长度 n。
外层循环：遍历数组，每次从剩余未排序部分找到最小元素的位置，并在首次执行时记录这个位置的索引 minIndex。
内层循环：查找当前未排序部分中的最小值。
交换操作：如果找到更小的元素，则与当前最小元素位置进行交换。
打印函数：printArray 用于输出数组内容，帮助验证排序结果。

这个简单的程序展示了选择排序的基本用法和实现细节。虽然选择排序的时间复杂度为 O(n^2)，但在实际应用中，选择排序的代码简洁且容易理解，适用于小规模数据的排序场景。