C语言常见算法详解及示例：排序、查找、动态规划、分治
C语言常见算法详解及示例
本文将介绍 C语言 中一些常见的算法，并给出解释和示例代码。
1. 排序算法
排序算法用于将一组数据按照一定规则排列。常见的排序算法包括：
- 冒泡排序：比较相邻两个元素的大小，若前者大于后者，则交换两个元素的位置，直到最后一个元素，然后再从头开始进行比较和交换，直到所有元素都排好序为止。
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
- 插入排序：将待排序的元素插入到已排序的序列中合适的位置。
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
- 选择排序：每次从待排序的序列中选择最小的元素，并将其放到已排序序列的末尾。
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
- 快速排序：通过递归的方式将数组划分为两个子数组，分别对子数组进行排序，最后将两个子数组合并成一个有序数组。
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
2. 查找算法
查找算法用于在一个数据集合中查找某个指定的值。常见的查找算法包括：
- 线性查找：从第一个元素开始依次比较，直到找到目标值或遍历完整个集合。
int linear_search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
- 二分查找：首先对已排序的数组取中间值，然后将查找值与中间值进行比较，若相等则返回中间值的位置，若大于中间值则在右半部分继续查找，若小于中间值则在左半部分继续查找，直到找到或者查找到最后一个元素为止。
int binary_search(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
- 哈希查找：将数据映射到一个哈希表中，通过哈希函数计算目标值的哈希值，并根据哈希值直接访问哈希表中的对应位置。
#include <stdio.h>
#include <stdlib.h>
// 哈希函数
int hash(int key) {
return key % 10;
}
// 哈希表
int hash_table[10];
// 插入元素
void insert(int key) {
int index = hash(key);
hash_table[index] = key;
}
// 查找元素
int search(int key) {
int index = hash(key);
if (hash_table[index] == key) {
return index;
}
return -1;
}
int main() {
insert(12);
insert(25);
insert(36);
int key = 25;
int index = search(key);
if (index != -1) {
printf("元素 %d 在哈希表中的索引为 %d\n", key, index);
} else {
printf("元素 %d 不存在于哈希表中\n", key);
}
return 0;
}
3. 动态规划算法
动态规划算法用于解决最优化问题。常见的动态规划算法包括：
- 背包问题：在有限的背包容量下，如何使装入背包中的物品总价值最大。可以使用动态规划算法来解决，通过构建状态转移方程，逐步求解问题的最优解。
#include <stdio.h>
// 物品价值数组
int value[] = {60, 100, 120};
// 物品重量数组
int weight[] = {10, 20, 30};
// 背包容量
int capacity = 50;
// 动态规划算法求解背包问题
int knapsack(int capacity, int n) {
// 创建二维数组存储子问题的解
int dp[n + 1][capacity + 1];
// 初始化第一行和第一列为0
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= capacity; j++) {
dp[0][j] = 0;
}
// 构建状态转移方程
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (weight[i - 1] <= j) {
dp[i][j] = max(value[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
// 返回最大价值
return dp[n][capacity];
}
// 返回两个数中的较大者
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
int max_value = knapsack(capacity, 3);
printf("最大价值为：%d\n", max_value);
return 0;
}
- 最长公共子序列：给定两个字符串，求出它们的最长公共子序列。
#include <stdio.h>
#include <string.h>
// 求解最长公共子序列的动态规划算法
int lcs(char *X, char *Y, int m, int n) {
// 创建二维数组存储子问题的解
int dp[m + 1][n + 1];
// 初始化第一行和第一列为0
for (int i = 0; i <= m; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = 0;
}
// 构建状态转移方程
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 返回最长公共子序列长度
return dp[m][n];
}
// 返回两个数中的较大者
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
int lcs_length = lcs(X, Y, m, n);
printf("最长公共子序列长度为：%d\n", lcs_length);
return 0;
}
4. 分治算法
分治算法将大问题分解为多个小问题，分别求解后再将结果合并。常见的分治算法包括：
- 归并排序：将待排序数组分成两个子数组，然后对每个子数组进行排序，最后将两个子数组合并成一个有序数组的过程，通过不断递归，可以将整个数组进行排序。
void merge_sort(int arr[], int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
void merge(int arr[], int low, int mid, int high) {
int n1 = mid - low + 1;
int n2 = high - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[low + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = low;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
- 快速排序：通过递归的方式将数组划分为两个子数组，分别对子数组进行排序，最后将两个子数组合并成一个有序数组。
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
总结
本文介绍了 C语言 中一些常见的算法，包括排序算法、查找算法、动态规划算法和分治算法。这些算法在不同的应用场景中都有着广泛的应用。希望本文能够帮助读者更好地理解和应用这些算法。
原文地址: https://www.cveoy.top/t/topic/m0Dt 著作权归作者所有。请勿转载和采集!