简单选择排序算法(C语言详解版)

 
该算法的实现思想为:对于具有 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