注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ocean's blog

平常心——可以寂寞,但不允许空虚

 
 
 

日志

 
 

排序算法之选择排序  

2009-05-30 15:28:10|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

版权所有,转载请注明:本文出自学与思编程网

选择排序应该是所有排序中最直接最简单的排序算法了,其基本思想是:首先在所有未排序元素序列中找到最小的元素并把这个元素与整个序列中的第一个元素交换,然后找出剩下的未排序序列中的最小元素与整个序列中的第二个元素交换,反复这一过程直到最后排序完成。我们还是以一个简单的整数升序排序为例看看其排序过程:

假定有一组待排序整数:3,5,2,1    现在我们要把这4个数按升序排列。

首先找到这四个元素中最小的1与第一个元素3交换,结果是:1,5,2,3

然后从第二个元素开始找到最小元素2与第二个元素5交换,结果是:1,2,5,3

再从第三个元素开始找到最小元素3与第三个元素5交换,结果是1,2,3,5

至此排序完成。

下面是选择排序的c语言代码

void selection_sort(int a[], int n)

{

int i, j;

int m;

int tmp;

for (i = 0; i < n - 1; i++) {

m = i;

for (j = i + 1; j < n; j++) {

if (a[j] < a[m]) {

m = j;

}

}

tmp = a[i];

a[i] = a[m];

a[m] = tmp;

}

}

下面简单的分析一下选择排序的时间复杂度。

看上面的代码,变量i循环了 n - 1 次,对每个i,j循环的次数为 n - (i + 1)次,即j的循环次数为:n - 1, n - 2, n - 3, …, 3, 2, 1. 这样j总共循环了1 + 2 + 3 + … + (n - 3) + (n - 2) + (n - 1) = (n - 1) * n / 2 = (n * n - n) / 2 次,这就是选择排序的比较次数。也样可知,选择排序的比较操作最坏,最好,平均时间复杂度均为n2。

版权所有,转载请注明:本文出自学与思编程网

  评论这张
 
阅读(91)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017