十大排序算法思路&代码实现(持续更新中）_算法排列问题的思路

写在前面:

本篇博客主要整理了基础的十大排序算法的排序思路，以及代码实现，还有时间和空间复杂度的详细总结

目录：

1. 排序总结
2. 冒泡排序
3. 选择排序
4. 插入排序
5. 希尔排序
6. 归并排序
7. 快速排序
8. 堆排序(待写ing）

排序总结

1、冒泡排序

算法思想：冒泡这个词让我们想起在幽蓝的深海里，一串串气泡，在海底下缓缓的浮上海面的画面，在那一瞬间破裂，也代表着一切的结束。冒泡排序也如此，通过前后两两进行比较达到大于(或小于）的条件就交换，依次类推.

---

C++代码实现：

#include<iostream>
#include<vector>
using namespace std;
void Print(vector<int>& v)//打印vector中的内容
{
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}
void BubleSort(vector<int>& v)
{
	int i, j;
	for (i = 0; i < v.size()-1; i++)//时间复杂度是O(n^2)最好的情况是O(n)全部有序扫描一遍即可 空间复杂度是O(1)
	{
		int count = 0;
		for (j = 0; j < v.size() - i-1; j++)
		{
			if (v[j] > v[j + 1])
			{
				swap(v[j], v[j + 1]);
				count++;
			}
		}
		if (count == 0)//计数器，当没有交换时说明已经有序了 对冒泡排序的优化
		{
			break;
		}
		cout << "第" << i << "次排序结果为：";
		Print(v);
	}
	cout << "最终排序结果为：" << endl;;
	Print(v);
}
int main()
{
	vector<int> v;
	int n, m;
	cin >> m;
	while (m)
	{
		cin >> n;
		v.push_back(n);
		m--;
	}
	BubleSort(v);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

测试用例
元素个数： n =10;
数组元素为：[121,32,2,13,31,13,13311,3,1231,12]

测试结果：
可以看到当增加计数器对冒泡排序优化之后，在排了6次有序之后就不再对数组进行排序了。

时间复杂度和空间复杂度：

这是两层循环，时间复杂度为O(n^2)，空间复杂度是O(1)且是稳定的排序算法

2、选择排序

选择排序可以看作冒泡排序的优化之后的子版本，选择排序的基本思想就是依次选出数组中最小或者最大的数按顺序放到数组的下标第 0，1，2，3，4，5，6，7，… 中

代码实现：

#include<iostream>
#include<vector>
using namespace std;
void Print(vector<int>& v)
{
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}
void SelectSort(vector<int>& v)
{
	int i = 0;
	int j ;
	for (i = 0; i < v.size(); i++)
	{
		int min = v[i];
		int index = i;
		for (j = i + 1; j < v.size(); j++)
		{
			if (v[j] < min)
			{
				min = v[j];
				index = j;
			}
		}
		cout << "每次选择的最小的数是：" << v[index] << "下标为：" << index << endl;
		swap(v[i], v[index]);
		cout << "第" << i << "次排序结果为：";
		Print(v);
	}
	cout << "最终排序结果为：";
	Print(v);
}
int main()
{
	vector<int> v;
	int n, m;
	cin >> m;
	while (m)
	{
		cin >> n;
		v.push_back(n);
		m--;
	}
	SelectSort(v);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

测试用例：
元素个数： n = 10;
数组元素为：[34,2, 12, 67, 6754, 23, 789, 23, 5, 8]

测试结果：

时间复杂度和空间复杂度说明

这相当与冒泡排序的优化，还是两层循环，时间复杂度为O(n^2)

3、插入排序

插入排序的算法思想就是，将该数字插入到前面已经有序的数组里，将其插入到使前面数组有序的位置；
基本的步骤为： 循环+比较+挪动数据+找到小于+赋值(插入)
例如
数组元素为：1 3 4 2 5
数组下标为：0 1 2 3 4

循环： 默认第一个是有序的，因为第一个只有自己这一个元素，因此是有序的，因此从第二个开始循环比较。
比较+挪动数据 + 赋值： 比较的方式时向前比较 找到第一个比他小的数字，例如第一次 3 找不到比他小的数字，因此顺序不变，4 也是，循环到了 2 时 ，找到了 1 小于 2 因此 需要将 2 放到 1 的 后面 ，也就是 3 的位置，因此需要将 2 用 变量 temp 保存，并且 将 3 4 同时往后移动一个位置，也就是 将 4 放到 2 的位置上， 3 放到 4 的位置上，并且将 3 原来的位置上 放上 2 即可

代码实现：

#include<iostream>
#include<vector>
using namespace std;
void InsertSort(vector<int>&v)
{
	int i, j;
	for (i = 1; i < v.size(); i++)//循环的次数
	{
		int temp = v[i];//保存该位置的值 
		for (int j = i - 1; j >= 0; j--)//向前找比他小的数字
		{
			if (v[j] > temp)//将比他大的向后挪动
			{
				v[j + 1] = v[j];
			}
			else//找到比他小于等于的元素
			{
				break;
			}
		}
		v[j + 1] = temp;//在比他小的元素的后一个位置插入(赋值)  
	}
}
int main()
{
	vector<int> v;
	int n, m;
	cin >> m;
	while (m)
	{
		cin >> n;
		v.push_back(n);
		m--;
	}
	InsertSort(v);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

测试用例：
数组个数：10
数组元素：[21,42,232,4,231,5,32,12,21,3]
测试结果：

时间复杂度和空间复杂度说明：

插入排序也算是选择排序的一种优化，但是其还是一个O(n^2)的时间复杂度，两层循环的比较，但是其是稳定的排序，不需要额外的空间 ，空间复杂度为O(1)

4、希尔排序

首先，别人的排序都是根据排序的主要规则命名的，为什么你这是希尔排序？如果改成王铁柱排序大家估计就知道了，奥~，王铁柱发明的排序方法，对没错，希尔排序就是一个名为：Donlad Shell 的人发明的，因此叫做希尔排序，谷歌翻译是Hill,好了不乱扯了，接下来进入正题。

希尔排序的基本思想:
将一组数据分为若干组，比如一个有 8 个数据的数组，先将其分为 4 组，也就是一组两个数据，而这两个数据是由 间隔(gap) gap 个数据组成的，也就是说 下标 0 4，1 5 ，2 6，3 7，这样的四组先进行组内的排序

注意并不是新建数组或者将数组的元素排列成这样进行排序，这样会增加额外的空间或者重新排列的时间复杂度，而是通过下标的跳跃来控制的。

这样排排序之后，再分为gap/2 组，再次排序，最后再 gap/=2==1 也就是对整个数组排序，而希尔排序的基本方法就是之前学过的插入排序。

然后继续排：

这就是整个希尔排序的基本思路

这里就有人要问了，那你 Donlad Shell 不就是在抄人家插入的思想上改了点东西吗？？？
对没错！！！但是这也有着很大的区别，这里希尔的时间复杂度之所以比插入的低就是因为，之前所做的分组的预排序，我们知道在排序一个数组当数组中的数据高度有序且小规模的时候，排序的时间复杂度就会降低很多，正因是如此，这也是希尔排序的精华所在

通过以下插入排序和希尔排序在代码比较上，我们发现他们之间的差异并不是很大。

希尔排序基本步骤

1.定义一个gap 间隔多少个元素为一组，也就是分为几组
while(gap>=1) 当间隔为1 或者分为一组结束循环，最后一次就排好序了
外部循环控制要循环排序的每次划分的数组的个数(也就是次数) 这是一个logn的时间复杂度 每次gap/=2
内部就是对每一个数组进行的排序，进行插入排序

代码实现：

#include<iostream>
#include<vector>
using namespace std;
void Print(vector<int>& v)
{
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}
void ShellSort(vector<int>& v)
{
	int gap = v.size() / 2;//将整个数组划分为 gap个组 分别对这些组进行排序
	int i = 0;
	while (gap >= 1)// 当gap=1时为最后一次排序
	{
		for (i = 0; i<gap; i++)//每次分组需要对i个数组进行i次排序 如 gap=4 意思为分为4组
		{
			int k;
			for (k = i+gap; k < v.size(); k+=gap)//每个数组需要循环的次数
			{
				int j = 0;
				int temp = v[k];//插入进来的数
				for (j = k-gap; j >=0; j -= gap)//从后往前比较进行插入排序
				{
					if (v[j] > temp)//如果插入进来的比前一个小就挪动数据
					{
						v[j+gap] = v[j];
					}
					else//找到第一个比插入进来的数小的数的位置
					{
						break;
					}
				}
				v[j+gap] = temp;//将该位置的后一个赋值(也就是插入)为这个数	
			}
			cout << "gap=" << gap << " :";
			Print(v);
		}
		gap /= 2;//再次分组
	}
}
int main()
{
	vector<int> v;
	int n, m;
	cin >> m;
	while (m)
	{
		cin >> n;
		v.push_back(n);
		m--;
	}
	ShellSort(v);
	Print(v);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

测试用例：
数组个数：10
数组元素：[3,232,13,33,31,421,4,21,3,45]
测试结果：

结果分析：
相同颜色的代表是每一次的分的组，可以看到在每次的分组排序时，组内的数据都是有序的

时间复杂度和空间复杂度说明：

希尔排序因为每次需要跳跃性的进行数据排序也导致希尔排序是不稳定的，外层循环是logn次的，
而希尔排序的最坏情况下是O(logn^1.3 到n^2)的，其底层的推导过程比较的复杂，这里感兴趣的也可以去搜索查询）

5、归并排序

归并排序使用到的就是分治的算法思想
分治：

分治算法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题相同，递归的解这些问题的子问题然后将各个子问题的解合并到原问题的解。

那么归并排序也就是，将一个数组先分为两半，然后再对分成两半的数组再进行划分，然后再一步一步的进行使其有序的进行合并，最后得到一个有序的数组；

以下是归并排序的基本步骤

代码实现
首先我们应该想如何将两个有序的数组进行合并：这里需要开辟额外的空间来对排好序的进行保存，然后拷贝到原来的数组上：

void Merge(vector<int>& v, int left, int mid, int right,vector<int>& temp)
{
	int i = left, j = mid;//两个数组的范围
	int m = mid + 1, n = right;
	int k = 0;
	while (i <= j && m <= n)//两个数组的元素分别比较，比较小的先存放在开辟的数组temp中
	{
		if (v[i] < v[m])
		{
			temp[k++] = v[i++];
		}
		else
		{
			temp[k++] = v[m++];
		}
	}
	while (i <= j)//如果没有比较完就将剩下的数据放到temp后续的位置上来保持合并上的有序
	//例如 2 3 6 7这时候已经把 2 3 与6比较并放入temp中 这时候 m<=n将其余的 6 7放到后面的位置即可
		temp[k++] = v[i++];
	while (m <= n)
		temp[k++] = v[m++];
	for (i = 0; i < k; i++)
	{
		v[left + i] = temp[i];//再把排好序的拷贝给原来的数组中的left起始的位置
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这里的 例如 两个排好序的 [2, 3] [1, 4] 如何合并呢？

合并的写好了接下来就是对左右的划分了，一直向下划分即可

完整代码：

#include<iostream>
#include<vector>
using namespace std;
void Print(vector<int>& v)//打印数组中的元素
{
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}
void Merge(vector<int>& v, int left, int mid, int right,vector<int>& temp)
{
	int i = left, j = mid;//两个数组的范围
	int m = mid + 1, n = right;
	int k = 0;
	while (i <= j && m <= n)//两个数组的元素分别比较，比较小的先存放在开辟的数组temp中
	{
		if (v[i] < v[m])
		{
			temp[k++] = v[i++];
		}
		else
		{
			temp[k++] = v[m++];
		}
	}
	while (i <= j)//如果没有比较完就将剩下的数据放到temp后续的位置上来保持合并上的有序
	//例如 2 3 6 7这时候已经把 2 3 与6比较并放入temp中 这时候 m<=n将其余的 6 7放到后面的位置即可
		temp[k++] = v[i++];
	while (m <= n)
		temp[k++] = v[m++];
	for (i = 0; i < k; i++)
	{
		v[left + i] = temp[i];//再把排好序的拷贝给原来的数组中的left起始的位置
	}
}
void MergeSort(vector<int>& v,int left,int right,vector<int>& temp)
{
	if (left < right)
	{
		int mid = (right + left) / 2;
		MergeSort(v, left, mid,temp);
		MergeSort(v, mid + 1, right,temp);
		Merge(v, left, mid, right,temp);
		Print(v);//打印每次排序的结果
	}
}
int main()
{
	vector<int> v;
	int n, m;
	cin >> m;//输入数组元素的个数
	while (m)
	{
		cin >> n;
		v.push_back(n);
		m--;
	}
	int left = 0;
	int right = v.size() - 1;
	vector<int> temp(v.size(), 0);
	MergeSort(v,left,right,temp);
	cout << "最终排序结果为:";
	Print(v);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

测试用例：
数组元素个数： 10
数组元素：[32,321,4,12,454,7,876,65,5,41]
测试结果：

时间复杂度和空间复杂度

归并排序在分治的基本算法思想下使其的最好/平均/最差时间复杂度都是O(logn)级别的，且是稳定的排序算法，但是其每次需要开辟辅助空间来排序，因此空间复杂度是O(n+logn)

6、快速排序

快速排序应该是大家耳熟能详的算法之一了，快速排序和其名字一样比之前学习的的冒泡，选择还有插入等都要块很多。
快速排序基本思想与步骤：

1.选定一个基数，扫描区间，将比它小的放在左边，比他大的放在右边，将这个基数放在他应该在的位置上。

2.分治思想，接下来在对剩下的左右两个区间进行 1 的操作

终止的条件是 left=right表示只有这个区间只有一个元素 ，就不再继续分下去，这样递归下去每次找到key在整个区间的位置，最后就称为有序的数组了。

代码实现：

#include<iostream>
#include<vector>
using namespace std;
void Print(vector<int>& v)
{
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}
void QiuckSort(vector<int>& v,int left,int right)
{
	if (left < right)
	{
		//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 当选取中间的为基数时
		int i = left, j = right, x = v[left];//将区间最左边的定义为基数 //这个也可以因人而异
		cout << "key= " << x<<endl;
		while (i < j)
		{
			while (i < j && v[j] >= x) // 从右向左找第一个小于x的数
				j--;
			if (i < j)
				v[i++] = v[j];//找到之后将v[j]的值赋值给v[i]位置 并且i++ 开始从左向右找大于 基数的值
			//放到 右边
			while (i < j && v[i] < x) // 从左向右找第一个大于等于x的数
				i++;
			if (i < j)
				v[j--] = v[i];//v[i]赋值给v[j] 并且 j--,
		}
		v[i] = x;//当 i = j的时候就是找到了 基数的位置 放入该位置即可
		cout << "每次排序的结果为：";
		Print(v);
		cout << endl;
		QiuckSort(v, left, i - 1); // 递归调用左区间
		QiuckSort(v, i + 1, right);//右区间
	}
}
int main()
{
	int n;
	cin >> n;//输入数组元素的个数
	vector<int> v;
	while (n >0)
	{
		int temp;
		cin >> temp;
		v.push_back(temp);
		--n;
	}
	QiuckSort(v,0,v.size()-1);
	cout << "结果为: ";
	Print(v);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

测试用例：
数组个数：6
数组元素：[12,4,24,16,9,45]
测试结果

时间复杂度与空间复杂度说明：

最优和平均的时间复杂度 O(logn)就不在阐述了，最差的时候是每次取到的这个基数都是这个区间最大的或者最小的，这样就会每次进行比较而且这一次区间只划分出了这一个子序列，这样就会导致 O(n^2)的时间复杂度，因为递归的调用导致空间复杂度是O(logn)，且因为其是跳跃交换的因此排序算法是不稳定的。

7.堆排序（Updating)

本次完整测试代码：
Sort.h 头文件

#pragma once
#include<iostream>
#include<vector>
#include<random>
#include<ctime>
#include<Windows.h>
using namespace std;
class Sort
{
public:
	/***********************************
	名称 :   冒泡排序
	说明 :   
	每一次 相邻两个数字比较 例如 i 和 i + 1 进行比较，
	每一趟将会把最大或者最小的一个数排到最后
	依次类推，需要比较 n*n 次
	返回值 : 无
	参数 : 包含若干个整数的数组
	************************************/
	void BlueSort(vector<int>&vctResult);

	/***********************************
	名称 :    选择排序
	说明 :    
	选择排序的核心思想是依次选出最大或者最小的数字，
	然后依次从左到右排列这样就得出了一个递增或者递减的有序数列
	返回值 : 无
	参数 : 包含若干个整数的数组
	*/
	void SelectSort(vector<int>&vctResult);

	/***********************************
	名称 :    插入排序
	说明 :    
	默认第一个有序，从左到右依次遍历每一个数，与这个数的前面所有的数字进行比较
	比这个数字大的数都往后挪，将这个数字放在找到的第一个比这个数字小于等于 数字的后面
	例如 1 2 3 1 2 ，第一次排序为 1 1 2 3 2 ，遍历到第四个数字 1 时 ，将 2 3 都往后挪动
	并将 1 插入到第一个数字 1 的后面
	返回值 : 无
	参数   : 包含若干个整数的数组
	***********************************/
	void InsertSort(vector<int>&vctResult);

	/***********************************
	名称  : 希尔排序
	说明  : 
	希尔排序是因为发明该种排序方法的人叫做 Donlad Shell 所以叫做 希尔排序 
	希尔排序其实是在插入排序的基础上进行优化
	希尔的步骤为 
	1.先分组，使每一组内的数据有序 将整个数组划分为 
	例如: 先将
	2.有序的方法：插入排序
	返回值 : 无
	参数   : 包含若干个整数的数组
	***********************************/
	void ShellSort(vector<int>&vctResult);

	/***********************************
	名称  :  快速排序
	说明 :   快速排序 核心思想为每次将一个数字放到正确的位置上
	正确的位置指的是这个数字左边都是比他小(大) 且这个数字的右边都比他大(小) 
	并递归的处理 左区间和右区间
	参数  : 包含若干个整数的数组
	left ~ right 数组的左右区间
	返回值  : 无
	***********************************/
	void QuickSort(vector<int>&vctResult, int left , int right);

	/***********************************
	名称  :  归并排序
	说明 :	先分解问题，然后把有序的子数组左右区间逐渐合并
	参数  : 包含若干个整数的数组 vctResult
	left ~ right 数组的左右区间
	vctTemp 额外空间 用于辅助排序
	返回值  : 无
	***********************************/
	void MergeSort(vector<int>&vctResult, int left, int right, vector<int>&vctTemp);

	/***********************************
	名称  :  归并排序子函数，排序合并函数
	说明 :
	参数  : 包含若干个整数的数组 vctResult
	left ~ right 数组的左右区间 , mid 中间元素
	vctTemp 额外空间 用于存储有序元素，最后拷回到 vctResult
	返回值  : 无
	***********************************/
	void SortAndMerge(vector<int>&vctResult, int left, int right, int mid, vector<int>&vctTemp);

	/***********************************
	功能 : 打印一个vector中的所有元素
	参数 : vector<int>
	返回值 : 无
	***********************************/
	void PrintVectorCell(vector<int>&vctTemp);

	/***********************************
	功能 : 生成随机数
	返回值 : int
	参数 : 
	mixNumber ~ maxNumber 生成的随机数的数字范围区间 
	number 生成随机数的个数
	vctResult 生成随机数的结果(若生成多个随机数)
	说明 :
	如果只生成一个随机数只返回该随机数
	***********************************/
	int MakeRanoundNumber(int mixNumber, int maxNumber, int number,vector<int>&vctResult);

	//测试排序算法的正确性
	void TestSort();

	/***********************************
	说明 : 
	测试一个一段有序的数字是否时升序或者降序正确排列,默认检查升序，否则为降序
	参数 : vector<int>&vctResult 有序数组 ， isUp 是否升序
	返回值 : 正确的升序/降序 序列 返回 true 否则返回 false
	***********************************/
	bool CheckSortRight(vector<int>&vctResult, bool isUp = true);

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

Sort.cpp 文件

#include"Sort.h"
void Sort::BlueSort(vector<int>&vctResult)
{
	if (!vctResult.size())
	{
		cout << "Vector is empty" << endl;
	}
	else
	{
		for (int i = 0; i < vctResult.size(); i++)
		{
			int count = 0;
			for (int j = 0; j < vctResult.size() - i; j++)
			{
				if (j != vctResult.size() - 1 && vctResult[j] > vctResult[j + 1])
				{
					int temp = vctResult[j + 1];
					vctResult[j + 1] = vctResult[j];
					vctResult[j] = temp;
					count++;
				}
			}
			if (0 == count)
			{
				break;
			}
		}
	}
}
void Sort::PrintVectorCell(vector<int>&vctTemp)
{
	if (!vctTemp.size())
	{
		cout << "vector is empty" << endl;
	}
	else
	{
		for (auto e : vctTemp)
		{
			cout << e <<" ";
		}
		cout << endl;
	}

}
int Sort::MakeRanoundNumber(int mixNumber, int maxNumber, int number, vector<int>&vctResult)
{
	if (mixNumber == maxNumber && 0 == mixNumber)
	{
		return 0;
	}
	if (-1 == number)
	{
		return -1;
	}
	default_random_engine randTemp;
	uniform_int_distribution<int> range(mixNumber, maxNumber);
	randTemp.seed(time(0));
	for (int i = 0; i < number; i++)
	{
		if (1 == number)
		{
			vctResult.push_back(range(randTemp));
			return range(randTemp);
		}
		else
		{
			vctResult.push_back(range(randTemp));
		}
	}
	return 1;
}
bool Sort::CheckSortRight(vector<int>&vctResult, bool isUp)
{
	if (!vctResult.size())
	{
		return false;
	}
	for (int i = 0; i < vctResult.size(); i++)
	{
		if (isUp)
		{
			if (i != vctResult.size() - 1 && vctResult[i] > vctResult[i + 1])
			{
				return false;
			}
		}
		else
		{
			if (i != vctResult.size() - 1 && vctResult[i] < vctResult[i + 1])
			{
				return false;
			}
		}
	}
	return true;
}
void Sort::TestSort()
{
	bool bround = false;//是否进行随机测试
	int randonmTime = 200;//随机生成 组数;测试的组数
	int count = 0;
	cout << "测试排序:" << endl;
	cout << "测试冒泡排序请输入 1;" << endl;
	cout << "测试选择排序请输入 2;" << endl;
	cout << "测试插入排序请输入 3;" << endl;
	cout << "测试希尔排序请输入 4;" << endl;
	cout << "测试快速排序请输入 5;" << endl;
	cout << "测试归并排序请输入 6;" << endl;
	int k = 0;
	cin >> k;
	//记录排序所用时间
	int iStarTime = 0;
	int iEndTime = 0;
	double dTime = 0.0;
	for (int j = 0; j < randonmTime; j++)
	{
		cout << "当前为第 " << j << " 组" << endl;
		vector<int> vctNumber;
		int n = 0;
		Sleep(200 + j + 5);//防止每次生成的随机数一样
		if (bround)
		{
			
			n = MakeRanoundNumber(1, 100, 1, vctNumber); //控制每次产生的随机数的个数
		}
		else
		{
			n = 20;//每次固定产生20 个 随机数
		}
		MakeRanoundNumber(-100, 1000, n, vctNumber);
		cout << "生成的随机数为: " << endl;
		PrintVectorCell(vctNumber);
		//归并排序使用的额外空间
		vector<int> vctTemp;
		switch (k)
		{
			case 1:
				iStarTime = clock();
				BlueSort(vctNumber);
				iEndTime = clock();
				dTime += double(iEndTime - iStarTime);
				cout << "冒泡排序之后的数为: " << endl;
				break;
			case 2:
				iStarTime = clock();
				SelectSort(vctNumber);
				iEndTime = clock();
				dTime += double(iEndTime - iStarTime);
				cout << "选择排序之后的数为: " << endl;
				break;
			case 3:
				iStarTime = clock();
				InsertSort(vctNumber);
				iEndTime = clock();
				dTime += double(iEndTime - iStarTime);
				cout << "插入排序之后的数为: " << endl;
				break;
			case 4:
				iStarTime = clock();
				ShellSort(vctNumber);
				iEndTime = clock();
				dTime += double(iEndTime - iStarTime);
				cout << "希尔排序之后的数为: " << endl;	
				break;
			case 5:
				iStarTime = clock();
				QuickSort(vctNumber, 0, vctNumber.size()-1);
				iEndTime = clock();
				dTime += double(iEndTime - iStarTime);
				cout << "快速排序之后的数为: " << endl;
				break;
			case 6:
				iStarTime = clock();
				MergeSort(vctNumber, 0, vctNumber.size() - 1, vctTemp);
				iEndTime = clock();
				dTime += double(iEndTime - iStarTime);
				cout << "归并排序之后的数为: " << endl;
				break;
			default:
				break;
		}
		PrintVectorCell(vctNumber);
		if (!(CheckSortRight(vctNumber, true)))
		{
			cout << "排序结果错误！" << endl;
			count++;
		}
		vctNumber.clear();
	}
	if (count == 0)
	{
		cout << "所有排序结果均正确" << endl;
		
		cout << "本次共 " << randonmTime << " 组，排序结果均正确，平均每次排序用时: " << double(dTime / randonmTime) << " ms"<< endl;
	}
	
}
void Sort::SelectSort(vector<int>&vctResult)
{
	if (vctResult.size())
	{
		for (int i = 0; i < vctResult.size(); i++)
		{
			int min = vctResult[i];//默认第一个元素最小
			int index = 0;//记录右边数组中最小或最大元素下标
			for (int j = i + 1; j < vctResult.size(); j++)
			{
				if (vctResult[j] < min)
				{
					min = vctResult[j];
					index = j;//记录最小元素的下标
				}
			}
			if (i < index)//说明在右边的区间找到了 最大或者最小的数字
			{
				swap(vctResult[i], vctResult[index]); //自带的值交换函数
				//int iTemp = vctResult[index];
				//vctResult[index] = vctResult[i];
				//vctResult[i] = iTemp;
			}
		}
	}
}
void Sort::InsertSort(vector<int>&vctResult)
{
	if (vctResult.size())
	{
		//默认第一个有序，因此从 i = 1 开始向前比较
		for (int i = 1; i < vctResult.size(); i++)
		{
			int iTemp = vctResult[i];//保存该数
			//往前比较，先和 前一个数进行比较 找到第一个小于 iTemp 的数字 
			//需要将 iTemp 放在这个数字之后
			int j = i - 1;
			while(j >=0)
			{
				if (iTemp < vctResult[j])
				{
					//说明前面有比 iTemp 更大的数字 需要将这写数字往后挪动
					//因为是向后挪动数据，只需要把最后一个数字保存即可，
					//最后一个数字其实就是 vctResult[i] 这个已经 一开始用 iTemp 保存过了
					vctResult[j + 1] = vctResult[j];
					j--;
				}
				else
				{
					//找到了第一个比 iTemp 小于等于的数字
					break;
				}
			}
			//前面需要挪动的数据已经挪动好了 ，现在只需要将该数字 放到 j 的后一个位置上
			vctResult[j + 1] = iTemp;
		}
	}
}
void Sort::ShellSort(vector<int>&vctResult)
{
	if (vctResult.size())
	{
		int igap = vctResult.size()/2;//分组 
		//例如 1 2 3 4 5 6 7 8 分为 4 组
		//第一组数字为 1 ,5 ，这一组数字的选择规律为 
		//从下标 0 开始 间隔 igap(也就是组数) 选择下一个数字 下标为 4 
		//其余几组数据为 2 , 6; 3, 7; 4 ,8;
		while (igap >= 1)
		{
			//开始对每一组数据进行排序
			//逻辑上每一组，实际上并不额外开辟物理空间进行比较并交换
			//用下标控制每一组之间的比较于交换即可

			//分为几组就需要循环几次，将这几组的数据都变为有序,相当于 做 igap 次插入排序
			for (int i = 0; i < igap; i += igap)
			{
				//接下来的其实就和插入排序一样了
				for (int k = i + igap; k < vctResult.size(); k += igap)//i+igap 就相当于每次从每一组的数据的第二个开始
				{
					int iTemp = vctResult[k];
					int m = k - igap;//和前一个进行比较
					while (m >= 0)
					{
						if (vctResult[m] > iTemp)//将前面大的数字往后挪
						{
							vctResult[m+igap] = vctResult[m];
							m -= igap;
						}
						else
						{
							break;
						}
					}
					vctResult[m + igap] = iTemp;
				}
			}
			igap /= 2;
		}
	}
}
void Sort::QuickSort(vector<int>&vctResult, int left, int right)
{
	if (left < right)
	{
		int iRet = vctResult[left];//选择一个基数  这个基数可以选最左边也可以选最右边
		int i = left;
		int j = right;
		while (i < j)
		{
			while (i < j && vctResult[j] >= iRet)//先从左向右 找到第一个小于 iRet 的数字
			{
				j--;
			}
			if (i < j)
			{
				vctResult[i] = vctResult[j];//将小于这个基准的数调整到数组的右边
				i++;
			}
			while (i < j && vctResult[i] <= iRet)//先从右往左 找到第一个大于 iRet 的数字
			{
				i++;
			}
			if (i < j)
			{
				vctResult[j] = vctResult[i];//将大于这个基准的数调整到数组的右边
				j--;
			}
		}
		vctResult[i] = iRet;
		//一趟之后 该基数的左边都是比他小的数字，右边都是比他大的数字
		QuickSort(vctResult, left, i - 1);
		QuickSort(vctResult, i+1, right);
	}
}
void Sort::SortAndMerge(vector<int>&vctResult, int left, int right, int mid, vector<int>& vctTemp)
{
	vctTemp.clear();
	int i = left;
	int j = mid;
	int k = mid + 1;
	int m = right;
	//左右两个区间的数字进行比较 例如：
	//1 3 6; 2 4 5
	//比较有序变为 1 2 3 4 5 6
	while (i <= j && k <= m)
	{
		if (vctResult[i] <= vctResult[k])
		{
			vctTemp.push_back(vctResult[i]);
			i++;
		}
		else
		{
			vctTemp.push_back(vctResult[k]);
			k++;
		}
	}
	while (i <= j)
	{
		vctTemp.push_back(vctResult[i]);
		i++;
	}
	while (k <= m)
	{
		vctTemp.push_back(vctResult[k]);
		k++;
	}
	//将有序的数组拷回原来的数组中
	for (int g = 0; g < vctTemp.size(); g++)
	{
		vctResult[left + g] = vctTemp[g];
	}
}
void Sort::MergeSort(vector<int>&vctResult, int left, int right, vector<int>&vctTemp)
{
	
	if (left < right)
	{
		int mid = (left + right) / 2;
		MergeSort(vctResult, left, mid, vctTemp);
		MergeSort(vctResult, mid + 1, right, vctTemp);
		SortAndMerge(vctResult, left, right, mid, vctTemp);
	}
}
int main()
{
	Sort s;
	s.TestSort();
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390