2024NENU新生培训-排序
打算讲这几方面内容, 由易到难
- 简单排序(选择, 冒泡, 插入)
- sort 与 cmp
- 归并排序和快速排序
我们在做算法竞赛的时候通常用sort就可以解决所有问题了, 因此归并排序和快速排序我们学习的是一种思想而非真的需要用到, 此外还有许多种排序方法一样比简单排序更快, 但一个半小时是讲不完的, 因此如果你感兴趣, 在课后去了解是很有用的, 这在以后的某节专业课上同样会学到并出现在考试中. 但如果你有更重要的事情需要去做, 那么暂时跳过这一部分也是可以的, 但是至少也要掌握sort和cmp.
简单排序
简单的排序用时是n * n
选择排序
选择排序从前往后遍历, 两层循环, 每一次找到第 i 小的值放到 i 这个位置
伪代码如下
// n 为数组长度, a 为数组, 数组下标从 1 开始
for (int i = 1; i <= n; i ++ )
{
int x = 无限大
for (int j = i; j <= n; j ++)
{
x 取 x 与 a[j] 中更小值
}
交换 f[i] 与 x
}举例
5 4 3 2 1
第一次会找到从第一个数到第五个数中最小的 1, 与第一个数换, 变成
1 4 3 2 5
第二次找到从第二个数到第五个数中最小的数 2, 与第二个数换, 变成
1 2 3 4 5
第三次找到3, 与第三个数换
第四次找到4, 与第四个数换
第五次找到5, 与第五个数换
......
#include <stdio.h>
const int N = 100010;
int n;
int a[N];
void swap(int a[], int l, int r)
{
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
void select_sort(int a[], int l, int r)
{
for (int i = l; i <= r; i ++ )
{
int min_value = 1e9, min_index = i;
for (int j = i; j <= r; j ++ )
{
if (min_value > a[j])
{
min_index = j;
min_value = a[j];
}
}
swap(a, i, min_index);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
}
select_sort(a, 1, n);
for (int i = 1; i <= n; i ++ )
{
printf("%d ", a[i]);
}
}这很简单, 对吧?
冒泡排序
冒泡排序将从左往右, 每次将相邻数字相比决定是否交换位置, 从而获得一定范围内的最小值, 重复n次后就排好序了
举例
5 4 3 2 1
i = 1 时, j 从 n 往 1 遍历, 把 1 换到 下标为 1 的位置, 变成
1 5 4 3 2
i = 2 时, 把 2 换过去
1 2 5 4 3
1 2 3 5 4
1 2 3 4 5
最小值像气泡一样被换到其应在的位置
#include <stdio.h>
const int N = 100010;
int n;
int a[N];
void swap(int a[], int l, int r)
{
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
void bubble_sort(int a[], int l, int r)
{
for (int i = l; i <= r; i ++ )
{
for (int j = r; j > i; j -- )
{
if (a[j] < a[j - 1])
{
swap(a, j, j - 1);
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
}
bubble_sort(a, 1, n);
for (int i = 1; i <= n; i ++ )
{
printf("%d ", a[i]);
}
}插入排序
插入排序在遍历过程中,不断维护左边的有序性, 因为每次都会多一个数, 而且维护完后会让这个数放到左边的数组中, 因此得名插入排序
举例
5 4 3 2 1
i = 1 时, 从 1 到 i , 5 是有序的
i = 2 时, 从 1 到 i, 5 4 会被检查到顺序不对, 交换后变成 4 5
i = 3 时, 从 1 到 i, 4 5 3, 3 比 5, 被交换成 4 3 5, 接着检查 3 和 4, 3 比 4 小, 被交换,变成
3 4 5 2 1
i = 4 时, 维护后变为
2 3 4 5 1
i = 5 时, 维护后变为
1 2 3 4 5
#include <stdio.h>
const int N = 100010;
int n;
int a[N];
void swap(int a[], int l, int r)
{
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
void insert_sort(int a[], int l, int r)
{
for (int i = l; i <= r; i ++ )
{
for (int j = i; j > l; j -- )
{
if (a[j] < a[j - 1])
{
swap(a, j, j - 1);
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
}
insert_sort(a, 1, n);
for (int i = 1; i <= n; i ++ )
{
printf("%d ", a[i]);
}
}sort 与 cmp
sort 是c ++中<algorithm>这个头文件内的, 如果没有 using namespace std; 前面需要加std::
sort 的用法如下
sort (开始, 结尾)
你同样也可以这么用:
sort (开始, 结尾, 排序方法)
如果不手写一个排序方法的话, 那么sort 默认会按从小到大排序, 如下
#include <stdio.h>
#include <algorithm>
const int N = 100010;
int n;
int a[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
}
std::sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i ++ )
{
printf("%d ", a[i]);
}
}这很简洁, 对吧?
快速排序与归并排序
归并排序和快速排序真的是很经典的递归和分治, 掌握他们对于你构建属于你自己的算法大厦真的很有意义.
快速排序
代码
#include <bits/stdc++.h>
using namespace std;
int n;
int q[100010];
void quick_sort(int l, int r)
{
if (l >= r) return;
int x = q[l + r >> 1], i = l - 1, j = r + 1;
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> q[i];
quick_sort(1, n);
for (int i = 1; i <= n; i ++ ) cout << q[i] << " ";
}归并排序
代码
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100010], q[100010];
void merge_sort(int a[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1, i = l, j = mid + 1, k = 0;
merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
while (i <= mid && j <= r)
if (a[i] <= a[j]) q[k ++ ] = a[i ++ ];
else q[k ++ ] = a[j ++ ];
while (i <= mid) q[k ++ ] = a[i ++ ];
while (j <= r) q[k ++ ] = a[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) a[i] = q[j];
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
merge_sort(a, 1, n);
for (int i = 1; i <= n; i ++ ) cout << a[i] << " ";
return 0;
}