c++十大排序算法之选择排序

​
​

活动地址：CSDN21天学习挑战赛

• At first，我们先look一张我从某文章*的表格，来了解一下这几大算法
  

• 图都看了，那我也不得不提一嘴，图里面的东西了

  • 算法效率
    在一个算法设计完成后，还需要对算法的执行情况做一个评估。一个好的算法，可以大幅度的节省运行的资源消耗和时间。在进行评估时不需要太具体，毕竟数据量是不确定的，通常是以数据量为基准来确定一个量级，通常会使用到时间复杂度和空间复杂度这两个概念。

  • 时间复杂度
    通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句（赋值、判断、四则运算等基础操作)。我们可以把时问频度记为T(n)，它与算法中语句的执行次数成正比。其中的n被称为问题的规模，大多数情况下为输入的数据量。

    对于每一段代码，都可以转化为常数或与n相关的函数表达式，记做f(n)。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式，在合并后保留量级最大的部分即可确定时间复杂度，记做O(f(n))，其中的O就是代表数量级。
    常见的时间复杂度有（由低到高): O(1)、O(log2 n)、O(n)、O(n log2n)、O(n2)、o(n3)、O(2")、O(nl)。

  • 空间复杂度

  程序从开始执行到结束所需要的内存容量，也就是整个过程中最大需要占用多少的空间。为了评估算法本身，输入数据所占用的空间不会考虑，通常更关注算法运行时需要额外定义多少临时变量或多少存储结构。如:如果需要借助一个临时变量来进行两个元素的交换，则空间复杂度为O(1).

• 最坏的情况
  最坏的情况莫过于，完整的遍历了整个集合，也没有找到需要找的的元素，循环执行次数与n相关，所以时间复杂度为O(n).

• 最好的情况
  第一次循环便找到了元素，则时间复杂度为常数级O(1);

• 平常的情况
  综合两种情况，顺序查找的时间复杂度为O(n)，属于查找较慢的算法。

算法不会改变原有的元素集合，只需要一个额外的变量控制索引变化，所以空间复杂度为常数级:O(1)。

选择排序（Selection sort）是一种简单直观的排序算法。

先上图(无图无真相)
工作原理：

• 第一次从待排序数据中选择出最小或者最大的数据，然后存放的数据的起始位置。
• 然后再从未排序数据中，找出最小或者最大的元素，然后放到已排序数据为末尾。
• 以此类推，知道虚排序的数据个数为0。才算排序结束

void SelectionSort(vector& v) {
	int min, len = v.size();
	for (int i = 0; i < len - 1; ++i) {
		min = i;
		for (int j = i + 1; j < len; ++j) {
			if (v[j] < v[min]) {    // 标记最小的
				min = j;
			}
		}
		if (i != min)  // 交换到前面
			swap(v[i], v[min]);
	}
}

//选择排序
void SelectionSort(vector& v) {
	int min, len = v.size();
	cout << "排序前  " << endl;
	for (int i = 0; i <= v.size() - 1; i++) {
		cout << v.at(i) << " ";
	}
	for (int i = 0; i < len - 1; ++i) {
		min = i;
		for (int j = i + 1; j < len; ++j) {
			if (v[j] < v[min]) {    // 标记最小的
				min = j;
			}
		}
		if (i != min)  // 交换到前面
			swap(v[i], v[min]);
	}
	cout << endl << "排序后" << endl;
	for (int i = 0; i <= v.size() - 1; i++) {
		cout << v.at(i) << " ";
	}
}

void randperm(int Num)
{

	srand((int)time(0));
	vector temp;
	for (int i = 0; i < Num; ++i)
	{
		temp.push_back(i + 1);
	}
	random_shuffle(temp.begin(), temp.end());

	for (int i = 0; i < temp.size(); i++)
	{
		cout << temp[i] << ",";
	}
	getchar();
}

 #include 
#include 
#include 
#include  
#include  
#include 

using namespace std;

vector  y{ 39,29,30,22,7,43,1,5,48,27,11,25,4,
24,40,50,18,37,19,42,9,45,2,12,47,32,36,21,3,13,6,35,
28,17,41,14,8,10,16,46,15,26,44,33,49,31,20,34,23,38};
 

//生成打乱的数据
void randperm(int Num)
{

	srand((int)time(0));
	vector temp;
	for (int i = 0; i < Num; ++i)
	{
		temp.push_back(i + 1);
	}
	random_shuffle(temp.begin(), temp.end());

	for (int i = 0; i < temp.size(); i++)
	{
		cout << temp[i] << ",";
	}
	getchar();
}
 

//选择排序
void SelectionSort(vector& v) {
	int min, len = v.size();
	cout << "排序前  " << endl;
	for (int i = 0; i <= v.size() - 1; i++) {
		cout << v.at(i) << " ";
	}
	for (int i = 0; i < len - 1; ++i) {
		min = i;
		for (int j = i + 1; j < len; ++j) {
			if (v[j] < v[min]) {    // 标记最小的
				min = j;
			}
		}
		if (i != min)  // 交换到前面
			swap(v[i], v[min]);
	}
	cout << endl << "排序后" << endl;
	for (int i = 0; i <= v.size() - 1; i++) {
		cout << v.at(i) << " ";
	}
}

//冒泡排序
void BubbleSorderly(vector& v)
{

	//打印交换前的v向量
	cout << "排序前  " << endl;
	for (int i = 0; i <= v.size() - 1; i++) {
		cout << v.at(i) << " ";
	}
	int len = v.size();
	bool orderly = false;
	for (int i = 0; i < len - 1 && !orderly; ++i) {
		orderly = true;
		for (int j = 0; j < len - 1 - i; ++j) {
			if (v[j] > v[j + 1]) {  // 从小到大
				orderly = false;	// 发生交换则仍非有序
				swap(v[j], v[j + 1]);
			}
		}
	}
	cout << endl << "排序后" << endl;
	//打印整个vector
	for (int i = 0; i <= v.size() - 1; i++) {
		cout << v.at(i) << " ";
	}
	getchar();
}




int main()
{ 
	
	SelectionSort(y);	 
	getchar();
	return 0;
}

无图无真相