二分查找算法
二分查找：一种在有序数组中查找特定元素的搜索算法
基本思想：
- 在有序数组中，取中间位置的值与待查关键字进行比较
- 如果中间位置的值比关键字大，则在数组的左半部分继续查找；
- 如果中间位置的值比关键字小，则在数组的右半部分继续查找；
- 如果中间位置的值等于关键字，则查找成功。
问题关键：每次比较都会将查找范围缩小一半
代码实现：
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {int left = 0;//标记数组左边界int right = size - 1;//标记数组右边界while (right >= left) {int mid = left + (right - left) / 2;//中间数的下标if (arr[mid] == target) {return mid;//找到目标，返回下标}else if (arr[mid] < target) {//目标在中间值的右边left = mid + 1;//更新左边界}else if(arr[mid]>target){//目标在中间值的左边right = mid - 1;//更新右边界}}return -1;//没找到目标值，返回-1
}快速排序 QuickSort
基本思想：
- 分割——通过一趟排序将要排序的无序表分割成独立的两部分
- 其中一部分的所有数据项都比另外一部分的所有数据项都要小。
- 然后再按此方法对这两部分分别进行快速排序
- 整个排序过程可以递归进行，以此将整个列表变成有序序列。
代码实现：
void swap(int* x, int* y) {int temp = * x;*x = *y;*y = temp;
}int partition(int arr[], int low, int high) {//划分函数，以最后一个元素为基准，找出其下标，令下标左边数比基准小，右边数比基准大int pivot = arr[high];//把最后一个元素作为基准值int i = low - 1;//i用于标记最后一个比基准值小的下标，为什么是i-1，因为下面进入if后需要先进行i++操作for (int j = low; j <= high - 1; j++) {//为什么是j <= high - 1，因为最后一位是基准值，无需被遍历if (arr[j] <= pivot) {//若当前值小于基准值i++;swap(&arr[i] , &arr[j]);//把比基准值小的数从0下标开始放，当遇到本身就比基准值小的数时，自己和自己换}}swap(&arr[i + 1], &arr[high]);//i是最后一个比基准值小数的下标，i + 1这个位置就是基准元素的最终正确位置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);}
}
