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

- 一、算法原理
- 二、算法性能分析
- 三、C语言实现示例
- 四、总结

一、算法原理

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

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

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

请添加图片描述

二、算法性能分析

时间复杂度：最好、最坏和平均时间复杂度均为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;
}