折半查找（二分查找）
適用于已排序的數組，通過不斷縮小查找范圍定位目標值。
int binarySearch(int arr[], int size, int target) {int left = 0, right = size - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) return mid;if (arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1; // 未找到
}
插入排序
將未排序元素逐個插入已排序部分的正確位置。
void insertionSort(int arr[], int size) {for (int i = 1; i < size; i++) {int key = arr[i], j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}
快速排序
通過分治策略選取基準值，將數組分為左右兩部分遞歸排序。
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}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) {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);}
}
關鍵點
- 折半查找要求數組有序，時間復雜度為 O(log n)。
- 插入排序適合小規模數據，時間復雜度為 O(n2)。
- 快速排序平均時間復雜度為 O(n log n)，需注意基準值選擇。
?
