Selection Sort

Question

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.

Input

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.

Output

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.

Constraints

1 ≤ N ≤ 100

Sample Input 1

6

5 6 4 2 1 3

Sample Output 1

1 2 3 4 5 6

4

Sample Input 2

6

5 2 4 6 1 3

Sample Output 2

1 2 3 4 5 6

3

Meaning

实现选择排序的过程，并且输出选择排序过程中的排序次数

Solution

简单选择排序，每次在第二层无序区中找出一个最小的数，放到第一层的下标i处。但是小标i也有可能是最小的数，所以也要来进行比较。

Coding

#include<iostream>
using namespace std;
void SelectionSort(int a[], int n ,int &sum) {
	int i, j, min;
	for ( i = 0; i < n-1; i++) {
		//第一层循环为无序区
		min = i;//k记录当前的下标，到时需要交换
		for ( j = i + 1; j < n; j++) {
			//第二层循环为有序区
			if (a[j] < a[min])
				min = j; //此时min便是最小的数
		}
		if (min != i) {
			//为了防止最小数有两个，即最外层for循环i是最小数，无序区也有一个最小数，这样交换过来排序便不再稳定
			swap(a[min], a[i]);
			sum++;
		}
	}
}
void Print(int a[], int n) {
	for (int i = 0; i < n; i++) {
		if (i > 0) cout << " ";
		cout << a[i];
	}
}
int main() {
	int n, sum = 0;
	cin >> n;
	int a[105];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	SelectionSort(a, n, sum);
	Print(a, n);
	cout << endl << sum << endl;
}

Summary

插入排序能够较快的处理相对有序的数据，冒泡排序中的交换次数可以体现数列的错乱程度，

​

废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权

转载请注明原文链接：Selection Sort