HB4-简单选择排序¶

代码实现¶

C
/**
 * 交换两个元素
 */
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
 * 简单选择排序
 * 基本思想：每次从未排序部分选择最小元素，放到已排序部分的末尾
 */
void selectionSort(int arr[], int n) {  
    // 外层循环：控制排序趟数（n-1趟）
    for (int i = 0; i < n - 1; 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]);
        }
    }
}

算法执行过程图解¶

Text Only

初始数组: [49] [38] [65] [97] [76] [13] [27]
          A[0] A[1] A[2] A[3] A[4] A[5] A[6]

第1轮(i=0): 在整个数组中找最小元素
查找过程: 49>38(pos=1)→38<65→38<97→38<76→38>13(pos=5)→13<27
找到最小元素13，位置在A[5]
交换A[0]和A[5]: [13] [38] [65] [97] [76] [49] [27]

第2轮(i=1): 在[38] [65] [97] [76] [49] [27]中找最小元素
查找过程: 38<65→38<97→38<76→38>49→49>27(pos=6)
找到最小元素27，位置在A[6]
交换A[1]和A[6]: [13] [27] [65] [97] [76] [49] [38]

第3轮(i=2): 在[65] [97] [76] [49] [38]中找最小元素
查找过程: 65<97→65>76(pos=4)→76>49(pos=5)→49<38(pos=6)
但pos=6不在查找范围内，实际最小是49(pos=5)
交换A[2]和A[5]: [13] [27] [49] [97] [76] [65] [38]

...继续此过程直到排序完成

复杂度分析¶

时间复杂度：O(n²)¶

详细分析：

外层循环：执行 n-1 次（i 从 0 到 n-2）
内层循环：
第1轮：比较 n-1 次
第2轮：比较 n-2 次
第3轮：比较 n-3 次
...
第n-1轮：比较 1 次

总比较次数：

Text Only
1	`(n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2`

交换次数：
最好情况：0 次交换（数组已有序）
最坏情况：n-1 次交换
平均情况：n-1 次交换
总体时间复杂度：O(n²)

空间复杂度：O(1)¶

只使用了常数个额外变量（pos, temp, i, j）
没有使用额外的存储空间
空间复杂度为 O(1)

关键知识点延伸¶

1. 算法特点¶

不稳定排序：相等元素的相对位置可能改变
原地排序：只需要常数级额外空间
交换次数少：最多进行 n-1 次交换

2. 稳定性问题示例¶

Text Only

数组: [5] [2] [8] [2'] [1]  (其中2和2'相等但不同元素)
第1轮: 找到最小元素1，与位置0交换
结果: [1] [2] [8] [2'] [5]
此时原在后面2'跑到了前面，破坏了稳定性

3. 与冒泡排序的比较¶

特性	选择排序	冒泡排序
比较次数	n(n-1)/2	n(n-1)/2
交换次数	最多n-1次	最多n(n-1)/2次
稳定性	不稳定	稳定
性能	相对较好	相对较差

4. 优化版本：双向选择排序¶

C
/**
 * 双向选择排序 - 同时找最大和最小元素
 */
void BidirectionalSelectSort(int A[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        int minPos = left, maxPos = left;

        // 同时找最小和最大元素
        for (int i = left; i <= right; i++) {
            if (A[i] < A[minPos]) minPos = i;
            if (A[i] > A[maxPos]) maxPos = i;
        }

        // 交换最小元素到左端
        if (minPos != left) {
            int temp = A[left];
            A[left] = A[minPos];
            A[minPos] = temp;
        }

        // 如果最大元素在left位置，需要更新maxPos
        if (maxPos == left) maxPos = minPos;

        // 交换最大元素到右端
        if (maxPos != right) {
            int temp = A[right];
            A[right] = A[maxPos];
            A[maxPos] = temp;
        }

        left++;
        right--;
    }
}

5. 适用场景¶

数据量小：实现简单，适合小规模数据
交换代价高：相比冒泡排序，交换次数更少
内存受限：原地排序，空间复杂度低

6. 算法改进建议¶

减少不必要的交换：

C
if (pos != i) {  // 只有位置不同时才交换
    // 执行交换操作
}

记录最大值：可以同时记录最大值位置，减少轮数
结合其他算法：对于小规模子数组使用选择排序