Sort I-Selection Sort

题目描述

Write a program of the Selection Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode: SelectionSort(A)

1 for i = 0 to A.length-1 2     mini = i 3        for j = i to A.length-1 4           if A[j] < A[mini] 5               mini = j 6     swap A[i] and A[mini]

Note that, indices for array elements are based on 0-origin. Your program should also print the number of swap operations defined in line 6 of the pseudocode in the case where i ≠ mini.

输入

The first line of the input includes an integer N, the number of elements in the sequence. In the second line, N elements of the sequence are given separated by space characters.

输出

The output consists of 2 lines. In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character. In the second line, please print the number of swap operations.

题解

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[110];
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i = 1 ; i<=n ; i++){
cin>>a[i];
}

int ans = 0;
for(int i = 1 ; i<=n-1 ; i++){
    int min = a\[i\];
    int flag = i;
    for(int j = i+1 ; j<=n ; j++){
        if(min > a\[j\]){
            flag = j;
            min = a\[j\];
        }
    } 
    if(flag != i){
        swap(a\[flag\] , a\[i\] );
        ans++;
    }
}
for(int i = 1 ; i<=n ; i++){
    if(i == 1)
        cout<<a\[i\];
    else{
        cout<<" "<<a\[i\];
    }
}
cout<<endl;
cout<<ans<<endl;
return 0;

}