045. 实现选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是：在每一轮中，从未排序的部分选择最小（或最大）的元素，将其放到已排序部分的末尾。选择排序的时间复杂度为 O(n2)，虽然效率不高，但实现简单。

C语言实现选择排序

#include <stdio.h>

// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;

    for (i = 0; i < n - 1; i++) { // 外层循环控制排序的轮数
        minIndex = i; // 假设当前轮次的第一个元素是最小值的索引
        for (j = i + 1; j < n; j++) { // 内层循环在未排序部分查找最小值
            if (arr[j] < arr[minIndex]) { // 如果找到更小的值，更新最小值的索引
                minIndex = j;
            }
        }

        // 将找到的最小值与未排序部分的第一个元素交换
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    printArray(arr, n);

    selectionSort(arr, n); // 调用选择排序函数

    printf("排序后的数组：\n");
    printArray(arr, n);

    return 0;
}

代码说明

选择排序函数 selectionSort：
外层循环控制排序的轮数，每一轮从未排序部分选择最小值。
内层循环用于在未排序部分查找最小值的索引。
找到最小值后，将其与未排序部分的第一个元素交换。
打印数组函数 printArray：
用于打印数组的内容，方便查看排序前后的结果。
主函数 main：
定义了一个待排序的数组 arr。
调用 selectionSort 函数对数组进行排序。
打印排序前后的数组。

示例运行

输入：

原始数组：
64 25 12 22 11

输出：

排序后的数组：
11 12 22 25 64

选择排序的特点

简单易实现：选择排序的逻辑简单，实现起来容易。
稳定性：选择排序是一种不稳定的排序算法，即相等元素的相对顺序可能会改变。
时间复杂度：无论数组的初始状态如何，选择排序的时间复杂度始终为 O(n2)。
空间复杂度：选择排序的空间复杂度为 O(1)，因为它只需要一个额外的变量用于交换。

选择排序虽然效率较低，但它的实现简单，适合用于教学和理解排序算法的基本原理。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)