DSA之十大排序算法第二种：Straight Selection Sort

直接选择排序
直接选择排序在我看来，是一种非常简单粗暴的方法。注：我们这里实现的所有排序算法，统一由小到大 C++实现。

1. 在这个无序的数列里面,每次都从中选择 或者 挑选最小的那个元素出来，把它放在此次参与排序的序列的第一个位置。
2. 然后再从剩下的无序数列里面取出最小的那个元素（此时的它可以视为本数列的第二小），然后同样放在此次参与排序的序列的第一个位置。
3. 重复这个 从无序数列取出最小元素，然后放在参与排序的序列的第一个位置。一直到数列元素最终有序。
   

如上图所示（从菜鸟网站“拿”来的）：面对上面的一组数据：

1,50,38,5,47,15,36,26,27,2,46,4,19,44,48

首先从 这个无序序列里面暂定最小值就是下标为0的元素，将其最小值下标记为min，然后取出数列最小值，即1 （通过比较得来的）。然后交换这个数据和下标min的数据。

那么此时就相当于 继续对数列

1       50,38,5,47,15,36,26,27,2,46,4,19,44,48

进行排序。根据 减而治之 的策略，可以证明其正确性和有穷性。

1. 对于任何一个数列，都需要去遍历整个数列 才可以找到这个 此次参与排序的序列 所以其时间复杂度无论如何都是O（n²）
2. 在最开始的时候，数列的有序区间为无，无序区间为【0，n-1】。在第i趟排序开始的时候，（1<= i <=n-1）数列的有序区间为【0，i-2】，无序区间为【i-1，n-1】。于是就是在第i趟排序中，把array【i-1】与这趟循环中的最小值进行交换。以达到数列的有序区间为【0，i-1】，无序区间为【i，n-1】。（无序区间的个数越来越少，有序区间个数越来越多）
3. 直接选择排序不是一个 稳定的算法。直接选择排序可以看做是：依次给数列中的每一个位置，选定与位置相对应的元素。比如：给第一个位置选择序列最小值，给第二个位置选择序列的次小值 一直到第n-1个位置，也就可以结束了（也就是n-1趟）。例如：序列 8 3 8 9 2 5 第一趟结束之后（最小值就位），2 3 8 9 8 5，这两个8的最初先后次序就发生了改变。直接选择排序是一个 不稳定的排序算法。

void Straight_Selection_sort1(vector<int>& src)
{
	int size = src.size();
	int count = 0;//计作交换的次数
	for (int i = 0; i < size - 1; ++i)
	{
		int min = i;//默认最小值下标		
		for (int j = i + 1; j < size ; ++j)
		{
			if (src[j] < src[min])
			{
				min = j;//记录一下 新的最小值下标
			}
		}

		count++;
		std::swap(src[min], src[i]);

		cout << "第" << setw(2) << i + 1 << "次排序后，结果为：";
		for (int k = 0; k <= size - 1; ++k)
		{
			cout << setw(2) << src[k] << " ";
		}
		cout << endl;
		
	}
	cout << "整个排序过程共进行了" << count << "次的交换" << endl;
}

如果当前元素其实已经是最小的了，然后经过一轮的比较，其实此时的min就是 i 也就是没有必要去 自己和自己进行交换。进行提前预判是否需要交换，以提高算法的效率。

void Straight_Selection_sort2(vector<int>& src)
{
	int size = src.size();
	int count = 0;//计作交换的次数
	for (int i = 0; i < size - 1; ++i)
	{
		int min = i;//默认最小值下标		
		for (int j = i + 1; j < size; ++j)
		{
			if (src[j] < src[min])
			{
				min = j;//记录一下 新的最小值下标
			}
		}
		if (min != i)//在这里进行预判
		{
			count++;
			std::swap(src[min], src[i]);
		}	
		cout << "第" << setw(2) << i + 1 << "次排序后，结果为：";
		for (int k = 0; k <= size - 1; ++k)
		{
			cout << setw(2) << src[k] << " ";
		}
		cout << endl;
	}
	cout << "整个排序过程共进行了" << count << "次的交换" << endl;
}

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

void Straight_Selection_sort1(vector<int>& src)
{
	int size = src.size();
	int count = 0;//计作交换的次数
	for (int i = 0; i < size - 1; ++i)
	{
		int min = i;//默认最小值下标		
		for (int j = i + 1; j < size ; ++j)
		{
			if (src[j] < src[min])
			{
				min = j;//记录一下 新的最小值下标
			}
		}

		count++;
		std::swap(src[min], src[i]);

		cout << "第" << setw(2) << i + 1 << "次排序后，结果为：";
		for (int k = 0; k <= size - 1; ++k)
		{
			cout << setw(2) << src[k] << " ";
		}
		cout << endl;
		
	}
	cout << "整个排序过程共进行了" << count << "次的交换" << endl;
}
void Straight_Selection_sort2(vector<int>& src)
{
	int size = src.size();
	int count = 0;//计作交换的次数
	for (int i = 0; i < size - 1; ++i)
	{
		int min = i;//默认最小值下标		
		for (int j = i + 1; j < size; ++j)
		{
			if (src[j] < src[min])
			{
				min = j;//记录一下 新的最小值下标
			}
		}
		if (min != i)//在这里进行预判
		{
			count++;
			std::swap(src[min], src[i]);
		}	
		cout << "第" << setw(2) << i + 1 << "次排序后，结果为：";
		for (int k = 0; k <= size - 1; ++k)
		{
			cout << setw(2) << src[k] << " ";
		}
		cout << endl;
	}
	cout << "整个排序过程共进行了" << count << "次的交换" << endl;
}
int main()
{
	int Array[] = { 1,50,38,5,47,15,36,26,27,2,46,4,19,44,48 };
	vector<int>myvec(begin(Array), end(Array));

	Straight_Selection_sort1(myvec);
	cout << "排序结束后，最终结果：";
	for (int val : myvec)
	{
		cout << setw(2) << val << " ";
	}
	cout << endl;
	cout << "*******************************************" << endl;
	vector<int>myvec2(begin(Array), end(Array));
	Straight_Selection_sort2(myvec2);

	cout << "排序结束后，最终结果：";
	for (int val : myvec2)
	{
		cout << setw(2) << val << " ";
	}
	cout << endl;
	return 0;
}

总结：用到直接选择排序的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。