选择排序算法C/C++代码图文讲解

本篇主要简单介绍选择排序，并且通过图片和代码的形式帮助大家理解应用。

（1）什么是选择排序？

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的中数据元素选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

（2）选择排序思路

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

（3）排序过程

例：定义一个数组 int a[8] = {9，3，7，2，6，1，5，8}，要求利用选择排序的方法将数组从小到大排序。

排序的次数：因为每排好一个元素，那么所需要排的元素个数减一，直到排到倒数第二个元素停止，将倒数第二个元素也排好后，整体数组排序就完成了。所以排序的次数 = 元素个数 - 1。(冒泡排序的排序次数与该排序的排序次数计算方法相同)

第一次排序：假设首元素作为整体元素数据最小值，然后从该元素的后一个元素开始每个元素都与该最小值进行比较，假如有比该元素小的值，就用一个变量去记住下标值，最后比较完成后，把两个元素互换位置即可。

第一次排序结果：{1，3，7，2，6，9，5，8}

第二次排序：因为第一次排序选择的是将首元素作为最小值，最终经过互换位置，首元素排序完成，第二次排序就不需要排序首元素，只需要排序除首元素以外的元素，然后在依照第一次排序的原理进行排序。

第二次排序结果：{1，2，7，3，6，9，5，8}

然后根据第一次排序和第二次排序的原理，最终的排序结果为：{1，2，3，5，6，7，8，9}

（4）C语言代码实现如下：

#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=9;
    L->r[1].key=3;
    L->r[2].key=7;
    L->r[3].key=2;
    L->r[4].key=6;
    L->r[5].key=1;
    L->r[6].key=5;
    L->r[7].key=8;
    SelectSort(L);
    for (int i=0; i<L->length; i++) {
        printf("%d ",L->r[i].key);
    }
    return 0;
}

如果我们编译并运行上述程序，那么它应该产生以下结果：

1 2 3 5 6 7 8 9