教育改变生活

标题: 【数据结构】直接选择排序算法 [打印本页]

作者: wander 时间: 2021-1-21 11:28
标题: 【数据结构】直接选择排序算法
直接选择排序的效率与初始状态无关,即无最好最坏的情况.时间复杂度为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;
      }
}
}

欢迎光临教育改变生活 (http://193.112.175.132/discuz/)