简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，需要移动记录的次数最多为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 = 0i <10i ++ ) scanf("%d",&a[ i ])/*输入10个数，比武报名，报名费用10000￥ ^_^*/
for ( i = 0i <9i ++ )
for ( j = i + 1j <10j ++)
if ( a[ i ] <a[ j ] ) { t = a[ i ]a[ i ] = a[ j ]a[ j ] = t} /*打不过就要让出头把交椅，不过a[ i ]比较爱面子，不好意思见 a[ j ]，让t帮忙*/
for( i = 0i <10i ++) 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 = 0i <10i ++ ) scanf("%d",&a[ i ])/*输入10个数，比武报名，报名费用10000￥ ^_^*/
for ( i = 0i <9i ++ ) /*10个数，所以只需比9次*/
{
k = i/*裁判AND记者实时追踪报道比赛情况*/
for ( j = i + 1j <10j ++)
if ( a[ k ] <a[ j ] ) k = j/*使a[k]始终表示已比较的数中的最大数*/
if （k！=i）
{ t = a[ i ]a[ i ] = a[ k ]a[ k ] = t} /* t 发放奖品* /
}
for( i = 0i <10i ++) printf("%4d",a[ i ])/*显示排序后的结果*/
return 0
}
由小到大时：
int main(void)
{
int a[10]
int i,j,t,k
for ( i = 0i <10i ++ ) scanf("%d",&a[ i ])/*输入10个数，比武报名，报名费用10000￥ ^_^*/
for ( i = 0i <9i ++ )
{
k = i/*裁判AND记者实时追踪报道比赛情况*/
for ( j = i + 1j <10j ++)
if ( a[ k ] >a[ j ] ) k = j
if （k！=i）
{ t = a[ i ]a[ i ] = a[ k ]a[ k ] = t}/* t 发放奖品*/
}
for( i = 9i >= 0i --) 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=0i<pData.lengthi++){ //随机生成10个排序数
Integer a =random.nextInt(100)
pData[i]= a
System.out.print(pData[i]+" ")
}
System.out.println()
pData=Choose(pData)
for(int i=0i<pData.lengthi++){
System.out.print(pData[i]+" ")
}
System.out.println()
}
public static int[] Choose(int[] pData){
System.out.println()
for (int i = 0i <pData.lengthi++) {
for (int j = ij <pData.lengthj++) {
if(pData[j]<pData[i]){
int a=pData[j]
pData[j]=pData[i]
pData[i]=a
}
}
}
return pData
}
.example-btn{color:#fffbackground-color:#5cb85cborder-color:#4cae4c}.example-btn:hover{color:#fffbackground-color:#47a447border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%color:#000background-color:#f6f4f0background-color:#d0e69cbackground-color:#dcecb5background-color:#e5eeccmargin:0 0 5px 0padding:5pxborder:1px solid #d4d4d4background-image:-webkit-linear-gradient(#fff,#e5eecc 100px)background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4emwidth:98%background-color:#fffpadding:5pxborder:1px solid #d4d4d4font-size:110%font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospaceword-break:break-allword-wrap:break-word}div.example_result{background-color:#fffpadding:4pxborder:1px solid #d4d4d4width:98%}div.code{width:98%border:1px solid #d4d4d4background-color:#f6f4f0color:#444padding:5pxmargin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px autofont:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospacewhite-space:pre-wrapword-break:break-allword-wrap:break-wordborder:1px solid #dddborder-left-width:4pxpadding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序辩升铅、快速排序、堆排序、基数排序等。以下是选择排序算法：
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候，数据规模越笑纤小越好。唯一的好处可能就是不占用额外的内存空间了吧。
1. 算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排携好序序列的末尾。
重复第二步，直到所有元素均排序完毕。
2. 动图演示
代码实现 JavaScript 代码实现 实例function selectionSort ( arr ) {
var len = arr. length
var minIndex , temp
for ( var i = 0 i
#include<stdio.h>int main(){
int n,k,i,j,m
int a[100]
scanf("%d",&n)
for(i=0i<ni++){
scanf("%d",&a[i])
}
for(i=0i<渣侍n-1i++){
for(j=i+1j<nj++){
if(a[i]>a[j]){
k=a[j]
a[j]=a[i]
a[i]=k
}
}
}
for(i=0i<猛或ni++){
printf("%d "枝梁伍,a[i])
}
return 1
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）