选择排序 O(n^2)

一、选择排序流程

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

eg.a[3]={4,5,1}，
现在进行选择排序
首先：找出a中最大值5,将a[1]与a[0]互换 得到{5，4，1}
其次：找出a[1]-a[2]中剩余数据最大值4,不交换
结束

对于长度为n的数组，第一次取最值遍历n次，第二次遍历n-1次……最后一次。共计(n+1)*n/2次，因此时间复杂度为O(n^2)。

二、选择排序示例代码

#include<iostream>
using namespace std;
#define N 10
 
void Select_Sort(int* arr, int n)   //arr为数据数组，n为数组长度
{
	for (int i = 0; i < n-1; i++) 
	{
		int min = i;
		for (int j = i; j < n; j++) 
		{
			if (arr[min] > arr[j]) 
			{
				min = j;
			}
		}
		if (min != i) 
		{
			swap(arr[i], arr[min]);
		}
	}
}
 
int main()
{
	int arr[N]= { 1,4,6,3,0,2,5,9,8,7 };
	Select_Sort(arr, 10);
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << ",";
	}
	cout << endl;
	return 0;
}

三、附录 其他排序

十大经典算法复杂度及稳定性比较
冒泡排序
插入排序
快速排序
归并排序
堆排序
基数排序
计数排序

参考：
https://blog.csdn.net/alzzw/article/details/98100378