各种排序
| 排序 | 概述 | 时间复杂度 |
|---|
| 计数排序 | 对应票投入对应票箱 | O(n) |
| 选择排序 | 最小的放前 (两重循环) | O(n^2^) |
| 冒泡排序 | 依次比较相邻 (两重循环) | O(n^2^) |
| 插入排序 | 依次拿出一张牌插入排列中 (两重循环) | O(n^2^) |
| … | | |
这些排序各适用不同情况，但时间复杂度总体较大。
快速排序
程序设计竞赛中最普遍的排序。
随机选择哨兵，时间复杂度O(n log n)。但极端情况O(n^2^)。
概述：
选出一个哨兵，比哨兵小的数全放左边，比他大的全放右边。
再分别在左边和右边选出哨兵，进行分类。
以此循环，直到排序完成。
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
| #include <iostream>
using namespace std;
void qsort(int num[],int first,int last) {
int i = first, j = last, flag = num[(first + last) / 2], temp;
do {
while (num[i] < flag) i++;
while (num[j] > flag) j--;
if (i <= j) {
temp = num[i];
num[i] = num[j];
num[j] = temp;
i++; j--;
}
} while (i <= j); //带=为了让i和j交错而过，这样才可以用递归
if(first<j) qsort(num, first, j);
if(i<last) qsort(num, i, last);
}
int main()
{
int n, num[100000];
cin >> n;
//必须从i=1开始
for (int i = 1; i <= n; i++) {
cin >> num[i];
}
qsort(num,1,n);
for (int i = 1; i <= n; i++) {
cout << num[i]<<" ";
}
return 0;
}
|
当然也可以直接用algorithm头文件中的sort函数，
我们学会自己写是为了理解原理，提升思维，
同时在有特殊需求的时候可以更自定义化。
