首页 > 代码库 > 2016_12_29(选择排序)
2016_12_29(选择排序)
选择排序的基本思想是：每一趟从待排序的记录中挑选出关键字最小的记录，按顺序放在已排好的子文件的最后，直到全部记录排好为止。（从小到大的排序）
直接选择排序：从待排序的所有记录中，挑选出关键字最小的记录，把它与第一个记录交换，然后在其余的记录中再选择出关键字最小的记录与第二个记录交换，如此重复下去，直到所有记录排序完成。
void selectsort(RECORDNOD r[], int n)
{
int i,j;
int k;//从头到尾，挨个记录待排的关键字（记录）的位置
int tmp;
for(i=0;i<=n-2;i++)//从第一个记录到倒数第二个记录
{
k=i;
for(j=i+1;j<=n-1;j++)//从第i个记录到最后一个记录
{
if(r[j].key<r[k].key)//选择出待排序记录中最小的那个记录
k=j;
}
if(k!=i)//插入到已排好序的数据的最后
{
tmp=r[i];
r[i]=r[j];
r[j]=tmp;
}
}
}
算法复杂度分析：
总的比较次数为O(n^2);
当初始文件为正序时，移动次数为0；
当初始文件与要求的次序相反时候，总的移动次数为3(n-1);直接选择排序的平均时间复杂度为O（n^2）;
2016_12_29(选择排序)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。