最基础的查找和排序算法

2023-10-02 03:46| 来源: 网络整理| 查看: 265

二分查找（Binary Search）：通过不停分割成一半，缩小范围，将数组中的数字找到。要求数组有序。

冒泡排序（Bubble Sort）：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序正确就继续向下遍历，否则交换两个相邻元素后再向下遍历。

本篇博客将分别讲述二分查找和冒泡排序，并详细讲解二分查找中main版与函数版的区别，以此可以类比到冒泡排序上。

以下为详细内容讲解一、二分查找1.1 main中实现1.1.1 代码流程及实现 1.2 函数中实现1.2.1 与main版的区别1.2.2 代码流程及实现二、冒泡排序2.1 重难点分析2.1.1 冒泡过程的实现2.1.2 边界值的确认 2.2 代码流程及实现

一、二分查找 1.1 main中实现 1.1.1 代码流程及实现代码实现流程讲解：（1）明确要求： - 二分查找---main版本； - 编写代码在一个整形有序数组中查找具体的某个数； - 具体要求：找到了就打印数字所在的下标，找不到则输出：找不到。（2）计算数组长度，以此计算出数组最大下标；（3）引入变量left、right和mid，分别表示最左、最右和中间的下标；注意：mid的计算公式是mid = left+(right-left) / 2; （4）进入循环，开始寻找数字下标，循环条件取决于left、right，并且每次循环都会更新mid的值（以此达到二分查找的目的）；（5）通过对比要找的数字key与mid对应的数组中数字的大小，分为三种情况进行二分，缩小范围。（6）如果循环结束，还没找到，输出没找到的提示。 #define _CRT_SECURE_NO_WARNINGS 1 #include int main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int key = 0; printf("请输入想要寻找的数字："); scanf("%d", &key); int left = 0; int right = sizeof(arr) / sizeof(arr[0])-1; //通过sizeof来求最大下标 while (left printf("找到了！该数字在数组中的下标为%d\n", mid); break;//!!!不要忘记结束循环 } else if (key left = mid + 1; continue; } } if (left>right){ printf("没有在数组中找到您输入的数字\n"); } return 0; } 1.2 函数中实现 1.2.1 与main版的区别区别于main版的二分查找有以下几点：（1）数组隐式转指针：数组在函数调用或参与运算等情况可能会隐式转为指针，指针又能像数组[]一样取下标，所以尽量写在 main中，然后传参到函数中；（2）各司其职：尽量让每个函数只实现一个功能，所以二分查函数中先不写printf输出功能；（3）return作用：当函数中一旦执行了 return ，那么该方法立即结束执行，并返回 return 后的值,所以本函数中break可以省略。 1.2.2 代码流程及实现代码实现流程：与main版除了第（4）、（6）条在main中进行，其他流程在函数中的实现不改变。 #define _CRT_SECURE_NO_WARNINGS 1 #include int binarySearch(int n,int arr1[],int right){ int left = 0; int mid = left + (right - left) / 2; while (left return mid; /*break;*/ } else if (n left = mid + 1; continue; } } if (left > right){ return -1;//return的值范围与返回值类型有关 } } int main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int num = sizeof(arr) / sizeof(arr[0]) - 1; int key = 0; printf("请输入你想要查找的数字："); scanf("%d", &key); int n=binarySearch(key,arr,num); if (n == -1){ printf("您要找的数字不在该数组中！\n"); } else{ printf("你要查找的数字对应的数组下标为：%d\n", n); } return 0; } 二、冒泡排序 2.1 重难点分析由一开始的介绍可以知道，所谓冒泡排序，就是比较相邻的两个数字，如果符合升序(或者降序)的要求就继续向下遍历，否则将两个连续的数字交换后再进行遍历。冒泡排序的难点体现在两个方面，一、冒泡过程的实现；二、边界值的确认

接下来进行详细的讲解

2.1.1 冒泡过程的实现

假设一个数组arr[ ]={7,6,9,4,2,3,8}

下面通过图片，更加直观的了解冒泡排序的实现过程：在这里插入图片描述

2.1.2 边界值的确认（1）bound表示界限，sz表示数组中的个数，将未排序区间和已排序区域的区间分为[0,sz-bound)、[sz-bound,sz)。（2）对于+1、-1; //控制区间：使得在每一次循环结束后，未排序区域数字-1，已排序区域数字+1 for (int i = 1; i //升序操作 // if (arry[i-1] < arry[i]){ //降序操作 int tmp = arry[i-1]; arry[i-1] = arry[i]; arry[i] = tmp; } } } } int main(){ int arr[] = { 7, 6, 9, 4, 2, 3, 8 }; int size = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, size); for (int n = 0; n

【本文地址】

公司简介

联系我们