【C语言】二分查找与冒泡排序

​

 二分查找

在有序数组中查找具体的某个数字n，可能有同学会说一个一个找，但是这样的效率实在太低，特别是对于有序的数组，效率太低。我们一般从中间元素开始找，查一次去掉一半数字，这种方法我们给它取名为折半查找即为二分查找，效率大大提高！怎么理解呢？如果有2的32次方个数字，我们最多只需查找32次，而一个一个数运气不好却是2的32次方次。

在计算机科学中， 二分搜索 （英语：binary search），也称 折半搜索 （英语：half-interval search）、 对数搜索 （英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索 算法 。

注意点：关键在于有序数组，也就是说，二分查找存在缺陷：不能在无序数组中使用，当然对于无序数组你也可以选择排一下序。

思路分析

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]（即中间元素）与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

我们可以用int left来记录数组最左边元素的下标，right来记录数组最右边元素的下标，mid来表示中间元素的下标，即mid=（left+right）/2。如果查找的元素小于arr[mid],这说明查找的元素在中间元素的左边，这时候最右边元素right = mid-1,同理，如果查找的元素大于arr[mid]，这说明了查找元素在中间元素的右边，这时候最左边元素left = mid+1.如果出现left>right的情况，这也就说明了数组中并没有存在查找的元素。

代码实现：

​

编辑

​

编辑

冒泡排序

什么是冒泡排序？

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

冒泡排序是最简单的排序方法，理解起来容易。虽然它的计算不是最快的，但它是最基本的，初学者一定要掌握。

冒泡排序的原理是：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

思路分析：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

​

编辑

代码实现：

第一种形参是数组

​

编辑

第二种形式是指针

​

编辑

​

编辑

​