【数据结构】直接选择排序算法

wander

直接选择排序的效率与初始状态无关,即无最好最坏的情况.时间复杂度为O(n*n),不是稳定的排序算法
#include<stdio.h>
struct node
{
    int key;
};
typedef struct node DataType;      //DataType是struct node的别名
int Sel_sort(DataType Ar[],int n);      //声明直接选择排序算法
int main(void)
{
    int n,i;
    DataType array[20];
    printf("Input the length of the array <<20>:");
    scanf("%d",&n);
    for(i=0; i<n; i++)                 //输入数组
    {
        printf("Input %d datas:",i+1);
        scanf("%d",&array[i]);
    }
    printf("\n The array are:");
    for(i=0; i<n; i++)
    {
        printf("%4d",array[i]);              //输入的数组显示
    }
    Sel_sort(array,n);          //调用排序算法
    printf("\n The array after Sel_sort are:");
    for(i=0; i<n; i++)             //输出排序后的算法结果
    {
        printf("%4d",array[i]);
    }
    return(0);
}
int Sel_sort(DataType Ar[],int n)          //直接选择排序算法
{
    DataType temp;
    int i,small,j;
    for(i=0; i<=n-1; i++)             //i控制n-1趟扫描
    {
        small=i;                        //用变量small记住当前最小排序码的位置
        for(j=i+1; j<n; j++)            //j控制这趟扫描的比较范围
            if(Ar[j].key<Ar[small].key)      //如果发现更小者,随时修改small的值
                small=j;
        if(small!=i)                               //small与比较范围首元素下标不同,则交换
        {
            temp=Ar[i];                 //交换是利用临时变量temp进行的
            Ar[i]=Ar[small];
            Ar[small]=temp;
        }
    }
}