第一次上洛谷网校
一：log问题（高中数学）：
https://baike.baidu.com/item/%E5%AF%B9%E6%95%B0/91326?fromtitle=log&fromid=39110&fr=aladdin
二：简单排序
概述：把一个数组排好序。（一般是从小到大）
重要模板
1.选择排序
#include <iostream>
const int MAXN=100001;
using namespace std;
int main() {
int n, k, i, j;
float temp, a[MAXN];
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++){ // i控制当前序列最小值存放的数组位置
k=i;
for(j=i+1;j<n;j++) //j控制从i之后到n序列中选择最小的元素所在位置k
if(a[k]>a[j]) k=j;
if(k!=i){
temp=a[i];
a[i]=a[k];
a[k]=temp;
} //交换a[i]和a[k]将当前最小值放到a[i]位置
}
for(i=0; i<n; i++)
cout<<a[i]<<" ";
return 0;
}
2.插入排序
#include <iostream>
const int MAXN=100001;
using namespace std;
int main() {
float a[MAXN], temp;
int n, i, j, k;
cin>>n;
for (i=0;i<n;i++)
cin>>a[i];
for (i=0;i<n;i++) {
for (j=i-1;j>=0;j--) //为a[i]在前面的有序区域中找一个合适的插入位置
if(a[j]<a[i]) break; //找到比a[i]数据小的位置，退出，插入其后
if(j!=i-1){
temp=a[i]; //将比a[i]大的数据向后移
for(k=i-1; k>j; k--)
a[k+1]=a[k];
a[k+1]=temp; //将a[i]放到正确的位置上
}
}
for (i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
3.冒泡排序
#include <iostream>
const int MAXN=100001;
using namespace std;
int main() {
float temp, a[MAXN];
int n, i, j;
cin>>n; //读入n
for (i=0;i<n;i++) //读入数据
cin>>a[i];
for(i=n-1; i>=1; i--) //进行n-1轮冒泡
for(j=0; j<i; j++) //每轮进行i次的比较
if(a[j]>a[j+1]){ //相邻元素进行比较，如果大的在前面，则交换
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
for(i=0;i<n;i++) //输入排序结果
cout<<a[i]<<" ";
return 0;
}
4.归并排序
#include<bits/stdc++.h>
using namespace std;
void mergearray(int a[],int first,int mid,int last,int temp[]) //将两个有序数组合并排序
{
int i=first,j=mid+1;
int m=mid,n=last;
int k=0;
while(i<=m&&j<=n)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=m)
temp[k++]=a[i++];
while(j<=n)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[first+i]=temp[i];
}
void mergesort(int a[],int first,int last,int temp[]) //将两个任意数组合并排序
{
if(first<last)
{
int mid=(first+last)/2;
mergesort(a,first,mid,temp); //左边有序
mergesort(a,mid+1,last,temp); //右边有序
mergearray(a,first,mid,last,temp); //再将两个有序数组合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n]; //分配一个有n个int型元素的数组所占空间，并将该数组的第一个元素的地址赋给int *型指针p。
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
int main()
{
int a[1005];
int temp[1005];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1,temp);
for(int i=0;i<n;i++)
printf("%d ",a[i]);
}
5.桶排序（模板 略）
6.快速排序 #include <cstdio> using namespace std; void qsort(int,int); int a[100001]; int main() { int n, i; scanf("%d", &n); for(i=1; i<=n; i++) scanf("%d", &a[i]); qsort(1, n); for(i=1; i<=n; i++) printf("%d ",a[i]); } void qsort(int l, int r){ int i, j, mid, p; i=l;j=r; mid=a[(l+r)/2]; while(i<=j){ while (a[i]<mid) i++; while (a[j]>mid) j--; if(i<=j) { p=a[i]; a[i]=a[j]; a[j]=p; i++;j--; } } if(l<j) qsort(l,j); if(i<r) qsort(i,r); }
//这道题洛谷上有P1177
7.归并排序
void msort(int s,int t)
{
if(s==t) return; //如果只有一个数字则返回，无须排序
int mid=(s+t)/2;
msort(s,mid); //分解左序列
msort(mid+1,t); //分解右序列
int i=s, j=mid+1, k=s; //接下来合并
while(i<=mid && j<=t)
{
if(a[i]<=a[j])
{
r[k]=a[i]; k++; i++;
}else{
r[k]=a[j]; k++; j++;
}
}
while(i<=mid) //复制左边子序列剩余
{
r[k]=a[i]; k++; i++;
}
while(j<=t) //复制右边子序列剩余
{
r[k]=a[j]; k++; j++;
}
for(int i=s; i<=t; i++) a[i]=r[i];
return 0;
}
STL sort
#include<algorithm>
三：模拟
顾名思义 题目叫你干嘛你就干嘛
例题见：
https://www.cnblogs.com/2019computer/p/12248762.html
原文：https://www.cnblogs.com/2019computer/p/12293479.html