快速排序
主要思想是分治:
- 确定分界点
调整范围
递归处理左右两段
代码:
#include <iostream>
using namespace std;
const int N = 1e6+10;
int n,q[N];
void quick_sort(int q[],int l,int r) {
// 左右重合则返回
if (l >= r)
return;
// 选取分界点和双指针
int x = q[(l+r+1)/2],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(q,l,i-1);
quick_sort(q,i,r);
}
int main() {
scanf("%d",&n);
for (int i=0;i<n;i++) {
scanf("%d",&q[i]);
}
quick_sort(q,0,n-1);
for (int i=0;i<n;i++)
printf("%d ",q[i]);
return 0;
}
归并排序
主要思想是分治，快排以一个数来分界，归并以中间来分，并且先递归两边
- 确定分界点
递归排序左右
归并，合二为一
归并排序是稳定的
#include <bits/stdc++.h>
using namespace std;
const int N = 10e6+10;
int n,q[N],temp[N];
void merge_sort(int q[],int l,int r) {
if (l >= r) return;
int mid = l + r >> 1; // 取中点
merge_sort(q,l,mid); // 递归排序左边
merge_sort(q,mid+1,r); // 递归排序右边
int k=0,i=l,j=mid+1;
// 归并 将两个有序序列合并为一个有序序列
while (i <= mid && j <= r) {
if (q[i] <= q[j]) temp[k++] = q[i++];
else temp[k++] = q[j++];
}
// 将未循环完的数直接拼接
while (i <= mid) temp[k++] = q[i++];
while (j <= r) temp[k++] = q[j++];
for (i=l,j=0;i<=r;i++,j++)
q[i] = temp[j];
}
int main(void) {
scanf("%d",&n);
for (int i=0;i<n;i++) {
scanf("%d",&q[i]);
}
merge_sort(q,0,n-1);
for (int i=0;i<n;i++) {
printf("%d ",q[i]);
}
}
二分查找(整数)
按照某种性质将区间一分为二，分成一半满足和另一半不满足
#include <iostream>
using namespace std;
const int N = 10e5 + 10;
int n,m,q[N];
// 检查x是否具有某种性质
bool check(int x) {
// .....
}
// 第一种: 区间[l,r]划分为[l,mid]和[mid+1,r]
int bsearch(int l,int r) {
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
// 第二种: 区间[l,r]划分为[l,mid-1]和[mid,r]
int bsearch(int l,int r) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
二分查找(浮点)
浮点数的二分查找要关注精度
bool check(double x) {
// .....
}
double bsearch(double l,double r) {
const double eps = 1e-6;
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
