跳到主要内容

选择排序

代码​

C语言代码：

#include <stdio.h>

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

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

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

代码解释​

  1. 初始化：数组 arr 是待排序的数组，n 是数组的长度。
  2. 主排序循环：
    • 外部 for 循环控制每一轮的起始位置，从第0个元素到第 n-2 个元素。
    • 初始化最小值索引 min_idx 为当前起始位置 i。
    • 内部 for 循环遍历起始位置后面的所有元素，找到最小值，并更新 min_idx。
    • 找到最小值后，交换当前起始位置元素和最小值元素。
  3. 结果输出：排序完成后，输出排序后的数组。

示例运行​

假设输入数组为 {64, 25, 12, 22, 11}：

  1. 初始状态：{64, 25, 12, 22, 11}
  2. 第一次外部循环（i=0）：
    • 找到最小值11，索引为4，交换64和11：{11, 25, 12, 22, 64}
  3. 第二次外部循环（i=1）：
    • 找到最小值12，索引为2，交换25和12：{11, 12, 25, 22, 64}
  4. 第三次外部循环（i=2）：
    • 找到最小值22，索引为3，交换25和22：{11, 12, 22, 25, 64}
  5. 第四次外部循环（i=3）：
    • 当前剩余部分已经有序，无需交换：{11, 12, 22, 25, 64}

最终结果：{11, 12, 22, 25, 64}

时间复杂度分析​

选择排序的时间复杂度主要取决于两层循环的执行次数。

  • 最优时间复杂度：O(n2)O(n^2)，即使数组已经有序，仍需进行 n(n−1)/2n(n-1)/2 次比较。
  • 最坏时间复杂度：O(n2)O(n^2)，在最坏情况下，执行相同数量的比较和交换操作。
  • 平均时间复杂度：O(n2)O(n^2)，无论数组初始顺序如何，执行次数基本一致。

空间复杂度分析​

选择排序是一种原地排序算法，不需要额外的辅助空间，空间复杂度为 O(1)O(1)。在本实现中，我们仅使用了几个额外的变量（i, j, min_idx, temp），因此空间复杂度保持为常数级别。

优缺点​

优点：

  • 简单易实现。
  • 原地排序，空间复杂度低。
  • 不依赖于初始数据顺序，性能稳定。

缺点：

  • 时间复杂度较高，尤其是对大规模数据，效率较低。
  • 不稳定排序算法，可能改变相同元素的相对顺序。

适用场景​

选择排序适用于以下场景：

  • 数据量较小的排序。
  • 需要一个简单且易于理解的排序算法时。
  • 学习和教学用途，以理解基本的排序原理。

总结​

选择排序是一种简单直观的排序算法，通过反复选择剩余元素中的最小值，将其放到已排序部分的末尾来实现排序。尽管其时间复杂度较高，但在特定场景下，特别是数据量较小时，选择排序仍然是一个有效的选择。