C语言选择排序（附带源码和解析）

选择排序是一种简单直观的排序算法，它的工作原理是通过不断选择剩余元素中的最小值，将其放置到已排序序列的末尾。尽管选择排序在效率上不如一些更先进的排序算法，但它的概念简单，易于理解和实现，非常适合初学者学习排序算法的基本原理。

选择排序的基本原理

选择排序的核心思想是将待排序的数组分为两个部分：已排序部分和未排序部分。算法从未排序部分中反复选择最小的元素，将其添加到已排序部分的末尾。这个过程会不断重复，直到所有元素都被排序。

具体步骤如下：

将数组的第一个元素视为已排序部分，其余元素视为未排序部分。
在未排序部分中找到最小的元素。
将找到的最小元素与未排序部分的第一个元素交换位置。
已排序部分向右扩展一个元素。
重复步骤 2-4，直到所有元素都被排序。

为了更直观地理解这个过程，让我们通过一个例子来展示选择排序的工作原理：

原始数组：[64, 25, 12, 22, 11]

第一次迭代：
找到最小元素 11，与第一个元素 64 交换位置
[11, 25, 12, 22, 64]

第二次迭代：
在剩余元素中找到最小元素 12，与第二个元素 25 交换位置
[11, 12, 25, 22, 64]

第三次迭代：
在剩余元素中找到最小元素 22，与第三个元素 25 交换位置
[11, 12, 22, 25, 64]

第四次迭代：
在剩余元素中找到最小元素 25，已在正确位置，无需交换
[11, 12, 22, 25, 64]

排序完成：[11, 12, 22, 25, 64]

C语言实现选择排序

现在，让我们用 C 语言来实现选择排序算法。以下是一个完整的 C 程序，展示了选择排序的实现：

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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;
            }
        }
        if (min_idx != i) {
            swap(&arr[min_idx], &arr[i]);
        }
    }
}

void printArray(int arr[], int size) {
    for (int 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]);

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

    selectionSort(arr, n);

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

    return 0;
}

运行结果：

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

这段代码实现了选择排序算法，并包含了一个主函数来演示其使用，让我们逐步解析代码的关键部分。

swap() 函数用于交换两个整数的值。它使用指针来直接修改传入的变量值，而不是创建副本。

selectionSort() 函数是选择排序的核心实现，它接受一个整数数组和数组长度作为参数。函数使用两个嵌套的循环来完成排序：

外层循环 i 遍历数组，每次迭代都将当前位置视为未排序部分的起始位置。
内层循环 j 从 i+1 开始，查找未排序部分中的最小元素。
如果找到比当前最小值更小的元素，就更新 min_idx。
内层循环结束后，如果找到了更小的元素（即 min_idx != i），就交换它们的位置。

printArray() 函数用于打印数组的内容，方便我们查看排序前后的结果。

main() 函数演示了如何使用选择排序算法。它创建一个示例数组，打印原始数组，调用 selectionSort 函数进行排序，然后打印排序后的数组。

选择排序的性能以及优缺点

选择排序的时间复杂度在所有情况下都是 O(n²)，其中 n 是数组的长度。这是因为算法总是执行两个嵌套的循环，无论输入数据的初始排列如何。

外层循环执行 n-1 次，因为最后一个元素不需要比较。对于每次外层循环，内层循环的比较次数逐渐减少：n-1, n-2, ..., 2, 1。这些比较次数的总和是 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2，因此总的时间复杂度为 O(n²)。

选择排序有以下优点：

概念简单，易于理解和实现；
对于小规模的数据集，性能还算可以；
不需要额外的存储空间，是原地排序算法。

然而，选择排序也存在一些缺点：

时间复杂度较高，对于大规模数据集效率较低；
不稳定的排序算法，可能改变相等元素的相对顺序；
对于几乎已经排序的数据，没有优化余地。

优化选择排序

虽然选择排序的基本思想很简单，但我们仍然可以对其进行一些优化：

双向选择排序：每次迭代同时选择最小和最大元素，可以减少循环次数。
使用堆数据结构：将选择排序与堆结构结合，可以将时间复杂度降低到 O(n log n)。
对于小规模子数组使用插入排序：当子数组规模较小时，插入排序可能比选择排序更快。

以下是双向选择排序的C语言实现示例：

void bidirectionalSelectionSort(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        int min = left, max = right;
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[min]) min = i;
            if (arr[i] > arr[max]) max = i;
        }
        swap(&arr[left], &arr[min]);
        if (max == left) max = min;
        swap(&arr[right], &arr[max]);
        left++;
        right--;
    }
}

这个优化版本的选择排序在每次迭代中同时找出最小和最大元素，可以减少约一半的比较次数。虽然时间复杂度仍然是 O(n²)，但在实际运行中可以带来一定的性能提升。

总结

选择排序是一种简单直观的排序算法，通过不断选择未排序部分的最小元素，并将其放到已排序部分的末尾来实现排序。尽管它的时间复杂度为 O(n²)，不适合大规模数据排序，但对于初学者来说，选择排序是理解排序算法基本原理的一个不错的起点。

你可能还想关注其它 9 种排序算法：

声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。

新手在线学习编程的网站，专注于分享优质精品课程。您的下一套教程，何必是书籍。

编程笔记 | 版权证书 | 关于我们 | 联系我们

C语言选择排序（附带源码和解析）

选择排序的基本原理

C语言实现选择排序

选择排序的性能以及优缺点

优化选择排序

总结

相关文章

精选内容