排序算法总结
-
需要占用额外空间： 归并排序、计数排序、基数排序、桶排序。
-
不占用额外内存或占用常数的内存： 插入排序、选择排序、冒泡排序、堆排序、快速排序。
-
稳定排序： 插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序
-
非稳定排序： 选择排序、快排、堆排序
详细说明
插入排序
-
每次将新元素插入到已排好序的子数组中。
-
如果数组已经排好序，复杂度是
O(n)，优于快排。 -
操作次数等于逆序对的个数。
代码
1
2
3
4
5
6
7
8
9
10
11
12 void Insertion_Sort(vector<int> &A) {
int n = A.size();
int curr;
for(int i = 1, j; i < n; ++i) { // A[0]已经排好序，依次将A[1 ... n - 1]插入进去
curr = A[i]; // 待插入元素
for(j = i - 1; j >= 0 && A[j] > curr; --j) { // 比 curr 大的就往后挪一位
A[j + 1] = A[j];
}
A[j + 1] = curr; // 把 curr 插在最后一个比它大的位置（该位置的元素已经挪到了后面）
}
return ;
}
冒泡排序
-
每次在剩余未排序的元素中选择一个最小的放在已排序的数组后面。
-
交换次数等于逆序对的个数。
代码
1
2
3
4
5
6
7
8
9
10
11 void Bubble_Sort(vector<int> &A) {
int n = A.size();
for (int i = 0; i < n; ++i) {
for (int j = n - 1; j > i; --j) { // 也可以使用递增循环，只不过让大的元素一直下降。
if(A[j] < A[j - 1]) { // 小的元素一直往前上浮
swap(A[j], A[j - 1]);
}
}
}
return ;
}
选择排序
-
每次选择出一个最小值。
代码
1
2
3
4
5
6
7
8
9
10
11
12 void Selection_Sort(vector<int> &A) {
int n = A.size();
for (int i = 0, idx; i < n; ++i) { // 上限可以是 n - 1，因为只剩一个元素时，它自己就是剩余元素中的最小值。
idx = i;
for (int j = i + 1; j < n; ++j) { // 找出剩余元素中最小的一个
if(A[j] < A[idx]) {
idx = j;
}
}
swap(A[idx], A[i]); // 与当前位置元素交换
}
}
归并排序
-
需要外部空间。
-
适用于外部排序。
-
注意代码实现的一个技巧，设置哨兵值。
代码
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 // merge [s, m - 1] and [m, e]
void Merge(vector<int> &A, int s, int m, int e) {
int *L = NULL, *R = NULL;
int lena = m - s, lenb = e - m;
if(lena > 0) L = new int[lena + 1];
if(lenb > 0) R = new int[lenb + 1];
for (int i = s; i < m; ++i)
L[i - s] = A[i];
for (int i = m; i < e; ++i)
R[i - m] = A[i];
int idxl = 0, idxr = 0;
// 设置哨兵值后就不需要考虑两个序列谁先结束了
L[lena] = INT_MAX;
R[lenb] = INT_MAX;
for (int i = s; i < e; ++i) {
if(L[idxl] < R[idxr])
A[i] = L[idxl++];
else
A[i] = R[idxr++];
}
free(L);
free(R);
/*
while(idxl < lena && idxr < lenb) {
if(L[idxl] < R[idxr])
A[idx++] = L[idxl++];
else
A[idx++] = R[idxr++];
}
if(idxl == lena) {
while(idxr < lenb)
A[idx++] = R[idxr++];
}
else{
while(idxl < lena)
A[idx++] = L[idxl++];
}
*/
return ;
}
void _Merge_Sort(vector<int> &A, int s, int e) {
if(s + 1 >= e) return ;
int m = s + (e - s) / 2;
_Merge_Sort(A, s, m);
_Merge_Sort(A, m, e);
Merge(A, s, m, e);
}
void Merge_Sort(vector<int> &A) {
_Merge_Sort(A, 0, A.size());
}
快速排序
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 int Partition(vector<int> &A, int s, int e) {
int pivot = A[e];
int pos = s, idx;
for (idx = s;idx < e; ++idx) { // 不能等于e
if(A[idx] <= pivot) {
swap(A[idx], A[pos]);
++pos;
}
}
swap(A[idx], A[pos]);
return pos;
}
void _Quick_Sort(vector<int> &A, int s, int e) {
if(s < e) {
cout<<s<<" "<<e<<endl;
int p = Partition(A, s, e);
_Quick_Sort(A, s, p - 1);
_Quick_Sort(A, p + 1, e);
}
}
void Quick_Sort(vector<int> &A) {
_Quick_Sort(A, 0, A.size() - 1);
}