简单选择排序

简单选择排序：在每一轮循环中（第n轮），从剩下的元素中遍历，选出本轮的最小元素，放到第n个位置。循环完n - 1轮后，顺序表中的元素即有序。

简单选择排序的平均时间复杂度为O(n^2)。

// 简单选择排序
#include <stdio.h>

#define N 10 // 数组最大值

// 顺序表结构
typedef struct {
    int value[N + 1]; // 顺序表中的值
    int length; // 顺序表长度
} SqList;

/**
 * 交换顺序表L中i和j元素的值
 * @param L 顺序表
 * @param i 元素值
 * @param j 元素值
 */
void swap(SqList *L, int i, int j) {
    int temp = L->value[i];
    L->value[i] = L->value[j];
    L->value[j] = temp;
}

/**
 * 初始化顺序表
 * @param L 顺序表
 * @param d 存初始值的数组
 */
void InitSqList(SqList *L, int *d) {
    int i;

    for (i = 0; i < N; ++i) {
        L->value[i + 1] = d[i];
    }
    L->length = N;
}

/**
 * 遍历顺序表中元素的值
 * @param L 顺序表元素
 */
void Print(SqList L) {
    int i;

    printf("顺序表中的值为：");
    for (i = 1; i < L.length; i++) {
        printf("%d, ", L.value[i]);
    }
    printf("%d", L.value[i]);
    printf("\n");
}

/**
 * 简单选择排序
 * @param L 顺序表
 */
void SelectSort(SqList *L) {
    int i, j;
    int min; // 用来记录每轮循环获取的最小值的下标

    for (i = 1; i < L->length; i++) {
        min = i; // 设置本轮最小值元素的下标

        for (j = i + 1; j < L->length; j++) {
            if (L->value[min] > L->value[j]) { // 如果当前元素的值小于最小值元素
                min = j; // 记录当前元素的下标
            }
        }

        // 本轮最小值元素的下标不等于初始值，代表有比初始值更小的元素
        if (i != min) {
            swap(L, i, min); // 将本轮的最小值交换的对应位置
        }
    }
}

int main() {
    int d[N] = {50, 10, 90, 30, 70, 40, 80, 60, 20, 102}; // 存初始值的数组
    SqList L; // 顺序表

    InitSqList(&L, d); // 初始化顺序表
    printf("刚进行初始化后");
    Print(L); // 遍历顺序表

    SelectSort(&L); // 对顺序表进行简单选择排序
    printf("简单选择排序后");
    Print(L); // 遍历顺序表

    return 0;
}

运行结果