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]) {
                // 交换元素
                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("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2. 快速排序（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) {
        int pi = partition(arr, low, high);
        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("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

3. 二分查找（Binary Search）

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n-1, x);
    if (result == -1)
        printf("Element is not present in array\n");
    else
        printf("Element is present at index %d\n", result);
    return 0;
}

4. 斐波那契数列（Fibonacci Sequence）

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    int n = 10;
    printf("Fibonacci sequence up to %d terms: \n", n);
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

5. 插入排序（Insertion Sort）

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

6. 选择排序（Selection Sort）

#include <stdio.h>

void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        swap(&arr[min_idx], &arr[i]);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

7. 归并排序（Merge Sort）

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    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 mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printf("Given array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    return 0;
}

8. 堆排序（Heap Sort）

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

9. 线性查找（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;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 10;
    int result = linearSearch(arr, n, x);
    if (result == -1)
        printf("Element is not present in array\n");
    else
        printf("Element is present at index %d\n", result);
    return 0;
}

10. 递归求阶乘（Factorial）

#include <stdio.h>

int factorial(int n) {
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

int main() {
    int n = 5;
    printf("Factorial of %d is %d\n", n, factorial(n));
    return 0;
}

11. 递归求最大公约数（GCD）

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a = 60, b = 48;
    printf("GCD of %d and %d is %d\n", a, b, gcd(a, b));
    return 0;
}

12. 递归求幂（Power）

#include <stdio.h>

double power(double base, int exp) {
    if (exp == 0)
        return 1;
    if (exp > 0)
        return base * power(base, exp - 1);
    return 1 / power(base, -exp);
}

int main() {
    double base = 2.0;
    int exp = 3;
    printf("%.2f^%d = %.2f\n", base, exp, power(base, exp));
    return 0;
}

13. 递归求数组和（Array Sum）

#include <stdio.h>

int arraySum(int arr[], int n) {
    if (n <= 0)
        return 0;
    return arr[n-1] + arraySum(arr, n-1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Sum of array is %d\n", arraySum(arr, n));
    return 0;
}

14. 递归求数组最大值（Array Max）

#include <stdio.h>

int arrayMax(int arr[], int n) {
    if (n == 1)
        return arr[0];
    int max = arrayMax(arr, n-1);
    return (arr[n-1] > max) ? arr[n-1] : max;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Max of array is %d\n", arrayMax(arr, n));
    return 0;
}

15. 递归求数组最小值（Array Min）

#include <stdio.h>

int arrayMin(int arr[], int n) {
    if (n == 1)
        return arr[0];
    int min = arrayMin(arr, n-1);
    return (arr[n-1] < min) ? arr[n-1] : min;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Min of array is %d\n", arrayMin(arr, n));
    return 0;
}

16. 递归求数组平均值（Array Average）

#include <stdio.h>

double arrayAverage(int arr[], int n) {
    if (n == 1)
        return arr[0];
    return (arr[n-1] + (n-1) * arrayAverage(arr, n-1)) / n;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Average of array is %.2f\n", arrayAverage(arr, n));
    return 0;
}

17. 递归求数组逆序（Array Reverse）

#include <stdio.h>

void arrayReverse(int arr[], int start, int end) {
    if (start >= end)
        return;
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    arrayReverse(arr, start+1, end-1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    arrayReverse(arr, 0, n-1);
    printf("Reversed array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

18. 递归求数组是否有序（Array Sorted）

#include <stdio.h>

int isArraySorted(int arr[], int n) {
    if (n == 1)
        return 1;
    if (arr[n-1] < arr[n-2])
        return 0;
    return isArraySorted(arr, n-1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isArraySorted(arr, n))
        printf("Array is sorted\n");
    else
        printf("Array is not sorted\n");
    return 0;
}

19. 递归求数组是否包含元素（Array Contains）

#include <stdio.h>

int arrayContains(int arr[], int n, int x) {
    if (n == 0)
        return 0;
    if (arr[n-1] == x)
        return 1;
    return arrayContains(arr, n-1, x);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 3;
    if (arrayContains(arr, n, x))
        printf("Array contains %d\n", x);
    else
        printf("Array does not contain %d\n", x);
    return 0;
}

20. 递归求数组元素个数（Array Count）

#include <stdio.h>

int arrayCount(int arr[], int n, int x) {
    if (n == 0)
        return 0;
    if (arr[n-1] == x)
        return 1 + arrayCount(arr, n-1, x);
    return arrayCount(arr, n-1, x);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 3;
    printf("Array contains %d occurrences of %d\n", arrayCount(arr, n, x), x);
    return 0;
}

21. 递归求数组元素位置（Array Index）

#include <stdio.h>

int arrayIndex(int arr[], int n, int x) {
    if (n == 0)
        return -1;
    if (arr[n-1] == x)
        return n-1;
    return arrayIndex(arr, n-1, x);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 3;
    int index = arrayIndex(arr, n, x);
    if (index == -1)
        printf("Array does not contain %d\n", x);
    else
        printf("Array contains %d at index %d\n", x, index);
    return 0;
}