前言
本文将分享NOI中常见的几种排序算法
本文中使用的定义来源于Wikipedia。
本文中使用的图片除最后一张来源于cnblogs之外,其他图片均来源于VisuAlgo。
本文中的C++代码除归并排序处引用自Wikipedia,其他的排序的代码均为本人所写。
🤣调用algorithm进行排序
algorithm中的std::sort()函数可以方便地进行排序,如果题目没有特殊要求,可以直接调用此函数。
C++代码
1
2
3
4
5
6
7
| #include <algorithm>
using namespace std;
/* your code ... */
sort(arr, arr + arr_len);
/* your code ... */
|
🧼冒泡排序
冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢「浮」到数列的顶端。
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
| #include <iostream>
using namespace std;
const int N = 10000;
void bubble_sort(int arr[], int len)
{
for (int i = len - 1; i >= 1; i--)
{
for (int j = 0; j < i; j++)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
}
}
}
}
int input(int arr[])
{
int len;
cin >> len;
for (int i = 0; i < len; i++)
{
cin >> arr[i];
}
return len;
}
void output(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
}
int main()
{
int arr[N], len;
len = input(arr);
bubble_sort(arr, len);
output(arr, len);
return 0;
}
|
👆选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
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
| #include <iostream>
using namespace std;
const int N = 10000;
void selection_sort(int arr[], int len)
{
for (int i = 0; i < len - 1; i++)
{
int min = i;
for (int j = i + 1; j < len; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
swap(arr[i], arr[min]);
}
}
int input(int arr[])
{
int len;
cin >> len;
for (int i = 0; i < len; i++)
{
cin >> arr[i];
}
return len;
}
void output(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
}
int main()
{
int arr[N], len;
len = input(arr);
selection_sort(arr, len);
output(arr, len);
return 0;
}
|
🀄️插入排序
插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
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
| #include <iostream>
using namespace std;
const int N = 10000;
void insertion_sort(int arr[], int len)
{
for (int i = 1; i < len; i++)
{
int key = arr[i];
int j = i - 1;
while ((j >= 0) && (key < arr[j]))
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int input(int arr[])
{
int len;
cin >> len;
for (int i = 0; i < len; i++)
{
cin >> arr[i];
}
return len;
}
void output(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
}
int main()
{
int arr[N], len;
len = input(arr);
insertion_sort(arr, len);
output(arr, len);
return 0;
}
|
📦桶排序
桶排序(Bucket sort)或所谓的箱排序,是一个排序演算法,工作的原理是将阵列分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序演算法或是以递归方式继续使用桶排序进行排序)。
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
| #include <iostream>
using namespace std;
const int N = 10000;
int bucket[N] = {};
void bucket_sort(int arr[], int bucket[], int len) {
for (int i = 0; i < len; i++) {
bucket[arr[i]]++;
}
}
int input(int arr[])
{
int len;
cin >> len;
for (int i = 0; i < len; i++)
{
cin >> arr[i];
}
return len;
}
void output(int bucket[], int len)
{
for (int i = 0; i < N; i++)
{
while (bucket[i]) {
cout << i << ' ';
bucket[i]--;
}
}
cout << endl;
}
int main()
{
int arr[N], bucket[N] = {}, len;
len = input(arr);
bucket_sort(arr, bucket, len);
output(bucket, len);
return 0;
}
|
🏇快速排序
快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要$O(nlogn)$次比较。在最坏状况下则需要$O(n^2)$次比较,但这种状况并不常见。事实上,快速排序$O(nlogn)$通常明显比其他演算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。
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
| #include <iostream>
using namespace std;
const int N = 10000;
void quick_sort(int arr[], int head, int tail)
{
if (head >= tail)
{
return;
}
int i = head, j = tail;
int pivot = arr[head]; // 通常取第一个数为基准
while (i < j) // i,j 相遇即退出循环
{
while (i < j and arr[j] >= pivot) // 从右向左扫描,将比基准小的数填到左边
{
j--;
}
arr[i] = arr[j];
while (i < j and arr[i] <= pivot) // 从左向右扫描,将比基准大的数填到右边
{
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot; // 将基准数填回
quick_sort(arr, head, i - 1); // 以基准数为界左右分治
quick_sort(arr, j + 1, tail);
}
int input(int arr[])
{
int len;
cin >> len;
for (int i = 0; i < len; i++)
{
cin >> arr[i];
}
return len;
}
void output(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
}
int main()
{
int arr[N], len;
len = input(arr);
quick_sort(arr, 0, len - 1);
output(arr, len);
return 0;
}
|
🎛归并排序(二路)
归并排序(英语:Merge sort,或mergesort),是建立在归并操作上的一种有效的排序算法,效率為$O(nlogn)$。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
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
| void Merge(vector<int> &Array, int front, int mid, int end) {
// preconditions:
// Array[front...mid] is sorted
// Array[mid+1 ... end] is sorted
// Copy Array[front ... mid] to LeftSubArray
// Copy Array[mid+1 ... end] to RightSubArray
vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
int idxLeft = 0, idxRight = 0;
LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
for (int i = front; i <= end; i++) {
if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
Array[i] = LeftSubArray[idxLeft];
idxLeft++;
} else {
Array[i] = RightSubArray[idxRight];
idxRight++;
}
}
}
void MergeSort(vector<int> &Array, int front, int end) {
if (front >= end)
return;
int mid = front + (end - front) / 2;
MergeSort(Array, front, mid);
MergeSort(Array, mid + 1, end);
Merge(Array, front, mid, end);
}
|
比较
名称 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
---|
冒泡排序 | $O(n^2)$ | $O(1)$ | ✔︎ |
选择排序 | $O(n^2)$ | $O(1)$ | ✖︎ |
插入排序 | $O(n^2)$ | $O(1)$ | ✔︎ |
桶排序 | $O(n)$ | $O(n)$ | ✖︎ |
快速排序 | $O(nlogn)$ | $O(logn)$ | ✖︎ |
归并排序(二路) | $O(nlogn)$ | $O(n)$ | ✔︎ |
选择