选择排序法 百科内容来自于: 百度百科

基本思想

选择排序的基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序
简单选择排序的基本思想:第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趟:12与49交换:12 { 27 65 97 76 49 38 }
第2趟:27不动 :12 27 { 65 97 76 49 38 }
第3趟:65与38交换:12 27 38 { 97 76 49 65 }
第4趟:97与49交换:12 27 38 49 { 76 97 65 }
第5趟:76与65交换:12 27 38 49 65 { 97 76 }
第6趟:97与76交换:12 27 38 49 65 76 97 完成
简单选择排序的算法具体描述如下:
void SelectSort(RecordType r[], int length) /*对记录数组r做简单选择排序,length为待排序记录的个数*/
{
for ( i=1 ; i< length; i++) //n-1趟排序
{
int index=i; //假设index是最小的
for ( j=i+1 ; j<= length ; j++)  //查找最小记录的位置
if (r[j].key < r[index].key )
index=j;
if ( index!=i)  //若无序区第一个元素不是无序区中最小元素,则进行交换
{ r[0]= r[i]; r[i]= r[index]; r[index]=r[0]; } //利用r[0]作为临时空间
}
}

算法

简单选择排序算法分析:在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,需要移动记录的次数最多为3(n-1)( 此情况中待排序记录并非完全逆序,给完全逆序记录排序的移动次数应为(n/2)*3,其中n/2向下取整)。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为O(n2)。
选择排序法 是对 定位比较交换法(也就是冒泡排序法) 的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解,设有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]以后,排序就完成了。
下面给大家一个例子:
int main(void)
{
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 ]); /*显示排序后的结果*/
return 0;
}
好啦,啰嗦了半天总算把定位比较排序法讲完了,这个方法不错,容易理解,就是有点麻烦,一把椅子换来换去,哎~
所以就有了下面的选择排序法,开始的时候椅子谁也不给,放在一边让大家看着,找个人k记录比赛结果,然后发椅子。具体来讲呢就是,改进定位比较排序法,但是这个改进只是一部分,比较的次数没变,该怎么打还是怎么打,就是不用换椅子了。每次外循环先将定位元素的小标i值记录到K,认为a[k]是最大元素其实k=i还是a[ i ]最大,a[k]与后面的元素一一比较,该交换的也是也不换,就是把K的值改变一下就完了,最后在把a[k]与a[ i ]交换,这样a就是最大的元素了。然后进入下一轮的比较。选择排序法与定位比较排序法相比较,比的次数没变,交换的次数减少了。
下面也写个例子:
由大到小时:
int main(void)
{
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;
if (k!=i)
{ t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t;} /* t 发放奖品* }
}
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*显示排序后的结果*/
return 0;
}
由小到大时:
int main(void)
{
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;
if (k!=i)
{ t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t; }/* t 发放奖品*/
}
for( i = 9; i >= 0; i --) printf("%4d",a[ i ]); /*显示排序后的结果*/
return 0;
}
java选择排序法代码 public static void main(String[] args) {
Random random=new Random();
int[] pData=new int[10];
for(int i=0;i<pData.length;i++){ //随机生成10个排序数
Integer a =random.nextInt(100);
pData[i]= a;
System.out.print(pData[i]+" ");
}
System.out.println();
pData=Choose(pData);
for(int i=0;i<pData.length;i++){
System.out.print(pData[i]+" ");
}
System.out.println();
}
public static int[] Choose(int[] pData){
System.out.println();
for (int i = 0; i < pData.length; i++) {
for (int j = i; j < pData.length; j++) {
if(pData[j]<pData[i]){
int a=pData[j];
pData[j]=pData[i];
pData[i]=a;
}
}
}
return pData;
}
$firstVoiceSent
- 来自原声例句
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定