选择排序算法详解：原理、代码与优化

选择排序概述

选择排序（Selection Sort）是一种基础且直观的排序算法。它的核心逻辑很简单：每一轮遍历从未排序的序列中选出最小（或最大）的元素，将其放到已排序序列的末尾。

实现思路遵循由局部到整体：先排好一个元素，再处理多个，直到整个数组有序。

工作原理演示

以升序排序为例，整个过程可以拆解为以下步骤：

1. 初始化：假设数组前部分是已排序的，后部分是未排序的。初始时，已排序部分为空。
2. 寻找极值：遍历未排序部分，找出其中的最小值。
3. 交换位置：将找到的最小值与未排序部分的第一个元素交换。
4. 重复迭代：缩小未排序部分的范围，重复上述步骤，直到整个数组有序。

执行过程示例

假设待排序数组为：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

• 第一轮：在未排序部分 [3, 44, ...] 中找到最小值 2。将 2 与首位 3 交换。数组变为 [2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]。
• 第二轮：在剩余未排序部分 [44, 38, ...] 中找到最小值 3。将 3 与首位 44 交换。数组变为 [2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]。
• 第三轮：找到最小值 4，与首位 38 交换。数组变为 [2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]。
• 第四轮：最小值是 5，它已经在正确位置，无需交换。
• 后续轮次：依次确定 15, 19, 26, 27, 36, 38, 44, 46, 47, 48 的位置。

经过多轮筛选与交换，最终得到有序数组：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]。

代码实现

下面是基于 C 语言的基础选择排序实现。注意，这里假设存在一个 Swap 辅助函数用于交换两个整数的地址。

void SelectSort(int* a, int n) {
    // i 控制排序趟数，需要 n-1 趟才能使得待排数组有序
     ( i = ; i < n - ; i++) {
        
         min_index = i;
        
        
         ( j = i + ; j < n; j++) {
             (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        
        
         (min_index != i) {
            Swap(&a[i], &a[min_index]);
        }
    }
}