基础算法

基本思想

选择排序（Selection Sort）是一种简单且直观的排序算法。它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，并将其放到已排序部分的末尾。具体步骤如下：

  1. 初始状态：假设有一个无序数组 arr，长度为 n。

  2. 遍历未排序部分：

    • 从第一个元素开始，假设当前元素是最小值（索引为 i）。
    • 在剩余的未排序部分中查找比当前最小值更小的元素，并记录其索引。

  3. 交换位置：

    • 找到更小的元素后，将其与当前最小值进行交换，使得当前最小值位于已排序部分的末尾。

  4. 重复步骤2-3：

    • 依次对 arr[0] 到 arr[n-1] 进行上述操作。

  5. 结束条件：

    • 当整个数组都被遍历并排序完成后，算法结束。

选择排序的特点

  • 时间复杂度：选择排序的时间复杂度为 $O(n^2)$，因为它需要进行两次嵌套循环，分别遍历未排序和已排序部分。
  • 空间复杂度：选择排序的空间复杂度为 $O(1)$，因为它只需要常数级别的额外空间来存储索引变量。
  • 稳定性：选择排序是不稳定的排序算法，因为交换操作可能导致相同的元素的相对顺序发生变化。

优化

选择排序的核心是每次选择最小或最大元素，因此它的时间复杂度固定为 O(n²)，无法通过优化显著提升性能。

适用场景：

选择排序适用于数据量较小或已经部分有序的情况。虽然它的效率不高，但在特定条件下（如内存限制）仍然有其应用价值。

C语言实现

#include <stdio.h>

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

    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) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = 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, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    selectionSort(arr, n);

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

    return 0;
}

代码解析

  1. selectionSort 函数：

    • i 用于控制外层循环，表示当前待排序部分的起始位置。
    • minIndex 用于记录每一轮遍历中最小元素的下标。
    • 内层循环从 i + 1 开始，找到未排序部分中的最小元素的下标。
    • 如果找到的最小元素不在当前位置，则交换它们。

  2. printArray 函数：

    • 用于打印数组中的元素。

  3. main 函数：

    • 定义了一个待排序的数组 arr，并计算数组的长度 n。
    • 调用 selectionSort 函数对数组进行排序，并打印排序前后的数组。

输出结果

原始数组: 
64 25 12 22 11 90 
排序后的数组: 
11 12 22 25 64 90

发表评论