117 精讲精练 - 选择排序

主要内容

1. 选择步骤
2. 排列奇数
3. 排列数组

1. 选择排序步骤

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 3. 重复第二步，直到所有元素均排序完毕。

2. 排列奇数

题目描述 给定一个长度为n(不大于500)的正整数序列，请将其中所有的奇数取出，并按照升序输出； 输入 第一行为n。 第二行有n个正整数，中间用空格分开。 输出 以增序的方式输出基数序列。数据至少保证有一个奇数。 样例输入 10 1 3 2 6 4 9 8 7 10 5 样例输出 1 3 5 7 9 参考程序

#include < iostream >
#include < string >
using namespace std;
nt main(){
    //接收数据
    int accept[1001] = {0};
    int n;
    cin >> n;
    int i = 0;
    while(n--){
        //接收数据
        int num;
        cin >> num;
        //如果是奇数就存储下来,i存贮数据的长度
        if(num % 2 == 1){
            accept[i] = num;
            ++i;
        }
    }
    //进行选择排序
    for(int j = 0; j < i - 1; ++j){
        //记录当前最小值的下标
        int min = j;
        for(int k = j + 1; k < i; ++k){
            //找到更小的记录
            if(accept[min] > accept[k]){
                min = k;
            }
        }
        swap(accept[j], accept[min]);
    }
    //输出
    for(int j = 0; j < i; ++j){
        cout << accept[j] << ' ';
    }
    return 0;
}

2. 排列数组

题目描述 输入n整数，排序后并输出。 输入 第一行一个整数n，表示要排序的数个数。 第二行n个元素，表示待排序的元素。 数据范围：1≤n≤1000，序列中的元素范围在[-10^6,10^6]之间。 输出 输出n个数字，表示排序后的数字。 样例输入 5 -1 2 1 4 3 样例输出 -1 1 2 3 4 参考程序

#include < iostream >
using namespace std;
void selectSort(int *nums,int n)
{
    for(int i=0;i<n-1;i++)
    {
        int min=i;
        for(int j=i+1;j<n;j++)
        {
            if(nums[j]<nums[min])
            min=j;   //找出最小值
        }
        swap(nums[min],nums[i]);
    } 
 
}
int main()
{
    int nums[1001];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
    }
    selectSort(nums, n);
    for(int i=0;i<n;i++)
    {
       if(i != n - 1){
            cout << nums[i] << " ";
        } else {
            cout <<nums[i] << endl;
        }
    }
    return 0;
}