C语言-数据结构-选择排序-源代码

待我称王封你为后i 2022-07-13 14:29 134阅读 0赞

**1. 基本思想及时间复杂度**

简单选择排序的基本思想：第1趟，在待排序记录r\[1\]~r\[n\]中选出最小的记录，将它与r\[1\]交换；第2趟，在待排序记录r\[2\]~r\[n\]中选出最小的记录，将它与r\[2\]交换；以此类推，第i趟在待排序记录r\[i\]~r\[n\]中选出最小的记录，将它与r\[i\]交换，使有序序列不断增长直到全部排序完毕。

选择排序时间复杂度为O（n^2）.

**2. 源代码**

#include<stdio.h>
    
    void selectsort(int a[], int n)
    {
        int i, j, min, temp, c1=0, c2=0;
        for(i=0;i<n;i++)
        {
            min=i;
            for(j=i+1;j<n;j++)//寻找最小的值
            {
                c1++;
                if(a[j]<a[min])
                {
                    min=j;
                }
            }
            if(min!=i)//如果最小的值不是i,则交换
            {
                temp=a[i];
                a[i]=a[min];
                a[min]=temp;
                c2++;
            }
        }
        printf("总计数据交换%d次, 访问数组%d次\n\n", c2, c1);
    }
    
    int main(void)
    {
        int i;
        int a[10]={5,2,6,0,3,9,1,7,4,8};
        printf("排序前：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        selectsort(a, 10);
        printf("排序后：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        return 0;
    }

运行结果如下图：

![Center][]

[Center]: /images/20220713/dd6cb18f6fdd46cdbadc355fd8136ad1.png