几大常见的排序算法
算法分类
- 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(nlogn)$，因此称为非线性时间比较类排序。
- 线性时间非比较类排序： 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
时间复杂度
相关定义
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法流程
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
动画演示
http://www.atool.org/sort.php
代码演示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| inline void ()
{
int len = arr.length();
for(int i = 0;i < len - 1;++i)
{
for(int j = 0;j < len - 1;++j)
{
if(arr[j] > arr[j + i])
{
t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
}
|
选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法流程
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。
动画演示
http://www.atool.org/sort.php
代码演示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| inline void SelectionSort()
{
int len = arr.length();
int minindex,temp;
for(int i = 0;i < len - 1;++i)
{
minindex = i;
for(int j = i+1;j < len;++i)
{
if(a[j] < a[minindex])
minindex = j;
}
temp = a[i];
a[i] = a[minindex];
a[minindex] = temp;
}
}
|
插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法流程
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
动画演示
http://www.atool.org/sort.php
代码演示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void insertSort(int a[], int n)
{
for(int i = 1; i < n; i++)
{
if(a[i] < a[i-1])
{
int j = i-1;
int x = a[i];
while(j >= 0 && x < a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = x;
}
}
}
|
归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法流程
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
动画演示
http://www.atool.org/sort.php
代码演示
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
| void Merge(int arr[], int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q + 1;
int left[n1 + 1], right[n2];
for (int i = 0; i != n1; ++i){
left[i] = arr[p + i];
}
left[n1] = N;
for (int j = 0; j != n2 - 1; ++j){
right[j] = arr[q + j + 1];
}
right[n2 - 1] = N;
int i = 0, j = 0;
for(int k = p; k != r + 1; ++k){
if(left[i] > right[j]){
arr[k] = right[j];
++j;
}
else{
arr[k] = left[i];
++i;
}
}
}
void MergeSort(int arr[], int p, int r)
{
if(p < r){
int q = (p + r)/2;
MergeSort(arr, p, q);
MergeSort(arr, q + 1, r);
Merge(arr, p, q, r);
}
}
|
快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法流程
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
动画演示
http://www.atool.org/sort.php
代码演示
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
| void quicksort(int left, int right)
{
int i, j, t, temp;
if(left > right)
return;
temp = a[left];
i = left;
j = right;
while(i != j) {
while(a[j] >= temp && i < j)大专栏 0x05 排序r/> j--;
while(a[i] <= temp && i < j)
i++;
if(i < j)
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[left] = a[i];
a[i] = temp;
quicksort(left, i-1);
quicksort(i+1, right);
}
|
离散化
在很多情况下，问题的范围虽然定义在整数集合$Z$，但是只涉及其中$m$个有限数值，并且与数值的绝对大小无关（只把这些数值作为代表，或只与它们的相对顺序有关）。此时，我们就可以把整数集合$Z$中的这$m$个整数与$1～m$建立映射关系。
通俗来讲，就是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
算法流程
- 先将无序数组排序。
- 去重。
知识拓展
- C++STL中的unique函数解析
- C++ lower_bound 与 upper_bound 函数
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
inline void discrete()
{
sort(a + 1,a + n + 1);
for(int i = 1;i <= n;++i)
{
if(i == 1 || a[i] != a[i-1])
b[++m] = a[i];
}
}
inline int query(int x)
{
return lower_bound(b + 1,b + m + 1,x) - b;
}
|
莫斯科正在举办一个大型国际会议，有$n$个来自不同国家的科学家参会。
每个科学家都只懂得一种语言。
为了方便起见，我们把世界上的所有语言用$1$到$10^9$之间的整数编号。
在会议结束后，所有的科学家决定一起去看场电影放松一下。
他们去的电影院里一共有$m$部电影正在上映，每部电影的语音和字幕都采用不同的语言。
对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。
现在科学家们决定大家看同一场电影。
请你帮忙选择一部电影，可以让观影很开心的人最多。
如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。
输入格式
第一行输入一个整数$n$，代表科学家的数量。
第二行输入$n$个整数$a_1,a_2…a_n$,其中$a_i$表示第$i$个科学家懂得的语言的编号。
第三行输入一个整数$m$，代表电影的数量。
第四行输入$m$个整数$b_1,b_2…b_m$,其中$b_i$表示第i部电影的语音采用的语言的编号。
第五行输入$m$个整数$c_1,c_2…c_m$,其中$c_i$表示第i部电影的字幕采用的语言的编号。
请注意对于同一部电影来说，$b_i≠c_i$。
同一行内数字用空格隔开。
输出格式
输出一个整数，代表最终选择的电影的编号。
如果答案不唯一，输出任意一个均可。
数据范围
$1≤n,m≤200000$,
$1≤a_i,b_i,c_i≤10^9$
输入样例：
输出样例：
题解
用不可重集map来进行映射，很容易想到。
然后再排序查找，这里要进行重载，因为语言和字幕的权重是不一样的。
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
|
using namespace std;
const int MAX = 200010;
int n,mm;
unordered_map<int, int> m;
struct node {
int pos,lan,sub;
bool operator <(const node &num) const
{
if(lan == num.lan) return sub > num.sub;
else return lan > num.lan;
}
}a[MAX];
inline void init()
{
cin >> n;
for(int i = 1;i <= n;++i)
{
int x;
cin >> x;
m[x]++;
}
cin >> mm;
for(int i = 1;i <= mm;++i)
{
int x;
cin >> x;
a[i].pos = i;
a[i].lan = m[x];
}
for(int i = 1;i <= mm;++i)
{
int x;
cin >> x;
a[i].sub = m[x];
}
}
inline void find()
{
sort(a+1,a+mm+1);
cout << a[1].pos;
}
int main(void)
{
init();
find();
return 0;
}
|
中位数
没什么，就是中位数。。。
在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1$~$A_N$。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数$N$。
第二行$N$个整数$A_1$~$A_N$。
输出格式
输出一个整数，表示距离之和的最小值。
数据范围
$1≤N≤100000$
输入样例：
输出样例：
题解
排序之后查找中位数，然后相加，完事。
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
|
using namespace std;
const int MAX = 1e5 + 10;
int num[MAX],n;
inline void init()
{
cin >> n;
for(int i = 1;i <= n;++i)
cin >> num[i];
}
inline long long find()
{
sort(num+1,num+n+1);
int mid = num[(1+n)/2];
long long ans = 0;
for(int i = 1;i <= n;++i)
ans += abs(num[i] - mid);
return ans;
}
int main(void)
{
init();
cout << find();
return 0;
}
|
逆序对
设有一个序列$a_1, a_2, a_3,…a_{n-1}, a_n$,对于序列中任意两个元素$a_i,a_j$，若$i<j,a_i>a_j$，则说明$a_i$和$a_j$是一对逆序对。
逆序对求解
暴力
写两层循环，时间复杂度为$O(n^2)$ 。
归并排序
比如将下面两个区间排序
$a_i$
$3,4,7,9$
首先将右区间的 $1$ 取出，放到$r_k$中，此时 $1$ 是比每个$a_i$中的元素都小，也就是说此时i的指针指向 $a_1$ 的位置，此刻得到的逆序对的数量为 $4$ ； $r_k= 1$ ;
然后再将$a_i$和$a_j$比较（直到$a_i<a_j$），$a_i<a_j$ 将$a_i$的元素放到$r_k$中； $r_k= 1,3,4$;
现在$a_j>a_i$,$ i$ 指向$a_3$的位置，将 $5$ 放到$r_k$中，得到的逆序对数量为 $2$ ； $r_k= 1,3,4,5$
以此类推，直到进行完归并排序，每次合并都会求出逆序对的数目，即$mid-i+1$,最后每次将$ans$加上$mid-i+1$即可得到最后的答案；
树状数组
咕咕咕。。。。
参考资料
- 十大经典排序算法总结
- 洛谷：逆序对题解
0x05 排序
原文：https://www.cnblogs.com/lijianming180/p/12032689.html
