TGCode

关注互联网技术

简单选择排序算法（C语言详解版）

2021年1月17日   |   by tgcode

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

例如对无序表{56，12，80，91，20}采用简单选择排序算法进行排序，具体过程为：

  • 第一次遍历时，从下标为 1 的位置即 56 开始，找出关键字值最小的记录 12，同下标为 0 的关键字 56 交换位置：


    %title插图%num
     
  • 第二次遍历时，从下标为 2 的位置即 56 开始，找出最小值 20，同下标为 2 的关键字 56 互换位置：


    %title插图%num
     
  • 第三次遍历时，从下标为 3 的位置即 80 开始，找出最小值 56，同下标为 3 的关键字 80 互换位置：


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


    %title插图%num
     
  • 到此简单选择排序算法完成，无序表变为有序表。

简单选择排序的实现代码为：

#include 
#include 
#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+1length) {
        if (L->r[min].key>L->r[i+1].key) {
            min=i+1;
        }
        i++;
    }
    return min;
}
//简单选择排序算法实现函数
void SelectSort(SqList * L){
    for (int i=0; ilength; 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; ilength; i++) {
        printf("%d ",L->r[i].key);
    }
    return 0;
}

运行结果：

13 27 38 49 49 65 76 97

相关推荐: 树的孩子兄弟表示法

前面讲解了存储普通树的双亲表示法和孩子表示法，本节来讲解最后一种常用方法——孩子兄弟表示法。 图 1 普通树示意图 树结构中，位于同一层的节点之间互为兄弟节点。例如，图 1 的普通树中，节点 A、B 和 C 互为兄弟节点，而节点  D、E 和 F 也互为兄弟节…

Tags: