现在的位置: 首页 > 综合 > 正文

选择排序法

2013年03月02日 ⁄ 综合 ⁄ 共 1400字 ⁄ 字号 评论关闭
选择排序法 是对 定位比较交换法 的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解,设有10个数分别存在数组元素a[0]~a[9]中。定位比较交换法是由 大到小依次定位a[0]~a[9]中恰当的值(和武林大会中的比武差不多),a[9]中放的自然是最小的数。如定位a[0],先假定a[0]中当前值是最 大数,a[0]与后面的元素一一比较,如果a[4]更大,则将a[0]、a[4]交换,a[0]已更新再与后面的a[5]~a[9]比较,如果a[8]还 要大,则将a[0]、a[8]交换,a[0]又是新数,再与a[9]比较。一轮比完以后,a[0]就是最大的数了,本次比武的武状元诞生了,接下来从a [1]开始,因为状元要休息了,再来一轮a[1]就是次大的数,也就是榜眼,然后从a[2]开始,比出探花,真成比武大会了,当必到a[8]以后,排序就 完成了。
下面给大家一个例子:
mai()
{
    int a[10];
    int i,j,t;
    for ( i = 0; i < 10; i ++ )      scanf("%d",&a[ i ]);                 /*输入10个数,比武报名,报名费用10000¥ ^_^*/
    for ( i = 0; i < 9; i ++ )
         for ( j = i + 1; j < 10; j ++)
               if ( a[ i ] < a[ j ] )    { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; }   /*打不过就要让出头把交椅,不过a[ i ]比较爱面子,不好意思见 a[ j ],让t帮忙*/
    for( i = 0; i < 10; i ++)   printf("%4d",a[ i ]);   /*显示排序后的结果*/
}
好啦,罗嗦了半天总算把定位比较排序法讲完了,这个方法不错,容易理解,就是有点麻烦,一把椅子换来换去,哎~
所以就有了下面的选择排序法,开始的时候椅子谁也不给,放在一边让大家看着,找个人k记录比赛结果,然后发椅子。具体来讲呢就是,改进定位比较排序法,但 是这个改进只是一部分,比较的次数没变,该怎么打还是怎么打,就是不用换椅子了。每次外循环先将定位元素的小标i值记录到K,认为a[k]是最大元素其实 i=k还是a[ i ]最大,a[k]与后面的元素一一比较,该交换的也是也不换,就是把K的值改变一下就完了,最后在把a[k]与a[ i ]交换,这样a就是最大的元素了。然后进入下一轮的比较。选择排序法与定位比较排序法相比较,比的次数没变,交换的次数减少了。
下面也写个例子:
mai()
{
    int a[10];
    int i,j,t,k;
    for ( i = 0; i < 10; i ++ )      scanf("%d",&a[ i ]);                 /*输入10个数,比武报名,报名费用10000¥ ^_^*/
    for ( i = 0; i < 9; i ++ )
        { k = i;                                                                       /*裁判AND记者实时追踪报道比赛情况*/
         for ( j = i + 1; j < 10; j ++)
               if ( a[ k ] < a[ j ] )   k = j;
         t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t;                           /* t 发放奖品*/
        }
    for( i = 0; i < 10; i ++)   printf("%4d",a[ i ]);   /*显示排序后的结果*/
}

抱歉!评论已关闭.