NVIDIA RTX wallpaper
741 字
4 分钟
【OI考古】基础算法 | 排序
排序算法(Sorting algorithm)是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样,性质也大多不同。
几种排序算法的比较:
模板题:洛谷 P1177 | [模板]快速排序
题目描述
利用快速排序算法将读入的 个数从小到大排序后输出。
输入格式
第 行为一个正整数 ,第 行包含 个空格隔开的正整数 ,为你需要进行排序的数,数据保证了 不超过 。
输出格式
将给定的 个数从小到大输出,数之间空格隔开,行末换行且无空格。
输入输出样例
输入 #1
5
4 2 4 5 1
输出 #1
1 2 4 4 5
说明/提示
对于 的数据,有 ;
对于 的数据,有 。
快速排序
快速排序(Quicksort),又称分区交换排序(partition-exchange sort),简称快排,是一种被广泛运用的排序算法。
解决方案
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100500;
int n;
int a[maxn];
void quick_sort(int a_[], int l, int r)
{
int mid = a_[(l + r) >> 1]; //取区间中点的数,也可以随机化取数
int i = l;
int j = r;
do
{
while (a_[i] < mid) //如果合法,就继续遍历
i++;
while (a_[j] > mid)
j--;
if (i <= j) //找到一对不合法的数,将其交换
{
swap(a_[i], a_[j]);
i++;
j--;
}
} while (i <= j); //最终的效果是[l, j]内的数都≤mid,[i, r]内的数都≥mid,与初始mid的位置无关
if (l < j) //如果[l, j]是一个合法区间,则继续排序
quick_sort(a_, l, j);
if (r > i) //如果[i, r]是一个合法区间,则继续排序
quick_sort(a_, i, r);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
quick_sort(a, 1, n);
for (int i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
归并排序
归并排序(merge sort)是一种采用了 分治 思想的排序算法。
解决方案
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100500;
int n;
int a[maxn];
void merge_sort(int a_[], int l, int r)
{
int mid = (l + r) >> 1; //取区间中点,左右子区间分别排序
int len = r - l + 1;
if (l < mid)
merge_sort(a_, l, mid);
if (r > mid + 1)
merge_sort(a_, mid + 1, r);
int tmp[len];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) //将两个有序数组合并,保存在临时数组tmp中
tmp[k++] = a_[i] < a_[j] ? a_[i++] : a_[j++];
while (i <= mid)
tmp[k++] = a_[i++];
while (j <= r)
tmp[k++] = a_[j++];
for (i = 0; i < len; i++) //将tmp数组中的临时有序序列传回a_数组
{
a_[l + i] = tmp[i];
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
merge_sort(a, 1, n);
for (int i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
例题
洛谷 P1309 | [NOIP2011 普及组] 瑞士轮
请参阅
【OI考古】基础算法 | 排序
https://blog.vonbrank.com/posts/oi-basic-algorithm-sort/