数据结构 简单选择排序（C语言实现）

       选择排序的基本思想：每一趟在n-i+1(i=1,2,3,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。

算法思想

 

      第一趟简单选择排序时，从第一个记录开始，通过n-1 次关键字比较，从n 个记录中选出关键字最小的记录，并和第一个记录进行交换。

      第二趟简单选择排序时，从第二个记录开始，通过n-2 次关键字比较，从n -1个记录中选出关键字最小的记录，并和第二个记录进行交换。

      ......

      第i趟简单选择排序时，从第i个记录开始，通过n-i 次关键字比较，从n - i + 1个记录中选出关键字最小的记录，并和第i个记录进行交换。

      如此反复，经过n-1 趟简单选择排序，将第n-1 个记录排到位，剩下一个最小记录直接在最后，所以共需进行n-1 趟简单选择排序。

源代码

#include<stdio.h>
 
typedef int KeyType;
 
typedef struct
{
    KeyType key;
}RecordType;
 
void SelectSort(RecordTyper[],int length)     //简单选择排序
{
    
    int x;
    //假设待排序列有n个数，从第一个数开始依次与其后面的数比较，需要比较n-1次
    for (int i = 1; i <=length-1;i++)
    {
        int k = i;
        for (int j = i + 1; j <=length; j++) //j从2开始
        {
            if (r[j].key <r[k].key)
            {
                k = j;
            }
        }
        if (k != i)          //当r[j].key>=r[k].key将r[k]的值借助中间变量X与x[i]的值交换
        {
            x = r[i].key;              //r[i].key为最小数
            r[i].key = r[k].key; 
            r[k].key = x;
 
        }
    }
}
 
void ShowResult(RecordType*r,int length)       //输出结果
{
    for (int i = 1; i <=length; i++)
    {
        printf("%d\t", r[i]);
    }
}
int main()
{
    RecordType r[] = { 0, 8, 2, 9, 7, 3, 6, 4, 5, 1, 0 };
    int length = sizeof(r) / sizeof(r[0]) - 1;
    SelectSort(r, length);
    ShowResult(r,length);
    printf("\n");
    return  0;
}