R6-2 简单选择排序 分数 15 作者 DS课程组 单位 临沂大学 本题要求实现简单选择排序函数，待排序列的长度1<=n<=1000。 函数接口定义： void SelectSort(SqList L); 其中L是待排序表，使排序后的数据从小到大排列。 ###类型定义： typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; 裁判测试程序样例： #include<stdio.h> #include<stdlib.h> typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ void SelectSort(SqList L); int main() { SqList L; int i; CreatSqList(&L); SelectSort(L); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0; } /*你的代码将被嵌在这里 */ 输入样例： 第一行整数表示参与排序的关键字个数。第二行是关键字值 例如： 10 5 2 4 1 8 9 10 12 3 6 输出样例： 输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。 1 2 3 4 5 6 8 9 10 12

以下是简单选择排序的实现过程，主要思路是每次从未排序的序列中选择一个最小的元素，将其放到已排序的序列末尾。时间复杂度为 $O(n^2)$。

void SelectSort(SqList L) {
    int i, j, min_idx;
    for (i = 1; i < L.Length; i++) {
        min_idx = i;
        for (j = i + 1; j <= L.Length; j++) {
            if (L.elem[j] < L.elem[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            // 交换 L.elem[i] 和 L.elem[min_idx]
            KeyType temp = L.elem[i];
            L.elem[i] = L.elem[min_idx];
            L.elem[min_idx] = temp;
        }
    }
}

主函数中调用该函数即可。

int main() {
    SqList L;
    int i;
    CreatSqList(&L);
    SelectSort(L);
    for (i = 1; i <= L.Length; i++) {
        printf("%d ", L.elem[i]);
    }
    printf("\n");
    return 0;
}