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

妖狐艹你老母 2022-06-06 07:35 277阅读 0赞

选择排序的基本思想：每一趟在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;
    }