C语言每日练习之选择排序

C语言每日练习之选择排序

选择排序算法简介

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思路是在未排序的数列中，从前往后依次选择最小的数，和第一个数进行交换，然后在剩余的数列中从前往后选择最小的数，与第二个数进行交换，直到选择到最后一个数为止。

选择排序的时间复杂度为O(n²)，属于较慢的排序算法，但是它的实现简单易懂，不需要额外的空间，因此可以用来排序小规模的数据。

选择排序算法实现

以下是选择排序的C语言实现：

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

以上代码中，a数组表示待排序的数列，n表示数列的长度。在外层循环中，依次选择数列中的第i个元素，并记录其索引为min_index。在内层循环中，从i+1到n遍历数列，找到最小值的索引，并将最小值的索引赋给min_index。如果min_index不等于i，说明第i个元素不是最小的，需要将a[i]和a[min_index]进行交换。

选择排序算法示例

以下是使用选择排序对数列进行排序的示例。

示例1：对整数数组进行排序

#include <stdio.h>

void selection_sort(int a[], int n);

int main()
{
    int a[] = {30, 50, 10, 20, 40};
    int n = 5;
    selection_sort(a, n);

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

    return 0;
}

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

输出结果：

sorted array:
10 20 30 40 50

示例2：对字符串数组进行排序

#include <stdio.h>
#include <string.h>

void selection_sort(char* a[], int n);

int main()
{
    char* a[] = {"bbb", "aaa", "ddd", "ccc"};
    int n = 4;
    selection_sort(a, n);

    printf("sorted array:\n");
    for (int i = 0; i < n; i++) {
        printf("%s ", a[i]);
    }
    printf("\n");

    return 0;
}

void selection_sort(char* a[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        int min_index = i;
        for (j = i + 1; j < n; j++) {
            if (strcmp(a[j], a[min_index]) < 0) {
                min_index = j;
            }
        }
        if (min_index != i) {
            char* temp = a[min_index];
            a[min_index] = a[i];
            a[i] = temp;
        }
    }
}

输出结果：

sorted array:
aaa bbb ccc ddd

以上实例中，分别对整数数组和字符串数组进行了选择排序。字符串数组的排序使用了strcmp函数来进行字符串的比较。