简单选择排序算法 C语言解析版

发布时间：2022-07-10 11:49 所属栏目：51 来源：互联网

导读：该算法的实现思想为：对于具有 n 个记录的无序表遍历 n-1 次，第 i 次从无序表中第 i 个记录开始，找出后序关键字中最小的记录，然后放置在第 i 的位置上。例如对无序表{56，12，80，91，20}采用简单选择排序算法进行排序，具体过程为：第一次遍历时，从下

　　该算法的实现思想为：对于具有 n 个记录的无序表遍历 n-1 次，第 i 次从无序表中第 i 个记录开始，找出后序关键字中最小的记录，然后放置在第 i 的位置上。

　　例如对无序表{56，12，80，91，20}采用简单选择排序算法进行排序，具体过程为：
　　第一次遍历时，从下标为 1 的位置即 56 开始，找出关键字值最小的记录 12，同下标为 0 的关键字 56 交换位置：

　　第二次遍历时，从下标为 2 的位置即 56 开始，找出最小值 20，同下标为 2 的关键字 56 互换位置：
　　
　　第三次遍历时，从下标为 3 的位置即 80 开始，找出最小值 56，同下标为 3 的关键字 80 互换位置：

　　第四次遍历时，从下标为 4 的位置即 91 开始，找出最小是 80，同下标为 4 的关键字 91 互换位置：

　　到此简单选择排序算法完成，无序表变为有序表。

　　简单选择排序的实现代码为：
　　#include <stdio.h>
　　#include <stdlib.h>
　　#define MAX 9
　　//单个记录的结构体
　　typedef struct {
　　    int key;
　　}SqNote;
　　//记录表的结构体
　　typedef struct {
　　    SqNote r[MAX];
　　    int length;
　　}SqList;
　　//交换两个记录的位置
　　void swap(SqNote *a,SqNote *b){
　　    int key=a->key;
　　    a->key=b->key;
　　    b->key=key;
　　}
　　//查找表中关键字的最小值
　　int SelectMinKey(SqList *L,int i){
　　    int min=i;
　　    //从下标为 i+1 开始，一直遍历至最后一个关键字，找到最小值所在的位置
　　    while (i+1<L->length) {
　　        if (L->r[min].key>L->r[i+1].key) {
　　            min=i+1;
　　        }
　　        i++;
　　    }
　　    return min;
　　}
　　//简单选择排序算法实现函数
　　void SelectSort(SqList * L){
　　    for (int i=0; i<L->length; i++) {
　　        //查找第 i 的位置所要放置的最小值的位置
　　        int j=SelectMinKey(L,i);
　　        //如果 j 和 i 不相等，说明最小值不在下标为 i 的位置，需要交换
　　        if (i!=j) {
　　            swap(&(L->r[i]),&(L->r[j]));
　　        }
　　    }
　　}
　　int main() {
　　    SqList * L=(SqList*)malloc(sizeof(SqList));
　　    L->length=8;
　　    L->r[0].key=49;
　　    L->r[1].key=38;
　　    L->r[2].key=65;
　　    L->r[3].key=97;
　　    L->r[4].key=76;
　　    L->r[5].key=13;
　　    L->r[6].key=27;
　　    L->r[7].key=49;
　　    SelectSort(L);
　　    for (int i=0; i<L->length; i++) {
　　        printf("%d ",L->r[i].key);
　　    }
　　    return 0;
　　}
　　运行结果：
　　13 27 38 49 49 65 76 97

（编辑：ASP站长网）