经典算法（二）----选择排序----图解法让你快速入门

引言

     只要设计到数据，就会涉及到数据的排序问题，比如给你随机给你五个整数  3，1，5，2，4 。让你从小到大进行排序，那我们该怎样才是实现对这些整数的排序呢 ？

    答案是多种多样的，比如用冒泡排序、选择排序、堆排序、归并排序、快速排序等等，这些排序方法都可以实现对整数排序，而这篇文章要讲的就是选择排序

本文将从以下几个问题对选择排序进行分析和讲解：

1. 什么是选择排序？
2. 选择排序的大概过程是什么？
3. 怎样用代码实现选择排序？
4. 选择排序的代码详解。

什么是选择排序？

下面看百度百科对选择排序的定义：

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

简单来说：选择排序就是经过一轮一轮的查找，每一轮都从待排序的元素中选择一个最小的（或最大的）元素，存放在起始位置，直接排序完成位置。

下面看一个动图：

选择排序的大概过程是什么？

下面拿一个例子说明选择排序的大概过程。

选择排序的基本思想就是：首先选出来最小的数放到最前面，再选出来第二小的数放到最小的数前面，按照前面的方法直到排序完成。

下面来说用选择排序对3，1，5，2，4进行排序（从小到大排序）

1. 首先用一个变量minx记录3的下标，拿着minx对应的数字3和第二个数字1比较，发现1小，那数字1的下标存入minx中。
2. 继续拿着minx的数字1和第三个数字5进行比较，发现5大于1，不做处理。
3. 继续拿着minx的数字1和第四个数字2进行比较，发现2大于1，不做处理。
4. 继续拿着minx的数字1和第五个数字4进行比较，发现4大于1，不做处理。
5. 截止到现在为止，已经找到了最小数的下标minx，让这组数的第一个数和这个minx对应下标的值进行交换即可，这样就把最小的数放到了第一个位置，这时候这组数据变成了1，3，5，2，4.
6. 下面开始第二轮，寻找剩余元素的最小数。
7. 首先把第二个数的下标存入minx，拿着minx的数字3和第三个数字5进行比较，发现5大于3，不做处理。
8. 继续拿着minx的数字3和第四个数字2进行比较，发现3大于2，那就把3的下标存入到minx中。
9. 继续拿着minx的数字2和第五个数字4进行比较，发现4大于2，不做处理。
10. 截止到现在为止，已经找到了最小数的下标minx，让这组数的第二个数和这个minx对应下标的值进行交换即可，这样就把最小的数放到了第二个位置，这时候这组数据变成了1，2，5，3，4。
11. 下面继续重复上面的操作即可。

总结：选择排序是每次找到一个最小的数，放到前面，假如有n个元素需要排序，那么只需要n-1轮查找即可，因为最后一个数不处理，也会把最大的数剩余到最后面。而且每轮的查找次数也是有规律的，比如第 i 轮查找，只要比比较n-i-1次即可（重要★★★）

 怎样用代码实现选择排序？

通过上面对3，1，5，2，4的排序过程讲解，我们需要明确已知的三个条件

1. 我们要排序的数组有哪些数？数组长度为多少？
2. 我们要查找的次数为多少？
3. 每次查找，我们需要比较的次数为多少？

搞清楚了上面三个条件，我们下面我们动图数据排序的实现代码：

#include<iostream>
using namespace std;
//选择排序函数    不稳定 
void SelectionSort(int arr[],int len)
{
	int temp;
	for(int i=0;i<len-1;i++)
	{
		int minx=i;
		for(int j=i+1;j<len;j++)
		{
			if(arr[j]<arr[minx]) //寻找最小的数 
				minx=j;         //记录对应的下标 
		}
		temp=arr[i];
		arr[i]=arr[minx];
		arr[minx]=temp;
	}
}
//输出数组的值
void printf(int arr[],int len)
{
	for(int i=0;i<len;i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}
int main()
{
	//要排序的数组 
	int arr[]={3, 44,38, 5,47,15,36,26,27,2 ,46,4 ,19,50,48};
	int len=15;//要排序的数组长度 
	
	//排序 
	SelectionSort(arr,len);
	
	//输出 
	printf(arr,len);
	return 0;
}

运行结果：

 

选择排序的代码详解

上面代码写了两个函数，一个是printf函数，这个是输出排序后的数组。
另一个函数就SelectionSort函数，在这个函数里面有一个二重循环，外层循环的的次数就是要查找的次数，内层循环的次数的就是要比较的次数，刚好对应上面说的（这里数组下标是从0开始的）。
如果对上面代码有疑问，自己可以按照前面的过程，模拟一边对3，1，4，5，2的排序过程，就知道代码是怎样执行的了 。

本文参考以及引用：

百度百科

图片动画