排序算法---选择排序

原创不易，转载请注明出处。欢迎点赞收藏~

选择排序是一种简单直观的排序算法，其基本思想是每次从待排序的元素中选取最小（或最大）的元素，将其与未排序部分的第一个元素进行交换，从而逐步形成有序序列。

具体的过程如下：

1. 首先，在待排序序列中找到最小（或最大）的元素，记为a。
2. 将a与待排序序列的第一个元素进行交换。
3. 接着，在剩余的未排序元素中找到最小（或最大）的元素，记为b。
4. 将b与待排序序列的第二个元素进行交换。
5. 重复上述步骤，直到所有元素都排列完毕。

选择排序的时间复杂度为O(n^2)，其中n表示待排序序列的长度。由于需要进行n次查找最小（或最大）值的操作，每次查找需要比较n次，因此总共需要比较的次数为n*(n-1)/2。同时，需要进行n次交换操作，每次交换需要花费O(1)的时间。因此，选择排序的时间复杂度为O(n^2)。

选择排序的空间复杂度为O(1)，因为排序过程中只需要使用常数个临时变量来存储最小（或最大）值和交换元素位置时的临时变量。

需要注意的是，选择排序是一种不稳定的排序算法，即相等元素的相对位置可能会发生改变。

#include <stdio.h>

// 选择排序函数
void selection_sort(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;
        }

        // 将最小元素与当前元素交换位置
        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]);

    printf("排序前的数组: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    selection_sort(arr, n);

    printf("\n排序后的数组: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    putchar('\n');

    return 0;
}

在这个示例中，selection_sort函数实现了选择排序算法。它首先遍历整个数组，找到未排序部分的最小元素的索引，然后将最小元素与当前元素交换位置。通过不断重复这个过程，直到整个数组排序完成。
在main函数中，我们定义了一个整型数组arr并初始化了一些随机值。然后，我们调用selection_sort函数对数组进行排序，并输出排序后的结果。

运行这段代码，你可以看到以下输出：