????????算法是解決問題的核心。無論是排序、搜索，還是遞歸與動態規劃，算法的選擇和實現對程序的效率和性能有著重要影響。本節將介紹幾種常見的算法，包括排序算法、搜索算法，以及遞歸和動態規劃的應用。

排序算法

????????排序算法是將一組數據按特定順序排列的過程。常見的排序算法有冒泡排序、選擇排序、插入排序、快速排序和歸并排序等。下面是幾種常見排序算法的介紹和示例代碼。

冒泡排序

????????冒泡排序通過多次遍歷數組，每次比較相鄰的元素，如果順序錯誤就交換，直到整個數組有序，例如：

#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("排序后的數組: ");for (int i = 0; i < n; i++)printf("%d ", arr[i]);return 0;
}

選擇排序

????????選擇排序每次從未排序部分中選出最小（或最大）的元素，放到已排序部分的末尾，例如：

#include <stdio.h>void selectionSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {int minIndex = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[minIndex])minIndex = j;}int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}
}int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr)/sizeof(arr[0]);selectionSort(arr, n);printf("排序后的數組: ");for (int i = 0; i < n; i++)printf("%d ", arr[i]);return 0;
}

快速排序

????????快速排序通過選擇一個基準元素，將數組分成兩部分，一部分所有元素比基準元素小，另一部分所有元素比基準元素大，然后遞歸地對這兩部分進行排序，例如：

#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("排序后的數組: ");for (int i = 0; i < n; i++)printf("%d ", arr[i]);return 0;
}

搜索算法

????????搜索算法用于在數據集合中查找特定元素。常見的搜索算法有線性搜索和二分搜索。

線性搜索

????????線性搜索逐一比較數據集合中的每個元素，直到找到目標元素或搜索完所有元素，例如：

#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 x = 10;int n = sizeof(arr)/sizeof(arr[0]);int result = linearSearch(arr, n, x);if(result == -1)printf("元素不在數組中\n");elseprintf("元素在數組中的索引: %d\n", result);return 0;
}

二分搜索

????????二分搜索在有序數組中查找目標元素，通過反復將搜索范圍縮小為一半，直到找到目標元素或搜索范圍為空，例如：

#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;elser = m - 1;}return -1;
}int main() {int arr[] = {2, 3, 4, 10, 40};int x = 10;int n = sizeof(arr)/sizeof(arr[0]);int result = binarySearch(arr, 0, n-1, x);if(result == -1)printf("元素不在數組中\n");elseprintf("元素在數組中的索引: %d\n", result);return 0;
}

遞歸與動態規劃

遞歸

????????是指一個函數調用其自身。遞歸算法通常用于解決分治問題，例如斐波那契數列和階乘，例如：

#include <stdio.h>int fibonacci(int n) {if (n <= 1)return n;return fibonacci(n - 1) + fibonacci(n - 2);
}int main() {int n = 9;printf("Fibonacci數列的第%d項是: %d\n", n, fibonacci(n));return 0;
}

動態規劃

????????是一種將復雜問題分解為更小子問題的技術，通過記憶化或表格化存儲子問題的結果，避免重復計算，提升算法效率，例如：

#include <stdio.h>int fibonacci(int n) {int f[n+1];f[0] = 0;f[1] = 1;for (int i = 2; i <= n; i++) {f[i] = f[i-1] + f[i-2];}return f[n];
}int main() {int n = 9;printf("Fibonacci數列的第%d項是: %d\n", n, fibonacci(n));return 0;
}

總結

????????排序算法、搜索算法以及遞歸與動態規劃是C語言編程中不可或缺的重要部分。通過掌握這些算法，將能夠高效地處理和操作數據，解決復雜的編程問題。學習和理解這些基礎算法，不僅有助于提升編程能力，也為解決實際問題打下堅實的基礎。