C语言中的经典算法：从基础到高级

引言

C语言作为一种高效、灵活的编程语言，广泛应用于各种软件开发领域。其中，算法是编程的核心之一，它决定了程序的效率和性能。本文将介绍一些经典的C语言算法，帮助初学者理解并掌握这些重要的概念。

1. 排序算法

排序算法是计算机科学中最基本的算法之一。常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序和归并排序等。下面我们以冒泡排序为例进行介绍。

冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。由于它的实现简单，但在处理大数据集时效率较低，因此常被用于教学目的。

#include <stdio.h>
void bubbleSort(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]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("排序后的数组: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

快速排序（Quick Sort）

快速排序是一种高效的排序算法，采用分治法策略。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的记录关键字小，然后分别对这两部分继续进行排序，以达到整个序列有序。

#include <stdio.h>
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
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++; // 增加较小元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区索引，arr[pi] 已经排好序
        int pi = partition(arr, low, high);
        // 分别对 pi 左边和右边的元素进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("排序后的数组: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2. 查找算法

查找算法是根据给定的条件在数据集合中寻找特定元素的过程。常见的查找算法包括线性查找和二分查找等。

线性查找（Linear Search）

线性查找是最简单的查找算法，逐个比较数组中的元素直到找到目标元素或遍历完整个数组。

#include <stdio.h>
int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i; // 返回目标元素的索引
        }
    }
    return -1; // 如果未找到，返回-1
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int x = 10;
    int n = sizeof(arr)/sizeof(arr[0]);
    int result = linearSearch(arr, n, x);
    if (result == -1) {
        printf("元素 %d 不在数组中", x);
    } else {
        printf("元素 %d 在数组中的索引是 %d", x, result);
    }
    return 0;
}

二分查找（Binary Search）

二分查找是一种高效的查找算法，适用于有序数组。它通过将目标值与数组的中间元素进行比较，从而缩小查找范围。

#include <stdio.h>
int binarySearch(int arr[], int n, int x) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            return mid; // 返回目标元素的索引
        }
        if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 如果未找到，返回-1
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int x = 10;
    int n = sizeof(arr)/sizeof(arr[0]);
    int result = binarySearch(arr, n, x);
    if (result == -1) {
        printf("元素 %d 不在数组中", x);
    } else {
        printf("元素 %d 在数组中的索引是 %d", x, result);
    }
    return 0;
}

3. 递归与分治

递归和分治是两种重要的编程技巧，它们在算法设计中有着广泛的应用。

递归（Recursion）

递归是指函数调用自身的过程。递归通常用于解决那些可以分解为相同类型但规模较小的问题的情况。

#include <stdio.h>
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
int main() {
    int number = 5;
    printf(" %d 的阶乘是 %d", number, factorial(number));
    return 0;
}

分治（Divide and Conquer）

分治法将问题分解为更小的子问题，分别解决这些子问题，然后将结果合并以得到最终答案。经典的分治算法包括归并排序和快速排序等。

4. 动态规划

动态规划是一种通过将复杂问题分解为更小的子问题来解决的技术。它通常用于优化递归算法，避免重复计算。

斐波那契数列（Fibonacci Sequence）

斐波那契数列是一个经典的动态规划问题。我们可以使用记忆化技术来存储已经计算过的结果，从而提高效率。

#include <stdio.h>
#include <stdlib.h>
int fibonacci(int n, int *memo) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
    return memo[n];
}
int main() {
    int n = 10;
    int *memo = (int *)malloc((n+1) * sizeof(int));
    for (int i = 0; i <= n; i++) {
        memo[i] = -1;
    }
    printf("斐波那契数列的第 %d 项是 %d", n, fibonacci(n, memo));
    free(memo);
    return 0;
}