排序算法是经典算法的重要一环，不仅需要了解如何实现，更应该注意每一种排序适用的范围以及相应的时间空间复杂度要求。

插入排序（Insertion sort）

时间复杂度：Best = O（n）， Worst = O（n^2^）
空间复杂度：O（1）
稳定性：稳定

Code（C++）：

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
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
void insert_sort(vector<int>& data){
        int temp, j;
        for (int i = 1; i < data.size(); i++){
            temp = data[i];
            for (j = i; j > 0 && temp < data[j - 1]; j--){
                data[j] = data[j - 1];
            }
            data[j] = temp;
        }
}
int main(){
        int len;
        int cond;
        vector<int> data;
        string ans = "";
        cin >> len;
        for (int i = 0; i < len; i++){
            cin >> cond;
            data.push_back(cond);
        }
        insert_sort(data);
        for (int i = 0; i < data.size(); i++){
            char temp[64];
            sprintf(temp, "%d", data[i]);
            string s(temp);
            ans += s.c_str();
            ans += " ";
        }
        cout << ans << endl;
        return 0;
}

选择排序（Selection sort）

时间复杂度：Best = O（n^2^）， Worst = O（n^2^）
空间复杂度：O（1）
稳定性：不稳定

Code（C++）：

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
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
void swap(vector<int>& data, int i, int j){
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}
void selection_sort(vector<int>& data){
	for (int i = 0; i < data.size(); i++){
		int min = i;
		for (int j = i + 1; j < data.size(); j++){
			if (data[j] < data[min]){
				min = j;
			}
		}
		if (i != min){
			swap(data, i, min);
		}
	}
}
int main(){
	int len;
	int cond;
	string ans = "";
	vector<int> data;
	cin >> len;
	for (int i = 0; i < len; i++){
		cin >> cond;
		data.push_back(cond);
	}
	selection_sort(data)
	for (int i = 0; i < data.size(); i++){
		char temp[64];
		sprintf(temp, "%d", data[i]);
		string s(temp);
		ans += s.c_str();
		ans += " ";
	}
	cout << ans << endl;
	return 0;
}

希尔排序（Shell sort）

时间复杂度：Best = O（n）， Worst = O（n^2^）
空间复杂度：O（1）
稳定性：不稳定

Code（C++）：

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
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
void Shell_sort(vector<int>& data, int gap){
	for (; gap > 0; gap = gap / 2){
		for (int i = gap; i < data.size(); i++){
			int candidate = data[i];
			int j = i - gap;
			for (; j >= 0 && data[j] > candidate; j -= gap){
				data[j + gap] = data[j];
			}
			data[j + gap] = candidate;
		}
	}
}
int main(){
	int len, cond, gap;
	vector<int> data;
	string ans = "";
	cin >> len;
	for (int i = 1; i < len; i++){
		cin >> cond;
		data.push_back(cond);
	}
	gap = data.size() / 2;
	Shell_sort(data, gap);
	for (int i = 0; i < data.size(); i++){
		char temp[64];
		sprintf(temp, "%d", data[i]);
		string s(temp);
		ans += s.c_str();
		ans += " ";
	}
	cout << ans << endl;
	return 0;
}

堆排序（Heap sort）

时间复杂度：Best = O（nlogn）， Worst = O（nlogn）
空间复杂度：O（1）
稳定性：不稳定

Code（C++）：

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
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
void swap(vector<int>& data, int i, int j){
	int candidate = data[i];
	data[i] = data[j];
	data[j] = candidate;
}
void heapify(vector<int>& data, int root, int length){
	int leftChild = root * 2 + 1;
	int rightChild = root * 2 + 2;
	int max = -1;
	if (leftChild < length && (data[leftChild] > data[root]))
		max = leftChild;
	else
		max = root;
	if (rightChild < length && (data[rightChild] > data[max]))
		max = rightChild;
	if (max != root){
		swap(data, root, max);
		heapify(data, max, length);
	}
}
void heap_sort(vector<int>& data){
	for (int i = floor(data.size() / 2) - 1; i >= 0; i--){
		heapify(data, i, data.size());
	}
	for (int i = data.size() - 1; i > 0; i--){
		swap(data, i, 0);
		heapify(data, 0, i);
	}
}
int main(){
	int len, cond;
	vector<int> data;
	string ans = "";
	cin >> len;
	for (int i = 0; i < len; i++){
		cin >> cond;
		data.push_back(cond);
	}
	heap_sort(data);
	for (int i = 0; i < data.size(); i++){
		char temp[64];
		sprintf(temp, "%d", data[i]);
		string s(temp);
		ans += s.c_str();
		ans += " ";
	}
	cout << ans << endl;
	return 0;
}

冒泡排序（Bubble sort）

时间复杂度：Best = O（n）， Worst = O（n^2^）
空间复杂度：O（1）
稳定性：稳定

Code（C++）：

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
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
using namespace std;
void swap(vector<int>& data, int i, int j){
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}
void bubble_sort(vector<int>& data){
	bool flag = true;
	for (int i = 0; i < data.size() - 1 && flag; i++){
		flag = false;
		for (int j = 0; j < data.size() - i - 1; j++){
			if (data[j + 1] < data[j]){
				swap(data, j + 1, j);
				flag = true;
			}
		}
	}
}
int main(){
	int len, cond;
	vector<int> data;
	string ans = "";
	cin >> len;
	for (int i = 0; i < len; i++){
		cin >> cond;
		data.push_back(cond);
	}
	bubble_sort(data);
	for (int i = 0; i < data.size(); i++){
		char temp[64];
		sprintf(temp, "%d", data[i]);
		string s(temp);
		ans += s.c_str();
		ans += " ";
	}
	cout << ans << endl;
	return 0;
}

摇晃/鸡尾酒排序（Shaker sort）

时间复杂度：Best = O（n）， Worst = O（n^2^）
空间复杂度：O（1）
稳定性：稳定

Code（C++）：

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
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
void swap(vector<int>& data, int i, int j){
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}
void shaker_sort(vector<int>& data){
	int left = 0;
	int right = data.size() - 1;
	int shift = 0;
	while (left < right){
		for (int i = left; i < right; i++){
			if (data[i] > data[i + 1]){
				swap(data, i, i + 1);
				shift = i;
			}
		}
		right = shift;
		for (int i = right; i > left; i--){
			if (data[i] < data[i - 1]){
				swap(data, i, i - 1);
				shift = i;
			}
		}
		left = shift;
	}
}
int main(){
	int len, cond;
	vector<int> data;
	string ans = "";
	cin >> len;
	for (int i = 0; i < len; i++){
		cin >> cond;
		data.push_back(cond);
	}
	shaker_sort(data);
	for (int i = 0; i < data.size(); i++){
		char temp[64];
		sprintf(temp, "%d", data[i]);
		string s(temp);
		ans += s.c_str();
		ans += " ";
	}
	cout << ans << endl;
	return 0;
}

快速排序（Quick sort）

时间复杂度：Best = O（nlogn）， Worst = O（n^2^）
空间复杂度：O（nlogn）
稳定性：不稳定

Code（C++）：

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
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
void swap(vector<int>& data, int i, int j){
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}
void Quick_sort(vector<int>& data, int first, int last){
	if (first < last){
		int pivot = data[first];
		int left = first + 1;
		int right = last;
		while (true){
			while (data[left] <= pivot){
				if (left != right)
					left++;
				else
					break;
			}
			while (data[right] > pivot)
				right--;
			if (left < right)
				swap(data, left, right);
			else
				break;
		}
		swap(data, right, first);
		Quick_sort(data, first, right - 1);
		Quick_sort(data, right + 1, last);
	}
}
int main(){
	int len, cond;
	vector<int> data;
	string ans = "";
	cin >> len;
	for (int i = 0; i < len; i++){
		cin >> cond;
		data.push_back(cond);
	}
	Quick_sort(data, 0, data.size() - 1);
	for (int i = 0; i < data.size(); i++){
		char temp[64];
		sprintf(temp, "%d", data[i]);
		string s(temp);
		ans += s.c_str();
		ans += " ";
	}
	cout << ans << endl;
	return 0;
}

归并排序（Merge sort）

时间复杂度：Best = O（nlogn）， Worst = O（nlogn）
空间复杂度：O（n）
稳定性：稳定

Code（C++）：

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
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int* merge(int* left, int* right, int len, int l, int r){
	int* sorted = new int[len];
	int leftsize = 0, rightsize = 0;
	for (int i = 0; i < l + r; i++){
		if (leftsize == l)
			sorted[i] = right[rightsize++];
		else if (rightsize == r)
			sorted[i] = left[leftsize++];
		else if (left[leftsize] < right[rightsize])
			sorted[i] = left[leftsize++];
		else
			sorted[i] = right[rightsize++];
	}
	return sorted;
}
int* merge_sort(int* data, int len){
	if (len > 1){
		int* left = new int[len];
		int* right = new int[len];
		int middle = ceil(len / 2);
		int cout_l = 0, cout_r = 0;
		for (int i = 0; i < middle; i++){
			left[i] = data[i];
			cout_l++;
		}
		for (int j = middle; j < len; j++){
			right[j - middle] = data[j];
			cout_r++;
		}
		left = merge_sort(left, cout_l);
		right = merge_sort(right, cout_r);
		return merge(left, right, len, cout_l, cout_r);
	}
	return data;
}
int main(){
	int len, cond;
	int* data = new int[len];
	int* result = new int[len];
	string ans = "";
	cin >> len;
	for (int i = 0; i < len; i++){
		cin >> cond;
		data[i] = cond;
	}
	result = merge_sort(data, len);
	for (int i = 0; i < len; i++){
		char temp[64];
		sprintf(temp, "%d", result[i]);
		string s(temp);
		ans += s.c_str();
		ans += " ";
	}
	cout << ans << endl;
	return 0;
}

基数/桶排序（Radix sort）

时间复杂度：Best = O（d(n+r)）， Worst = O（d(n+r)），其中d代表回合数，n代表数组长度，r代表基数（桶）大小
空间复杂度：O（nr）
稳定性：稳定

Code（C++）：

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
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
void init_bucket(int** buckets, int count[], int len){
	for (int i = 0; i < 10; i++){
		buckets[i] = new int[len];
		count[i] = 0;
	}
}
int* radix_sort(int* data, int len){
	int max = 100;
	int dataindex = 0, radix = 1;
	int** buckets = new int*[10];
	int count[len];
	init_bucket(buckets, count, len);
	while(radix <= max){
		for (int i = 0; i < len; i++){
			int LSD = (int)ceil(data[i] / radix) % 10;
			buckets[LSD][count[LSD]] = data[i];
			count[LSD]++;
		}
		radix *= 10;
		dataindex = 0;
		for (int i = 0; i < 10; i++){
			if (count[i] != 0){
				for (int j = 0; j < count[i]; j++){
					data[dataindex++] = buckets[i][j];
				}
			}
			count[i] = 0;
		}
	}
	return data;
}
int main(){
	int len, cond;
	int* data = new int[len];
	string ans = "";
	cin >> len;
	for (int i = 0; i < len; i++){
		cin >> cond;
		data[i] = cond;
	}
	int* result = radix_sort(data, len);
	for (int i = 0; i < len; i++){
		char temp[64];
		sprintf(temp, "%d", data[i]);
		string s(temp);
		ans += s.c_str();
		ans += " ";
	}
	cout << ans << endl;
	return 0;
}