【算法】编程拓展-C语言-期末复习

二分查找算法

二分查找：一种在有序数组中查找特定元素的搜索算法

基本思想：

在有序数组中，取中间位置的值与待查关键字进行比较
如果中间位置的值比关键字大，则在数组的左半部分继续查找；
如果中间位置的值比关键字小，则在数组的右半部分继续查找；
如果中间位置的值等于关键字，则查找成功。

问题关键：每次比较都会将查找范围缩小一半

代码实现：

#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

基本思想：

分割——通过一趟排序将要排序的无序表分割成独立的两部分
其中一部分的所有数据项都比另外一部分的所有数据项都要小。
然后再按此方法对这两部分分别进行快速排序
整个排序过程可以递归进行，以此将整个列表变成有序序列。

案例：快速查找数组中给定次序的元素从一组未排序的数中选出第k大的数。

代码实现：

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);}
}
//快速选择算法，找第k大的数
int quickSearch(int arr[], int low, int high,int k) {//用分区算法对数组分区，找出基准值的下标int povitIndex = partition(arr, low, high);//看基准值是第几大的数int pos = high - povitIndex + 1;//由于基准值右边的数比它大，high - povitIndex计算出基准值右边还剩几个比它大的数//high - povitIndex + 1 可以知道基准值对应的是“第几大”的数if (pos == k) {return arr[povitIndex];//基准值的位置刚好就是要找的第k大的位置}else if (pos > k) {//例如pos是第三大，k是第一大，说明k比pos位置的数大，在pos数的右边quickSearch(arr, povitIndex + 1, high, k);//就从pivotIndex + 1到high这个范围）再调用quickSelect函数去找第k大的数}else {//pos < k 例如pos位置是第二大，k是第三大，k比pos的数小，k在pos数的左边quickSearch(arr, low, povitIndex - 1, k - pos);//要注意，去掉右边那些比pos数大（也比k数大）的数后，我们在左边要找第 k - pos大的数}}

经典排序算法对比

归并排序

模式图：

代码：

// 合并两个已排序的子数组
// 这个函数的作用就是把两个已经各自排好序的子数组合并成一个有序的数组
// 参数说明：
// arr是要进行操作的原始数组，里面包含了要合并的两个子数组
// l是左边子数组在原数组中的起始下标
// m是左边子数组在原数组中的结束下标（同时也是右边子数组在原数组中的起始下标减1）
// r是右边子数组在原数组中的结束下标
void merge(int arr[], int l, int m, int r) {int i, j, k;// n1表示左边子数组的元素个数，通过计算分割点m与起始下标l的差值再加1得到int n1 = m - l + 1;// n2表示右边子数组的元素个数，通过计算原数组结束下标r与分割点m的差值得到int n2 = r - m;// 创建临时数组// 创建一个名为L的临时数组，用来存放左边的子数组元素，大小就是左边子数组的元素个数n1int* L = (int*)malloc(n1 * sizeof(int));// 创建一个名为R的临时数组，用来存放右边的子数组元素，大小就是右边子数组的元素个数n2int* R = (int*)malloc(n2 * sizeof(int));// 拷贝数据到临时数组L和R// 下面这个循环就是把原数组中左边子数组的元素依次拷贝到临时数组L中for (i = 0; i < n1; i++)L[i] = arr[l + i];// 下面这个循环就是把原数组中右边子数组的元素依次拷贝到临时数组R中for (j = 0; j < n2; j++)R[j] = arr[m + 1 + j];// 合并临时数组回到原数组// 初始化三个下标，i用来遍历临时数组L，j用来遍历临时数组R，k用来确定原数组中放置元素的位置i = 0;j = 0;k = l;// 只要临时数组L和R中都还有元素没处理完，就进行下面的比较和放置操作while (i < n1 && j < n2) {// 比较临时数组L和R当前位置的元素大小，如果L中的元素小于等于R中的元素if (L[i] <= R[j]) {// 就把L中当前位置的元素放到原数组对应位置（由k确定）arr[k] = L[i];// 然后L数组中用于遍历的下标i往后移动一位，准备处理下一个元素i++;}else {// 反之，如果R中的元素更小，就把R中当前位置的元素放到原数组对应位置（由k确定）arr[k] = R[j];// 然后R数组中用于遍历的下标j往后移动一位，准备处理下一个元素j++;}// 不管放的是L还是R中的元素，原数组放置元素的下标k都要往后移动一位，为放置下一个元素做准备k++;}// 拷贝L中剩余元素// 如果临时数组L中还有剩余的元素（也就是前面比较的时候，R中的元素先用完了）while (i < n1) {// 就把L中剩余的元素依次拷贝到原数组后面对应的位置上arr[k] = L[i];i++;k++;}// 拷贝R中剩余元素// 如果临时数组R中还有剩余的元素（也就是前面比较的时候，L中的元素先用完了）while (j < n2) {// 就把R中剩余的元素依次拷贝到原数组后面对应的位置上arr[k] = R[j];j++;k++;}// 释放临时数组内存// 因为前面创建临时数组的时候是动态分配内存的，现在用完了就要释放掉，避免内存泄漏free(L);free(R);
}// 归并排序主函数
// 这个函数就是用来实现归并排序的整体逻辑，通过不断地把数组分割成子数组然后合并来实现排序
// 参数说明：
// arr是要进行排序的原始数组
// l是当前要处理的子数组在原数组中的起始下标
// r是当前要处理的子数组在原数组中的结束下标
void mergeSort(int arr[], int l, int r) {// 如果起始下标l小于结束下标r，说明这个子数组的长度大于1，还需要继续分割排序if (l < r) {// 先计算出当前子数组的中间位置，这样就可以把当前子数组分割成左右两部分int m = l + (r - l) / 2;// 对左半部分排序// 通过递归调用mergeSort函数，继续对左边的子数组进行归并排序mergeSort(arr, l, m);// 对右半部分排序// 通过递归调用mergeSort函数，继续对右边的子数组进行归并排序mergeSort(arr, m + 1, r);// 合并已排序的两部分// 当左右两边的子数组都排好序后，调用merge函数把这两部分合并成一个有序的子数组merge(arr, l, m, r);}
}