选择排序------简单直观的排序算法

选择排序（Selection Sort）也是一种经典排序算法（话说经典排序算法好多），它是一种简单直观的排序算法。

个人觉得，选择排序算法的原理比冒泡排序算法更容易理解。

算法原理/步骤

1. 从第一个元素开始，查找序列中最小的元素；
2. 将该元素与第一个元素交换；
3. 从下一个元素开始，查找剩下元素中最小的元素；
4. 重复操作2、3直到找出最后一个元素。

（维基好呀）

时间复杂度

从算法原理中可以看到，每次选择一个最小元素，故原序列第K个位置上的元素恰需要N-K次比较和1次交换，故最优、最差、平均时间复杂度均为O(N^2)。

稳定性

选择排序中相同元素相对位置不会改变，所以是稳定的排序。

算法演示

下面给出是对数据 {6, 5, 3, 1, 2, 4} 进行排序的过程演示。

Step 1 –> {1}, {6, 5, 3, 2, 4}

Step 2 –> {1, 2}, {6, 5, 3, 4}

Step 3 –> {1, 2, 3}, {6, 5, 4}

Step 4 –> {1, 2, 3, 4}, {6, 5}

Step 5 –> {1, 2, 3, 4, 5}, {6}

Step 6 –> {1, 2, 3, 4, 5, 6}

实例代码

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;

#define MAXN 10

int select_sort(int *, int);

int main()
{
	int src[MAXN];
	//先随机生成MAXN个数字，做测试用
	for(int i=0; i<MAXN; i++)
		src[i] = rand()%10000;

	/**输出原始数据*/
	for(int i=0; i<MAXN; i++)
		cout<<src[i]<<" ";
	cout<<endl;

	/**执行选择排序*/
	select_sort(src, MAXN);

	/**检查排序结果*/
	for(int i=0; i<MAXN-1; i++)
	{
		if(src[i] > src[i+1]){
			cout<<"wrong"<<endl;
		}
	}
	cout<<"sort finished!"<<endl;
	return 0;
}

/*
 * 选择排序
 * @param int* src 待排序数组
 * @param int size 待排序数组大小
 * 默认执行升序排序
 */

int select_sort(int *src, int size){
	int min;
	/*找出第i小的元素并将该元素放在第i位上*/
	for(int i=0; i<size; i++)
	{
		min=i;
		//跟它后面的元素比较，选出从第i位开始最小的
		for(int j=i+1; j<size; j++)
		{
			min=src[j] < src[min]?j:min;
		}
		//交换使得第i位上元素为第i小元素
		swap(src[i], src[min]);
	}
	return 0;
}

算法改进

好像没有吧，反正我是不知道。

总结

原地操作几乎是选择排序的唯一优点，当方度（space complexity）要求较高时，可以考虑选择排序；实际适用的场合非常罕见。

详细代码请点击这里查看。