排序---选择排序（Selection Sort）

一、选择排序的基本概念

选择排序（Selection Sort）是一种简单直观的排序算法，其核心思想是每次从待排序元素中找到最值（最小值或最大值），将其放到已排序序列的末尾，重复此过程直到所有元素完成排序。

与冒泡排序通过相邻元素交换逐步"浮"出最值不同，选择排序通过"选择"最值并一次性交换到目标位置，减少了交换操作的次数。这种特性使选择排序在某些场景下（如交换成本较高的情况）表现优于冒泡排序。

二、选择排序的工作原理

选择排序的工作过程可分为以下步骤，我们以升序排序（找最小值）为例说明：

1. 划分区域：将数组分为"已排序区域"和"未排序区域"。初始状态下，已排序区域为空，未排序区域为整个数组。
2. 查找最值：在未排序区域中找到最小元素，记录其索引。
3. 交换元素：将找到的最小元素与未排序区域的第一个元素交换，此时该元素被纳入已排序区域。
4. 重复迭代：缩小未排序区域的范围（左边界右移一位），重复步骤2和3，直到未排序区域为空。

示例演示：
对数组 [64, 25, 12, 22, 11] 进行升序排序的过程：

• 第1轮：未排序区域为 [64, 25, 12, 22, 11]，最小值为11（索引4），与未排序区域第一个元素64交换 → 数组变为 [11, 25, 12, 22, 64]（已排序区域：[11]）。
• 第2轮：未排序区域为 [25, 12, 22, 64]，最小值为12（索引2），与25交换 → 数组变为 [11, 12, 25, 22, 64]（已排序区域：[11, 12]）。
• 第3轮：未排序区域为 [25, 22, 64]，最小值为22（索引3），与25交换 → 数组变为 [11, 12, 22, 25, 64]（已排序区域：[11, 12, 22]）。
• 第4轮：未排序区域为 [25, 64]，最小值为25（索引3），无需交换 → 数组保持 [11, 12, 22, 25, 64]（已排序区域：[11, 12, 22, 25]）。
• 结束：未排序区域仅剩最后一个元素64，排序完成。

三、算法特性分析

1. 时间复杂度
   选择排序的时间复杂度不受输入数据的影响，始终为 O(n²)：

   • 外层循环需要执行 n-1 次（每次确定一个元素的位置）。
   • 内层循环在第 i 轮需要遍历 n-i 个元素（寻找未排序区域的最值）。
   • 总操作次数为 (n-1) + (n-2) + ... + 1 = n(n-1)/2，近似为 n²/2，因此时间复杂度为 O(n²)。

2. 空间复杂度
   选择排序仅使用常数级别的额外空间（如存储最值索引和临时交换变量），因此空间复杂度为 O(1)，是一种"原地排序"算法。

3. 稳定性
   选择排序是不稳定的排序算法。例如，对数组 [2, 2, 1] 排序时，第一个2会与1交换，导致两个2的相对位置发生改变（原顺序为 [2₁, 2₂, 1]，排序后为 [1, 2₂, 2₁]）。

4. 优缺点

   • 优点：实现简单，空间复杂度低，交换操作次数少（最多 n-1 次）。
   • 缺点：时间复杂度高，不适合处理大规模数据；稳定性差，不适用于要求保持相等元素相对顺序的场景。

四、C/C++代码实现

下面是选择排序的C++实现，包含完整的排序函数、测试用例和打印函数：

#include <iostream>
#include <vector>

using namespace std;

// 选择排序函数（升序）
void selectionSort(int arr[], int n) {
    // 外层循环：控制已排序区域的边界（0 ~ i-1为已排序）
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // 记录未排序区域中最小值的索引，初始假设为i
        
        // 内层循环：在未排序区域（i ~ n-1）中寻找最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小值索引
            }
        }
        
        // 将找到的最小值与未排序区域的第一个元素（arr[i]）交换
        if (minIndex != i) { // 若最小值就是当前元素，无需交换
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// 打印数组元素
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    // 测试用例1：整数数组
    int arr1[] = {64, 25, 12, 22, 11};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    
    cout << "排序前的数组：";
    printArray(arr1, n1);
    
    selectionSort(arr1, n1);
    
    cout << "排序后的数组：";
    printArray(arr1, n1);
    
    // 测试用例2：包含重复元素的数组
    int arr2[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    
    cout << "\n排序前的数组（含重复元素）：";
    printArray(arr2, n2);
    
    selectionSort(arr2, n2);
    
    cout << "排序后的数组（含重复元素）：";
    printArray(arr2, n2);
    
    return 0;
}

五、代码解析

1. 排序函数 selectionSort

   • 外层循环变量 i 表示已排序区域的边界（0 ~ i-1 为已排序元素），循环范围为 0 ~ n-2（最后一个元素无需排序）。
   • 内层循环从 i+1 开始遍历未排序区域，通过 minIndex 记录最小值的位置。
   • 找到最小值后，若其位置与 i 不同，则交换 arr[i] 和 arr[minIndex]，将最小值放入已排序区域的末尾。

2. 辅助函数 printArray
   用于打印数组元素，方便观察排序前后的变化。

3. 测试用例

   • 第一个测试用例验证基本排序功能，第二个测试用例验证对含重复元素数组的排序效果（可观察到选择排序的不稳定性）。

六、优化方向

标准选择排序可通过以下方式优化：

1. 双向选择排序
   每次迭代同时寻找未排序区域的最小值和最大值，分别放到已排序区域的两端，减少循环次数（迭代次数从 n-1 减少到 n/2）。

   void bidirectionalSelectionSort(int arr[], int n) {
       int left = 0, right = n - 1;
       while (left < right) {
           int minIndex = left, maxIndex = right;
           // 找最小值和最大值
           for (int i = left; i <= right; i++) {
               if (arr[i] < arr[minIndex]) minIndex = i;
               if (arr[i] > arr[maxIndex]) maxIndex = i;
           }
           // 交换最小值到左侧
           swap(arr[left], arr[minIndex]);
           // 若最大值在左侧（被交换过），更新maxIndex
           if (maxIndex == left) maxIndex = minIndex;
           // 交换最大值到右侧
           swap(arr[right], arr[maxIndex]);
           left++;
           right--;
       }
   }
   

2. 优化交换操作
   对于大型元素（如结构体），交换操作成本较高，可先记录最值位置，最后一次性移动元素（减少复制次数）。

七、适用场景

选择排序适合以下场景：

• 数据量较小（如 n < 100），对排序效率要求不高。
• 内存空间有限，需要原地排序（空间复杂度O(1)）。
• 交换操作成本较高（选择排序的交换次数最少）。

对于大规模数据（n > 1000），建议使用快速排序、归并排序等O(n log n)级别的算法。

选择排序是一种基础的排序算法，其核心思想是"选择最值并交换"，实现简单但效率较低。
在实际开发中，需根据数据规模、空间限制和稳定性要求，选择合适的排序算法。