【数据结构与算法】【排序】简单选择排序的代码实现

深藏阁楼爱情的钟 2022-08-13 14:42 109阅读 0赞

简单选择排序是一种选择排序。

前提：数组元素a\[0\]用作哨兵或临时变量，a\[1\]~a\[n\]存放n个待排序的元素。

基本思想是：对于第i个元素，通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换。

代码实现：

// Filename: select_sort.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "public.h"
    
    // 简单选择排序
    // n个元素序列的各元素下标：[1, 2, ..., n-1, n], a[0]不使用
    // 对于第i个元素，通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换。
    // 入参n是待排序元素个数，下表从1开始
    void SelectSort(int a[], int n)
    {
        int i, j, min; // min是数组下标
    
        for (i = 1; i < n; i++)
        {
            min = i;
            for (j = i + 1; j <= n; j++)
            {
                if (a[j] < a[min]) min = j;
            }
    
            if (min != i) swap(&a[i], &a[min]);
        }
    
        return;
    }
    
    // 简单选择排序主函数
    int SelectSortMain()
    {
        int a1[12] = {0xFF, 3, 4, 5, 8, 9, 7, 6, 1, 0, 2, -1};
    
        printf("简单选择排序演示(a[0]是哨兵, 不参与排序): \n");
    
        printf("排序前：\n");
        printf("a1: ");
        PrintArray(a1, sizeof(a1) / sizeof(int));
        printf("\n");
    
        // 将从a1[1]到a1[10]共10个元素进行排序
        SelectSort(a1, 10);
    
        printf("排序后：\n");
        printf("a1: ");
        PrintArray(a1, sizeof(a1) / sizeof(int));
        printf("\n");
    
        return 0;
    }