经典排序算法C++实现（10种）_c++排序算法

本文总结了10中排序算法
下述两张图片来自链接:https://www.cnblogs.com/onepixel/p/7674659.html


鉴于维基百科中对于每个排序都进行了详细的描述，同时有动态图进行展示，就不详细的介绍了，每个排序都附加了维基百科链接；

插入排序

插入排序维基百科链接
插入排序说白了就是建一个已经排好序的数组，然后把原数组中的值一个一个的往新数组里边插；他的平均时间复杂度是o($n^2$),最好的情况是o(n)；
C++代码实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> InsertionSort(vector<int> data) {
   
	int len = data.size();
	vector<int> sortdata;
	sortdata.push_back(data[0]);
	for (int i = 1; i < len; i++) {
   
		sortdata.push_back(data[i]);
		for (int j = sortdata.size()-2; j >=0 ; j--) {
   
			if (sortdata[j+1] < sortdata[j]) {
   
				swap(sortdata[j], sortdata[j + 1]);
			}
			else
				continue;
		}
	}
	return sortdata;	
	
}
int main() {
   
	vector<int> data;
	for (int i = 0; i < 10; i++) {
   
		data.push_back(rand() % 101);
	}
	cout << "未进行排序时的数组为：";
	for (int i = 0; i < 10; i++) {
   
		cout << data[i] << ' ';
	}
	cout << '\n';
	data=InsertionSort(data);
	cout << "排序结束后：";
	for (int i = 0; i < data.size(); i++)
	{
   
		cout << data[i] << ' ';
	}
	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

希尔排序（缩小增量排序）

希尔排序维基百科链接
希尔排序是插入排序的一种，核心思想就是先将整个待排数组进行分割（gap=length/2），先小范围的进行插入排序，然后再分割，，，，，，等到分割次数足够小（$ga{p}_{new}$=($ga{p}_{before}/2$)）时直接进行一次插入排序
C++代码实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void ShellSort(vector<int>& data) {
   
	int len = data.size();
	for (int gap = len / 2; gap > 0; gap /= 2) {
   //将待排数组进行切割
		//cout << "gap is"<<gap<<'\n';
		for (int i = 0; i < gap; i++)//开始进行插入排序
		{
   
			for (int j = i + gap; j < len; j+=gap) {
   
				if (data[i] > data[j]) {
   
					swap(data[i], data[j]);
					
				}
				int k = j - gap;
				if (k >= 0 && data[k] > data[j])
					swap(data[k], data[j]);
				
			}
		}
	}
}
int main() {
   
	vector<int> data;
	for (int i = 0; i < 10; i++) {
   
		data.push_back(rand() % 101);
	}
	cout << "原始数据为：";
	for (int i = 0; i < 10; i++) {
   
		cout << data[i] << ' ';
	}
	cout << '\n'<<"希尔排序结果为：";
	ShellSort(data);
	for (int i = 0; i < 10; i++) {
   
		cout << data[i] << ' ';
	}
	cout << '\n';

	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

选择排序

选择排序维基百科链接
选择排序的时间复杂度最坏是O($n^2$),最好是O($n^2$)，平均是O($n^2$)，选择排序是一种简单直观的排序算法。
算法思想如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
C++代码实现

#include<iostream>
#include<vector>
#
1
2