0. 简介

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

1. 选择排序的实现

选择排序的基本思想：

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

选择排序过程演示：

2. 选择排序时空间复杂度分析

选择排序的时间复杂度和空间复杂度如下：

  1. 时间复杂度：

    • 无论数据状况如何，选择排序都需要进行 n-1 趟选择，每趟选择都需要进行 n-i 次比较（i 是当前趟数），所以总的时间复杂度是 O(n^2)。

  2. 空间复杂度：

    • 选择排序是原地排序，只需要一个额外空间用于临时交换元素，所以空间复杂度是 O(1)。

总结：选择排序的时间复杂度是 O(n^2)，空间复杂度是 O(1)。

3. 选择排序C语言代码

C代码实现：

#include 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;// 更新最小值的索引}}// 交换找到的最小值与当前趟的起始位置的值temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};// 待排序的数组int n = sizeof(arr)/sizeof(arr[0]);// 数组的长度selectionSort(arr, n); // 对数组进行选择排序printf("Sorted array: \n");for (int i=0; i < n; i++) {// 输出排序后的数组printf("%d ", arr[i]);}printf("\n");return 0;}

代码解释：

  • selectionSort 函数接收一个整数数组和它的长度作为参数。
  • 外层循环负责保证选择的趟数。例如，有7个数字，就需要选择6趟。
  • 内层循环负责在未排序的元素中查找最小值。minIndex 用于记录当前找到的最小值的索引，初始化为当前趟的起始位置。如果发现有更小的数，就更新 minIndex。
  • 内层循环结束后，我们已经找到了当前未排序部分的最小值，然后将其与当前趟的起始位置的值进行交换。这样，当前趟的起始位置就有了正确的值。
  • 外层循环继续进行，直到所有元素都排好序。

4. 选择排序代码运行结果

代码运行结果：