首页 > 数据算法> 详细内容
选择排序
日期:2020-03-13 

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

以下为简单选择排序的存储状态,其中大括号内为无序区,大括号外为有序序列:

初始序列:{49 27 65 97 76 12 38}

  第1趟:1249交换:12{27 65 97 76 49 38}

  第2趟:27不动 :12 27{65 97 76 49 38}

  第3趟:6538交换:12 27 38{97 76 49 65}

  第4趟:9749交换:12 27 38 49{76 97 65}

  第5趟:7665交换:12 27 38 49 65{97 76}

  第6趟:9776交换:12 27 38 49 65 76 97 完成


再举个例子

原始序列:49、38、65、97、76、13、27、49

1)在进行选择排序过程中分成有序和无序两个部分,开始都是无序序列

结果:49、38、65、97、76、13、27、49

2)从无序序列中取出最小的元素13,将13同无序序列第一个元素交换,此时产生仅含一个元素的有序序列,无序序列减一

结果:{13、}   {38、65、97、76、49、27、49}

3)从无序序列中取出最小的元素27,将27同无序序列第一个元素交换,此时产生仅两个元素的有序序列,无序序列减一

结果:{13、27、}   {65、97、76、49、38、49}

4)从无序序列中取出最小的元素38,将38同无序序列第一个元素交换,此时产生含三个元素的有序序列,无序序列减一

结果:{13、27、38、}   {97、76、49、65、49}

5)从无序序列中取出最小的元素49,将49同无序序列第一个元素交换,此时产生含四个个元素的有序序列,无序序列减一

结果:{13、27、38、49、}   {76、97、65、49}

6)从无序序列中取出最小的元素49,将49同无序序列第一个元素交换,此时产生含五个元素的有序序列,无序序列减一

结果:{13、27、38、49、49、}   {97、65、76}

7)从无序序列中取出最小的元素65,将65同无序序列第一个元素交换,此时产生含六个元素的有序序列,无序序列减一

结果:{13、27、38、49、49、65}   {97、76}

8)从无序序列中取出最小的元素76,将76同无序序列第一个元素交换,此时产生含七个元素的有序序列,无序序列减一

结果:{13、27、38、49、49、65、76、}   {97}

9)最后一个元素肯定是最大元素,无序排序直接生产一个有序的序列

void px (int a[],int n)
{int i,j,temp,k;
for(i=0;i<n-1;i++)
{k=i;
for(j=i+1;j<n;j++)
if(a[k]>a[j])
k=j;
if(k!=i)
{temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
main()
{int a[5],i;
for(i=0;i<5;i++)
scanf("%d",&a[i]);
px(a,5);
for(i=0;i<5;i++)
printf("%d ",a[i]);
}