模板
算法
冒泡排序
void bubble_sort(int* a, int n) {
bool f = 1;
while (f) {
bool f = 0;
for (int i = 1; i < n; i++)
if (a[i] > a[i+1]) swap(a[i], a[i+1]), f = 1;
}
return ;
}
冒泡排序优化
int n;
int a[10005];
void BubbleSort(int n, int a[]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j+1]) swap(a[j], a[j+1]);
}
}
}
插入排序
int n, cnt = 0;// 数组长度 插入数组长度
int a[10005], r[10005];// 原数组 插入数组
void InsertSort(int x) {// 插入 x
int pos = 0;// 记录 x 应插入的位置
while (pos < cnt && r[pos] < x) pos++;// 直到找到大于等于 x 的数
for (int i = cnt; i > pos; i--)
r[i] = r[i-1];// 后移数组
r[pos] = x;
cnt++; // 插入数组长度加一
}
插入排序优化
int n;
int a[10005];
void InsertSort() {
for (int i = 0; i < n; i++) {
int pos = 0, x = a[i];
while (pos < i && a[pos] < a[i]) pos++;
for (int k = i; k > pos; k--)
a[k] = a[k-1];
a[pos] = x;
}
}
归并排序
int n;
int a[10005], t[10005];// a 原数组 t 排序数组
void MergeSort(int l, int r) {
if (l == r - 1) return ;
int mid = (l + r) >> 1;
MergeSort(l, mid); MergeSort(mid, r);
int p = l, q = mid, k = l;
while (p < mid && q < r) {
if (a[p] < a[q]) t[k++] = a[p++];
else t[k++] = a[q++];
}
while (p < mid) t[k++] = a[p++]; // 复制剩余数组
while (q < r) t[k++] = a[q++];
for (int i = l; i < r; i++)
a[i] = t[i];
}
快速排序
int n;
int a[10005], t[10005];
void QuickSort(int l, int r) {
if (l >= r - 1) return ;
int flag = a[rand() % (r - l) + l];
int p = l, q = r;
for (int i = l; i < r; i++) {
if (a[i] < flag) t[p++] = a[i];
else if (a[i] > flag) t[--q] = a[i];
}
for (int i = p; i < q; i++) // 复制剩下等于 flag 的数
t[i] = flag;
for (int i = l; i < r; i++)
a[i] = t[i];
QuickSort(l, p);
QuickSort(q, r);
}
选择排序
int n;
int a[10005];
void SelectSort(int n, int a[]) {
for (int i = 0; i < n; i++) {
int key = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[key]) key = j;
swap(a[i], a[key]);
}
}
选择排序优化
int n;
int a[10005];
void SelectSort(int n, int a[]) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++)
if (a[j] < a[i]) swap(a[j], a[i]);
}
}
二分答案
记录答案
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid; r = mid - 1;
}
else l = mid + 1;
}
printf("%d", ans);
不记录答案
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d", l);
二分查找
查找值为 \(key\) 的元素的下标,不存在返回 \(-1\)
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] == key) return mid;
else if (a[mid] > key) r = mid - 1;
else l = mid + 1;
}
return -1;
快速幂
ll Fast_Power(ll a, ll b, ll p) {
a %= p;
while (b) {
if (b & 1) s = (s * a) % p;
a = (a * a) % p;
b >>= 1;
}
return s % p;
}
标签:10005,int,mid,pos,++,while,合集,模板
From: https://www.cnblogs.com/Gery-blog/p/17152081.html