你需要知道,人的事业就如同浪潮,如果你踩到浪头,功名随之而来;而一旦错失,则终其一生都将受困于浅滩与悲哀。
——《洛克菲勒写给儿子的38封信》
大家好哇,这里是小编记录算法模板的宝地啦,其中也会包含小编平时学习的一些心得。现在,让我们一起进入算法的世界吧~
1.快速排序
快速排序是在冒泡排序基础上的改进,其基本思想是基于分治。
在写代码之前最好是找到自己要写代码的大致步骤:
To:在找分界点时,当数据加强后最好是不要选择两边端点的值,之前小编便遇到过内存过载的ERROR。
按照教材上说的,我们在进行快排时会使用两个数组,用于存放两个区间的值,存放之前还会对之前的数据进行扫描,对于时间复杂度和空间复杂度都是不小的开销。
y总提供了一种优美的解决方案,即用两个指针分别指向数据集的两端i、j,再取其分界点x。
大致思路是i和j分别向中间走,其中当i大于x时便停下来,j小于x时也是【假设从小到大排序】。然后当i和j两个指针都停下来,便交换两边的值。最后当两个指针相遇时,便确保了一个区间的值是小于x的,另一个区间的值大于x的。
快速排序例子:
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼10的9次方范围内),表示整个数列。
输出格式
输出共一行,包含 n个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
源代码:
#include <iostream>
const int N=1e6+10;
int a[N];
void Sorttest(int l,int r){
if(l>=r){
return ;
}
//判断数据集
int i=l-1,j=r+1;
int x=a[(l+r)/2];
//取中间值
while(i<j){
do i++;while(a[i]<x);
do j--; while(a[j]>x);
if(i<j){
std::swap(a[i],a[j]);
//交换数据
}
}
Sorttest(l,j);Sorttest(j+1,r);
//分别处理两个区间的数据
}
int main(){
using namespace std;
int n,i;
cin>>n;
//输入排序数据集
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
//Sorttest函数进行排序
Sorttest(0,n-1);
//使用循环输出排序后的数据
for(i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}
快速排序模板:
void Sorttest(int l,int r){
if(l>=r){
return ;
}
int i=l-1,j=r+1;
int x=a[(l+r)/2];
while(i<j){
do i++;while(a[i]<x);
do j--; while(a[j]>x);
if(i<j){
std::swap(a[i],a[j]);
}
}
Sorttest(l,j);Sorttest(j+1,r);
}
To:可能会有人问为啥会有模板,在处理大部分排序时,模板都能起到很大的作用,平时可以多敲敲模板,关于临界值的处理则需要自己去记忆了。
2.归并排序
归并排序是一种稳定的排序,而快速排序则是一种不稳定的,归并排序也基于分治。
To:原序列中2个数相同,位置不发生变化我们便说这个排序是稳定的;反之则是不稳定的。
大致思路步骤为:
在归并排序中,我们也用到两个指针,分别指向排好序数据的最左端,并开始比较,值小的就拿出来【以从小到大排序】放入另一个数组中,依次比较,如果遇到相等的数,我们倾向于将第一个序列的值先放入另一个数组中;如果当第一个指针指向序列的最后一个值时,我们便把另一个序列直接补到数组后面。
归并排序例子:
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼10的9次方范围内),表示整个数列。
输出格式
输出共一行,包含 n个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
源代码:
#include<iostream>
using namespace std;
const int N = 1000010;
int a[N], temp[N], n;
void Sorttest(int a[], int l, int r) {
if (l >= r) {
return;
}
//判断数据集
int mid = l + r >> 1;
//取中间值
Sorttest(a, l, mid);
Sorttest(a, mid + 1, r);
//递归左右两边
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
//排序:比较大小,将较小的数据放入temp数组中
while (i <= mid) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
//判断某一个序列是否未放入temp数组中,并将其放入
for (i = l, j = 0; i <= r; i++, j++) {
a[i] = temp[j];
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
Sorttest(a, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
归并排序模板:
void Sorttest(int a[], int l, int r) {
if (l >= r) {
return;
}
int mid = l + r >> 1;
Sorttest(a, l, mid);
Sorttest(a, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
while (i <= mid) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (i = l, j = 0; i <= r; i++, j++) {
a[i] = temp[j];
}
}
平时也可多敲敲模板哦!