八大排序算法之简单选择排序算法

引言

简单选择排序算法是选择排序算法中的一种，另外一种选择排序就是堆排序了，这种简单的选择排序算法的复杂度其实和冒泡排序算法一样，并且最差情况，平均情况和最好的情况复杂度都是一样的，是一种不稳定的排序算法，主要思路和实现原理也都很简单，就是把一个无序数列中的数找出一个最小的数（从小到大排序的情况，从大到小则找出最大的数）然后与序列的最前面的数进行交换，然后循环依次放置即可。

具体思路

其实实现思路和直接插入排序有点像，都是把数组分成两个部分，一个是有序的部分，一个是无序的部分，但是直接插入排序是要不断插入在有序部分，需要在有序部分中找到一个合适的位置插入，但简单选择排序则不一样，只需要把最小的找出来放到最前面，之后只需遍历无序部分，然后把最小的找出来依次与前面有序部分的末尾的后一位（也就是无序部分的第一个数）进行交换就可以了。假设现在有一个数列为a，其中元素为5，11，43，6，2，9，7，16 每次查找的步骤如下

      （有序部分）2，11，43，6，5，9，7，16（无序部分）//找出无序部分中最小的数2，这里2就是第一位，无需交换
i=0   2（有序部分），11，43，6，5，9，7，16（无序部分）//找出无序部分中最小的数5，然后与无序部分第一位11进行交换
i=1   2，5（有序部分），43，6，11，9，7，16（无序部分）//找出无序部分中最小的数6，然后与无序部分第一位43进行交换
i=2   2，5，6（有序部分），43，11，9，7，16（无序部分）
i=3   2，5，6，7（有序部分），11，9，43，16（无序部分）
i=4   2，5，6，7，9（有序部分），11，43，16（无序部分）
i=5   2，5，6，7，9，11（有序部分），43，16（无序部分）
i=6   2，5，6，7，9，11，16（有序部分），43（无序部分）
i=7   2，5，6，7，9，11，16，43（有序部分）（无序部分）

代码实现

#include<iostream>
using namespace std;
int selectionSort(int *a,int n)
{
	int min,index; 
	for(int i=0;i<n-1;i++)
	{
		min=a[i];//设置最小初始值，一般设置为无序部分第一位数 
		index=i;//保存最小那个数的index 
		for(int j=i+1;j<n;j++)//从无序部分第二位开始找最小值 
		{
			if(min>a[j])
			{
				min=a[j];//找到最小值更新min值 
				index=j;//保存最小值的下标 
			}
		}
		swap(a[i],a[index]);//无序部分第一位数和最小值进行交换 
	}
}
int main()
{
	int n;
	cin>>n;
	int *a=new int[n]; 
	for(int i=0;i<n;i++)
		cin>>a[i];
	selectionSort(a,n);
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	delete []a;
	return 0;	
}

所以以上排序的复杂度是O(n^2),空间复杂度是O(1)，并且这是一个不稳定的排序算法，因为当无序数列中出现两个相同的数时，如果相同的其中一个数在第一位，那么与最小的一个数（最小的一个数如果在另一个相同的数的后面）交换后这两个相同的数前后顺序就破坏了，所以这是一种不稳定的排序。