当前位置：首页 > article >正文

数据结构：选择排序的实现

article 2025/3/26 14:01:54

概要

选择排序（Selection Sort）是一种原地比较排序算法，核心思想是每轮从未排序区选择极值（最小 / 最大），与未排序区起点交换。

整体架构流程

初始状态：将整个数组视为未排序区域，已排序区域为空。
遍历未排序区域：从当前未排序区域中找到最小值（或最大值）的索引。
交换元素：将找到的最小值与未排序区域的第一个元素交换位置，将该元素归入已排序区域。
重复操作：缩小未排序区域的范围，重复上述步骤，直到所有元素有序。

技术名词解释

不稳定排序：如果排序过程中相等元素的相对顺序可能改变，则该算法是不稳定的。选择排序是典型的不稳定排序（例如对序列 [5, 5, 2] 排序时，第一个 5 可能被交换到第二个 5 之后）。
时间复杂度：算法执行时间与数据规模的关系。选择排序的时间复杂度为 O(n²)，因为需要两层循环遍历元素。
原地排序：排序过程中仅使用常数级别的额外空间，不依赖输入数据规模。选择排序是原地排序。
比较次数：无论输入数据是否有序，选择排序的比较次数恒定为 n(n-1)/2 次。

技术细节

#include <stdio.h>

// 选择排序
void selectSort(int arr[], int length) {
    int i = 0; // 计数器
    int j = 0; // 计数器
    int k = 0; // 用于记录每一趟中最小值的下标
    int temp = 0; // 临时存储空间

    for (i = 0; i < length - 1; i++) {
        // 每一趟的过程
        k = i;

        for (j = i + 1; j < length; j++) {
            // 如果有比 arr[k] 小的值，则对 k 进行修改
            if (arr[j] < arr[k]) {
                k = j; // 记录最小值的下标
            }
        }

        // 如果 k != i，则证明这一趟中找到了比 arr[i] 小的值，
        // 进而交换 arr[i] 和 arr[k] 的值
        if (k != i) {
            temp = arr[k];
            arr[k] = arr[i];
            arr[i] = temp;
        }
    }
}

int main() {
    int arr[] = { 1, 5, 2, 12, 54, 2, 23 }; // 待排序的数组
    int sz = sizeof(arr) / sizeof(arr[0]); // 计算数组的大小

    selectSort(arr, sz); // 选择排序

    // 输出排序后的数组
    printf("排序后的数组: ");
    for (int i = 0; i < sz; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0; // 程序正常结束
}

在这段代码中，selectSort 函数实现了选择排序的逻辑。外层 for 循环控制排序的轮数，内层 for 循环用于在每一轮中寻找未排序部分的最小值的索引 k。

如果找到的最小值索引 k 与当前未排序部分的起始索引 i 不同，就通过临时变量 temp 交换 arr[i] 和 arr[k] 的值，从而将最小值放到已排序部分的末尾。