选择排序

选择排序的排序方法

通过 \(2\) 重循环遍历数组，发现有不符合顺序的数对，就交换他们.

时间复杂度

选择排序的最好时间复杂度: \(\Theta (n^2).\)

选择排序的平均时间复杂度: \(\Theta (n^2).\)

选择排序的最坏时间复杂度: \(\Theta (n^2).\)

稳定性

选择排序是不稳定的排序算法.

示例代码

这里以降序为例.

//降序 
#include <iostream>
#include <algorithm> // 调用 swap 函数 
using namespace std;
int a[310], n;
int main() {
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) { // a[i]与它之后的每一个数字比较 
			if(a[i] > a[j]) // 不是降序的数对 
				swap(a[i], a[j]); // 交换 
		}
	}
	for(int i = 0; i < n; i++)
		cout << a[i] << " ";
	return 0;
}

优化

因为我们每次都是都在交换，所以，我们可以找在 \(a_i\) 后面最小的数，进行交换. ( \(1 \le i \le n\) ).

\(n\) 为数组大小.

优化代码

//降序 
#include <iostream>
#include <algorithm>
using namespace std;
int a[310], n, zz; // zz-指针 指向一个位置 
int main() {
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < n; i++) { // 从数组开头循环到 n-2,等价于 i<n-1 
		zz = i; // 指针的位置先指向 i 
		for(int j = i + 1; j < n; j++) { // a[i]与它之后的每一个数字比较 
			if(a[zz] > a[j]) zz = j; // 若找到了比当前数字更小的数，zz指向这个更小的数的位置 
		}
		if(zz != i) swap(a[i], a[zz]); // 如果zz的位置有改动，交换a[i]和最小数 
	}
	for(int i = 0; i < n; i++)
		cout << a[i] << " ";
	return 0;
}