选择排序（日志14）

1.工作原理

选择排序（ Selection sort）是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2. 算法步骤

• （1）首先从原始数组中选择最小（最大）的1个数据，将其和位于第1个位置的数据交换。
• （2）接着从剩下的n-1个数据中选择次小（次大）的1个元素，将其和第2个位置的数据交换
• （3）然后，这样不断重复，直到最后两个数据完成交换。最后，便完成了对原始数组的从小到大（从大到小）的排序。

3.动图演示

4.代码实现

#include<iostream>
using namespace std;
int main()
{
	int a[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int temp;
	for(int i=0;i<15;i++)
	{
		temp = i;
		for(int j=i+1;j<15;j++)
		{
			if(a[temp]>a[j])
			{
				temp = j;
			}
		}
		if(temp!=i)
		{
			swap(a[i], a[temp]);
		}
	}
	for(int i=0;i<15;i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}

5.稳定性

选择排序是不稳定的排序，因其在排序过程中，会改变原本元素的相对位置。

以5 7 5 3 9 为例，若采用从小到大的排序，首先会对3和第一个位置的5进行交换位置，那在交换位置后，它和原来的5的相对位置就发生了转变，使得前5变成了后5，所以这种排序是不稳定的。