【C语言】深入解析选择排序算法

一、算法原理

 选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是不断地选择剩余元素中的最小（或最大）元素，放到已排序的序列的末尾，直到排序完整个序列。

选择排序的主要步骤如下：

1. 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
2. 从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

二、算法性能分析

• 时间复杂度：最好、最坏和平均时间复杂度均为O($n^2$)。
• 空间复杂度：O(1)，选择排序只需要一个额外的存储空间用于交换元素。
• 稳定性：不稳定，选择排序在找到最小（或最大）元素后，需要和序列的起始位置进行交换，可能会导致相同元素的相对顺序发生改变。

三、C语言实现示例

以下是一个使用C语言实现的选择排序算法的示例：

#include <stdio.h>
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    // 一遍又一遍地遍历未排序的部分
    for (i = 0; i < n - 1; i++) {
        // 找到最小元素的索引
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 将找到的最小元素与第i个位置的元素交换
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}
// 打印数组的函数
void printArray(int arr[], int size) {
    int i;
    for (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]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

运行上述代码，将会得到已排序的数组：

Sorted array: 
11 12 22 25 64 
1
2

四、总结

 选择排序是一种简单直观的排序算法，易于实现，但时间复杂度较高，适用于数据量较小的场景。在实际应用中，应根据具体需求选择合适的排序算法。希望本文对您有所帮助。