查找算法
1. 順序查找（哨兵法）
int search(int array[], int n, int k) {
int i = n-1;
array[0] = k; // 設置哨兵
while (array[i] != k) i--;
return i; // 返回下標，0 表示未找到
}
2. 折半查找（前提：數組有序）
int halfsearch(int array[], int n, int k) {
int i = 1, j = n, mid;
while (i <= j) {
mid = (i + j) / 2;
if (k == array[mid]) return mid;
else if (k < array[mid]) j = mid - 1;
else i = mid + 1;
}
return 0; // 未找到
}
排序算法
1. 冒泡排序
void mpsort(int array[]) {
int i, j, a;
for (i = 1; i < N; i++)
for (j = i+1; j < N; j++)
if (array[i] > array[j]) {
a = array[i]; array[i] = array[j]; array[j] = a;
}
}
2. 直接插入排序
void insertsort(int array[]) {
int i, j;
for (i = 2; i < N; i++) {
array[0] = array[i]; // 哨兵暫存待插元素
j = i - 1;
while (array[0] < array[j]) {
array[j+1] = array[j--];
}
array[j+1] = array[0];
}
}
主程序交互演示
#define N 11
void creat(int a[]) { for(i=1;i
複雜度速查
| 算法 | 平均時間 | 最壞時間 | 空間 | 穩定性 |
|---|
| 順序查找 | O(n) | O(n) | O(1) | 穩定 |
| 折半查找 | O(log n) | O(log n) | O(1) | 穩定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 穩定 |
| 直接插入 | O(n²) | O(n²) | O(1) | 穩定 |
