#1219. 【模板】选择排序

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: kawae

题目描述

排序是处理很多问题的预处理部分。 下面来介绍一种简单的排序算法, 选择排序

选择排序的思想是:从前往后依次得到每个位置上的数。对于第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个数字,表示排序后的数字。

样例

5
-1 2 1 4 3

-1 1 2 3 4

数据范围与提示

数据范围 1<=n<=1000 , 序列中的元素范围 [-1000000,1000000] ;