首页 > 试题广场 >

选择排序

[编程题]选择排序
  • 热度指数:441 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
排序是处理很多问题的预处理部分。
之前的题目中,数值范围比较小,通过记录每个数值出现的次数,再按照数值从小到大,该数值出现多少次,就输出多少个。
这种方法,不适用于数值范围很大的情况,因为数组无法开。不能开出A[100000000]这样1亿大小的数组,数组的总大小要控制在3千万以内。
除了计数排序,还有很多种排序方法。下面来介绍一种简单的排序算法,选择排序。
选择排序的思想是:从前往后依次得到每个位置上的数。对于第i个位置,在[i+1,n]这些位置中,找到一个最小值,记录它的位置k。把A[i]A[k]的值进行交换。

for(i=1;i<=n;i++){//依次得到每个位置上的数

k=i;//先设这个位置上的数不动,就是最小的那个

for(j=i+1;j<=n;j++)//在[i+1,n]这个区间找最小值的位置

if(A[j]<a[k])k=j;

if(k!=i){//交换A[i]和A[k]

t=A[i];

a[i]=A[k];

a[k]=t;

}

}



输入描述:
第一行一个整数n,表示要排序的数个数。
第二行n个元素,表示待排序的元素。


输出描述:
输出n个数字,表示排序后的数字。
示例1

输入

5
-1 2 1 4 3

输出

-1 1 2 3 4

备注:
数据范围:,序列中的元素范围在之间。

问题信息

上传者:小小
难度:
4条回答 2380浏览

热门推荐

通过挑战的用户

选择排序