简单算法的模板代码
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了简单算法的模板代码，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6659字，纯文字阅读大概需要10分钟。
内容图文
前言：该篇博客主要记录一些算法的模板代码，比较简单就不赘述其解决的思路，如确实有不明白的可以在评论区留言，谢谢阅读~
文章目录
two pointers
给定一个递增或递减的序列和一个正整数 M，求两个不同位置上的数 a 和 b，使得 a + b = M。
while (i < j)
{
if (a[i] + a[j] == M)
{
printf("%d %d\n", i, j);
++i; --j;
}
else (a[i] + a[j] < M)
++i;
else
--j;
}
序列合并
假设有两个递增（递减）序列 A 与 B，要求将它们合并为一个新的递增序列 C。
// n 和 m 分别为两个序列的长度
int merge(int A[], int B[], int C[], int n, int m)
{
int i = 0, j = 0, index = 0; // i 指向 A[0], b 指向 B[0]
while (i < n && j < m)
{
if (A[i] <= B[j])
C[index++] = A[i++]; // 将 A[i] 加入序列 C
else
C[index++] = B[j++]; // 将 B[j] 加入序列 C
}
while (i < n) C[index++] = A[i++]; // 将序列 A 的剩余元素加入序列 C
while (j < m) C[index++] = B[j++]; // 将序列 B 的剩余元素加入序列 C
return index;
}
归并排序
2-路归并排序
递归实现
const int maxn = 100;
// 将数组 A 的 [L1, R1] 与 [L2, R2] 区间合并为有序区间，此处 L2 即为 L1 加一
int merge(int A[], int L1, int R1, int L2, int R2)
{
int i = L1, j = L2; // i 指向 A[L1], b 指向 B[L2]
int temp[maxn], index = 0;
while (i <= R1 && j < = R2)
{
if (A[i] <= A[j])
temp[index++] = A[i++]; // 将 A[i] 加入序列 temp
else
temp[index++] = A[j++]; // 将 A[j] 加入序列 temp
}
while (i <= R1) temp[index++] = A[i++]; // 将 [L1, R1] 的剩余元素加入序列 temp
while (j <= R2) temp[index++] = A[j++]; // 将 [L2, R2] 的剩余元素加入序列 temp
for (i = 0; i < index; ++i)
A[L1 + i] = temp[i]; // 将合并后的序列赋值回数组 A
}
// 将 array 数组当前区间 [left, right] 进行归并排序
void mergeSort(int A[], int left, int right)
{
if (left < right) // 只要 left 不小于 right
{
int mid = (left + right) / 2; // 取 [left, right] 的中点
mergeSort(A, left, mid); // 递归，将左子区间 [left, mid] 归并排序
mergeSort(A, mid + 1, right); // 递归，将右子区间 [mid + 1, right] 归并排序
merge(A, left, mid, mid + 1, right); // 将左右子区间合并
}
}
非递归实现
void mergeSort(int A[])
{
// step 为组内元素个数，step / 2 为左子区间元素个数，注意等号可以不取
for (int step = 2; step / 2 <= n; step *= 2)
{
// 每 step 个元素一组，组内前 step / 2 和后 step / 2 个元素进行合并
for (int i = 1; i <= n; i += step) // 对每一组
{
int mid = i + step / 2 - 1; // 左子区间元素个数为 step / 2
if (mid + 1 <= n) // 右子区间存在元素则合并
// 左子区间为 [i, mid]，右子区间为 [mid + 1, min(i + step - 1), n]
merge(A, i, mid, mid + 1, min((i + step - 1), n));
}
}
}
如果题目中只要求给出归并排序每一趟结束时的序列，那么完全可以使用 sort 函数来代替 merge函数（只要时间限制允许），如下所示：
void mergeSort(int A[])
{
// step 为组内元素个数，step / 2 为左子区间元素个数，注意等号可以不取
for (int step = 2; step / 2 <= n; step *= 2)
{
// 每 step 个元素一组，组内前 step / 2 和后 step / 2 个元素进行合并
for (int i = 1; i <= n; i += step) // 对每一组
{
sort(A + i, A + min(i + step, n + 1));
}
// 此处输出归并排序的某一趟结束的序列
}
}
快速排序
普通快排
// 对区间 [left, right] 进行划分
int Partition(int A[], int left, int right)
{
int temp = A[left]; // 将 A[left] 存放至临时变量 temp
while (left < right) // 只要 left 与 right 不相遇
{
while (left < right && A[right] > temp)
--right; // 反复左移 right
A[left] = A[right]; // 将 A[right] 挪到 A[left]
while (left < right && A[left] <= temp)
++left; // 反复右移 left
A[right] = A[left]; // 将 A[left] 挪到 A[right]
}
A[left] = temp; // 把 temp 放到 left 与 right 相遇的地方
return left; // 返回相遇的下标
}
// 快速排序，left 与 right 初值为序列首尾下标（例如1与 n）
void QuickSort(int A[], int left, int right)
{
if (left < right) // 该条件为真同时也表示当前区间的长度超过1
{
// 将 [left, right] 按 A[left] 一分为二
int pos = Partition(A, left, right);
QuickSort(A, left, pos - 1); // 对左子区间递归进行快排
QuickSort(A, pos + 1, right); // 对右子区间递归进行快排
}
}
快速排序算法当序列中元素的排列比较随机时效率较高，但是当序列中元素接近有序时会达到最低时间复杂度 O ( n 2 ) O(n^2) O(n2)，产生这种情况的主要原因在于组员没有把当前区间划分为两个长度接近的子区间。解决这个问题的办法就是随机选择主元，这样对于任意输入数据的期望时间复杂度都能达到 O ( n l o g n ) O(nlogn) O(nlogn)，也就是说不存在一组特定的数据能使这个算法出现最坏情况。
生成随机数
生成十个随机数的代码：
#include<cstdio>
#include<cstdlib> // C 语言中为 stdlib.h
#include<ctime> // C 语言中为 time.h
int main()
{
srand((unsigned)time(NULL));
for (int i = 0; i < 10; ++i)
printf("%d ", rand());
return 0;
}
要注意，rand() 函数只能生成 [0, RAND_MAX] 范围内的整数，RAND_MAX 是 stdlib.h 中的一个常数，不同系统中值不同（注意不是 int 或 long 表示的范围）。如果要输出给定范围 [a, b] 内的随机数，需要使用 rand() % (b - a + 1)，它输出的范围是 [0, b - a]（通俗来讲，rand() % N 的范围就是 [0, N - 1]），再加上 a 之后就是 [a, b] 了。
#include<cstdio>
#include<cstdlib> // C 语言中为 stdlib.h
#include<ctime> // C 语言中为 time.h
int main()
{
srand((unsigned)time(NULL));
for (int i = 0; i < 10; ++i)
printf("%d ", rand() % 2); // [0, 1]
printf("\n");
for (int i = 0; i < 10; ++i)
printf("%d ", rand() % 5 + 3); // [3, 7]
return 0;
}
但是上面的做法只对左右端点相差不超过 RAND_MAX 的区间的随机数有效，如果需要生成更大的数就不行了。要生成大范围的随机数有以下几种做法：
- 多次生成 rand 随机数，然后用位运算拼接起来；
- 将两个 rand 随机数相乘；
- 随机选每一个数位的值，然后拼成一个大整数。
这里采用另一个做法：先用 rand() 生成一个 [0, RAND_MAX] 范围内的随机数，然后将这个随机数除以 RAND_MAX，这样就会得到一个 [0, 1] 范围内的浮点数。接下来只需要将这个浮点数乘以 (b - a)，再加上 a 即可，即 (int)(round(1.0 * rand() / RAND_MAX * (b - a) + a))，相当于这个浮点数就是 [a, b] 范围内的比例位置。如下为生成一个 [10000, 60000] 范围内的随机数的示例：
由于 rand() 生成的随机数是整数，所以需要乘上1.0转换为浮点数。
#include<cstdio>
#include<cstdlib> // C 语言中为 stdlib.h
#include<ctime> // C 语言中为 time.h
int main()
{
srand((unsigned)time(NULL));
for (int i = 0; i < 10; ++i)
printf("%d ", (int)(round(1.0 * rand() / RAND_MAX * 50000 + 10000)));
return 0;
}
在此基础上将随机数引入快排，不妨生成一个范围在 [left, right] 内的随机数 p，然后以 A[p] 作为主元来进行划分。具体做法是：将 A[p] 与 A[left] 交换，然后按原先 Partition 函数的写法即可，代码如下：
// 选取随机主元，对区间 [left, right] 进行划分
int Partition(int A[], int left, int right)
{
// 生成 [left, right] 内的随机数 p
int p = (round(1.0 * rand() / RAND_MAX * (right - left) + left));
swap(A[p], A[left]); // 交换 A[p] 与 A[left]
int temp = A[left]; // 将 A[left] 存放至临时变量 temp
while (left < right) // 只要 left 与 right 不相遇
{
while (left < right && A[right] > temp)
--right; // 反复左移 right
A[left] = A[right]; // 将 A[right] 挪到 A[left]
while (left < right && A[left] <= temp)
++left; // 反复右移 left
A[right] = A[left]; // 将 A[left] 挪到 A[right]
}
A[left] = temp; // 把 temp 放到 left 与 right 相遇的地方
return left; // 返回相遇的下标
}
内容总结
以上是互联网集市为您收集整理的简单算法的模板代码全部内容，希望文章能够帮你解决简单算法的模板代码所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。