c語(yǔ)言的經(jīng)典算法

一、排序算法
冒泡排序 (Bubble Sort)

原理：通過(guò)相鄰元素兩兩比較交換，使最大元素逐漸"浮"到數(shù)組末尾。

時(shí)間復(fù)雜度：O(n2)

代碼片段：
c
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])
swap(&arr[j], &arr[j+1]);
}

快速排序 (Quick Sort)

原理：分治思想，選取基準(zhǔn)元素將數(shù)組分為左右兩部分遞歸排序。

時(shí)間復(fù)雜度：平均O(n log n)，最壞O(n2)

核心代碼：
c
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j=low; j<high; j++)
if (arr[j] < pivot) swap(&arr[++i], &arr[j]);
swap(&arr[i+1], &arr[high]);
return i+1;
}
二、查找算法
二分查找 (Binary Search)

前提：有序數(shù)組

時(shí)間復(fù)雜度：O(log n)

代碼邏輯：
c
int binarySearch(int arr[], int l, int r, int target) {
while (l <= r) {
int mid = l + (r-l)/2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) l = mid+1;
else r = mid-1;
}
return -1;
}
三、數(shù)據(jù)結(jié)構(gòu)相關(guān)算法
鏈表逆置 (Reverse Linked List)

核心思想：三指針?lè)ㄐ薷墓?jié)點(diǎn)指向
c
struct Node* reverseList(struct Node* head) {
struct Node *prev = NULL, *curr = head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}

二叉樹(shù)遍歷

深度優(yōu)先 (DFS)：遞歸實(shí)現(xiàn)前序/中序/后序遍歷

廣度優(yōu)先 (BFS)：使用隊(duì)列層序遍歷

四、動(dòng)態(tài)規(guī)劃 (Dynamic Programming)
斐波那契數(shù)列 (Fibonacci)

優(yōu)化：避免遞歸重復(fù)計(jì)算，使用數(shù)組緩存結(jié)果

c
int fib(int n) {
int dp[n+1];
dp[0]=0; dp[1]=1;
for(int i=2; i<=n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
背包問(wèn)題 (0-1 Knapsack)

核心方程：dp[i][w] = max(value[i]+dp[i-1][w-weight[i]], dp[i-1][w])

五、圖算法
Dijkstra最短路徑

適用場(chǎng)景：權(quán)重非負(fù)的有向圖

核心：貪心策略 + 優(yōu)先隊(duì)列優(yōu)化
Floyd-Warshall算法
特點(diǎn)：多源最短路徑，通過(guò)三重循環(huán)動(dòng)態(tài)更新距離矩陣

六、字符串處理
KMP模式匹配

優(yōu)化：通過(guò)部分匹配表跳過(guò)無(wú)效比較

關(guān)鍵：計(jì)算最長(zhǎng)前綴后綴公共長(zhǎng)度（LPS數(shù)組）

七、數(shù)學(xué)算法
歐幾里得算法 (GCD)

c
int gcd(int a, int b) {
return b==0 ? a : gcd(b, a%b);
}
素?cái)?shù)篩法 (埃拉托斯特尼篩法)

用途：高效篩選指定范圍內(nèi)的素?cái)?shù)