[C++知识库]C++简单排序——选择排序

今天我们来学习一种新的排序方法——选择排序。

上一次我们学习了一种简单的排序——冒泡排序。但有的人啊，他就是说：“冒泡排序太难记了！换一种！” 于是，无敌天才?我决定发一下我认为最好记的排序之一——选排。

选择排序：选出一个作为基本位置，然后再把位置的数和后面的依次比较，交换，将基本位置的数确定好，重复，直到完成排序。

文字看不懂，看看具体操作：将数列：4 9 2 8 6 ?从小到大排序。

第一步： 4 9 2 8?6? ? ? // 基本位置是第一位：4，开始比较。4＜9，不交换。

第二步： 2?9 4?8?6? ? ? // 接下来将 4?2?比较，交换。

第三步： 2 9 4 8?6? ? ? // 将 2 8?比较，不交换。

第四步： 2 9 4?8?6?? ? ?// 将 2 6?比较，不交换。

//现在完成了最小数放在最前面，用了4次比较，1次交换。

第五步： 2 4 9 8?6? ? ? // 基本位置是第二位：9，开始比较。4＜9，交换。

第六步： 2 4 9 8?6? ? ? // 将 4 8?比较，不交换。

第七步： 2 4 9 8?6? ? ? // 将 4 8?比较，不交换。

//我们已经将第2小数放到第2位，用了3次比较，1次交换。

第八步： 2 4 8?9 6? ? ? // 将 9 8?比较，交换。

第九步： 2 4 6?9?8? ? ?// 将 8?6?比较，交换。

//我们已经将第3小数放到第3位，用了2次比较，2次交换。现在要将第4小数放到第4位。

第十步： 2 4 6 8 9 ? ? ?// 将 9?8?比较，交换。

这时，程序结束了。我们也将数列排好了。每一次的交换如下：

4 9 2 8 6

2 9 4 8 6

2 4 9 8 6

2 4 8 9 6

2 4 6 9 8

2 4 6 8 9

排序结束。

知道了基本原理，代码也就好打了（将整形的数从小到大排序）：

#include <iostream>
#include <cmath>
using namespace std;

int n,i,j,a[2000];
bool t;              //定义变量

int main()
{
	cin >>n;
	for (i=1;i<=n;i++)
		cin >>a[i];       //输入

	for (i=1;i<n;i++)        //从1开始，最后一位不用比
		for (j=i+1;j<=n;j++)
			if (a[i]>a[j])        //a[i]是基本位，a[j]是当前位
				swap(a[i],a[j]);     //交换

	for (i=1;i<=n;i++)
		cout <<a[i] <<" ";        //输出

	return 0;        //华丽结束
}

选择排序时间复杂度为O（n2），比计数排序要慢，和冒泡排序一样，但没有数据类型和范围的局限（当然，范围不能太大），是一种很好记的不稳定排序。

选择排序讲解完毕，别忘了点个赞哦。