详细掌握二分查找、冒泡排序与快速排序（面试必会）

今天药忘吃喽~ 2023-09-27 14:19 2阅读 0赞

**目录**

一、排序相关术语介绍

二、排序算法分类及复杂度总结

三、二分查找

四、冒泡排序

五、快速排序

快速排序之挖坑法

--------------------

## 一、排序相关术语介绍 ##

> 排序：将一串系列数字按照递增或递减顺序进行排列起来
> 
> 稳定性：在排序之前，两个相同的数字A和B，A排在B之前。若实现了排序操作后，A仍排在 B之前，称为稳定性；若实现了排序操作后，A排在B之后，则称为非稳定性。
> 
> 内排序：所有的排序操作都在内存中完成
> 
> 外排序：数据元素太多不能同时在内存中完成，因此在内存和外存中移动数据进行排序

## 二、排序算法分类及复杂度总结 ##

![f7333f2aaca4445694a130d54afae8f7.png][]

<table style="width:500px;"> 
 <tbody> 
 <tr> 
 <td style="width:105px;">排序算法</td> 
 <td style="width:177px;">时间复杂度</td> 
 <td style="width:104px;">空间复杂度</td> 
 <td style="width:113px;">是否稳定排序</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">直接插入排序</td> 
 <td style="width:177px;">O(<img alt="gif.latex?N%5E%7B2%7D" src="https://latex.csdn.net/eq?N%5E%7B2%7D">)</td> 
 <td style="width:104px;">O(1)</td> 
 <td style="width:113px;">稳定排序</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">希尔排序</td> 
 <td style="width:177px;">平均时间复杂度 O(<img alt="gif.latex?N%5E%7B1.3%7D" src="https://latex.csdn.net/eq?N%5E%7B1.3%7D">)</td> 
 <td style="width:104px;">O(1)</td> 
 <td style="width:113px;">不稳定排序</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">选择排序</td> 
 <td style="width:177px;">O(<img alt="gif.latex?N%5E%7B2%7D" src="https://latex.csdn.net/eq?N%5E%7B2%7D">)</td> 
 <td style="width:104px;">O(1)</td> 
 <td style="width:113px;">不稳定排序</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">堆排序</td> 
 <td style="width:177px;">O(<img alt="gif.latex?N*%7Blog_%7B2%7D%7D%5E%7BN%7D" src="https://latex.csdn.net/eq?N*%7Blog_%7B2%7D%7D%5E%7BN%7D">）</td> 
 <td style="width:104px;">O(1)</td> 
 <td style="width:113px;">不稳定排序</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">冒泡排序</td> 
 <td style="width:177px;">O(<img alt="gif.latex?N%5E%7B2%7D" src="https://latex.csdn.net/eq?N%5E%7B2%7D">)</td> 
 <td style="width:104px;">O(1)</td> 
 <td style="width:113px;">稳定排序</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">快速排序</td> 
 <td style="width:177px;">O(<img alt="gif.latex?N*%7Blog_%7B2%7D%7D%5E%7BN%7D" src="https://latex.csdn.net/eq?N*%7Blog_%7B2%7D%7D%5E%7BN%7D">）</td> 
 <td style="width:104px;">O(1)</td> 
 <td style="width:113px;">不稳定排序</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">归并排序</td> 
 <td style="width:177px;">O(<img alt="gif.latex?N*%7Blog_%7B2%7D%7D%5E%7BN%7D" src="https://latex.csdn.net/eq?N*%7Blog_%7B2%7D%7D%5E%7BN%7D">）</td> 
 <td style="width:104px;">O(N)</td> 
 <td style="width:113px;">稳定排序</td> 
 </tr> 
 </tbody> 
</table>

##  ##

## 三、二分查找 ##

二分查找的思路主要是定义数组的**最左下标left**和**最右下标right**及找出数组元素最中间值下标**mid，在进行**比较arr\[mid\] 与 目标值target值

1、首先，对 left 的值和 right 的值进行初始化，然后计算 middle 的值  
 **left = 0,**

**right = arr.length - 1，**

**mid = left + (right - left) / 2**

2、循环条件：while (left <= right)

3、比较arr\[mid\] 与 目标值target值

若arr\[mid\] > target ,说明target值在left和mid之间,则right=mid-1;

若arr\[mid\] < target ,说明target值在right和mid之间,则left=mid+1;

4、详细代码

package look;
 
 public class BinarySearch {
 	public static void main(String[] args) {
 		int[] arr = new int[]{1,2,6,7,9};
 		int i = search(arr, 1, 0, arr.length - 1);//(0 , 4)
 		System.out.print(i);
 	}
 	public static int search(int[] arr, int target, int left, int right) {
 		
 		while(left <= right) {
 			int mid = left+ (right-left) / 2;
 			if(arr[mid] < target) {
 				left = mid + 1;
 			}else if(arr[mid] > target) {
 				right= mid - 1;
 			}else{
 return mid;
 }
 		}
 		return -1;
 	}
 }

--------------------

## 四、冒泡排序 ##

**思路**：给定一组数据，将这组数据从第一个元素开始与第二个元素比较，若第一个元素大于第二个元素，则互换位置，前后两两相互比较，依次从第一个元素比较到最后一个元素。经过这一轮下来可以把这组数据的最大数据排序在最后一个位置上。第二轮也是同样操作，可以把第二大的数据排序在最后第二个位置上。接下来依次进行相同操作，直到这组数据全部排序好。

> 举例给定一组数据：5、3、2、7、8、1
> 
> 第一轮：3、2、5、7、1、8 比较次数：5次
> 
> 第二轮：2、3、5、1、7、8 比较次数：4次
> 
> 第三轮：2、3、1、5、7、8 比较次数：3次
> 
> 第四轮：2、1、3、5、7、8 比较次数：2次
> 
> 第五轮：1、2、3、5、7、8 比较次数：1次
> 
> **总结规律：如果一组数据有n个，则比较轮数用 i 表示，则 i=n-1，比较次数用 j 表示，则 j=n-i**

动态效果图：

![3124c266ac21492a81ca97125b6fdb6b.png][]

![9bcff90703cc48e19036a3389e380329.gif\#pic\_center][9bcff90703cc48e19036a3389e380329.gif_pic_center]

代码如下：

import java.util.Arrays;
 public class BubbleSort {
 public static void main(String[] args){
 int[] array={8,9,1,6,4,0,3};
 Bubble(array);
 System.out.println(Arrays.toString(array));
 }
 
 public static void Bubble(int[] array){
 for (int i = 0; i < array.length-1; i++) { //定义冒泡排序的比较轮数
 for (int j = 0; j < array.length-1-i; j++) { //定义每一轮的比较次数
 if (array[j] > array[j+1]) { // 前后比较，大的元素往后移，互换位置
 int tmp = array[j];
 array[j]=array[j+1];
 array[j+1]=tmp;
 }
 }
 }
 }
 }

##  ##

## 五、快速排序 ##

快速排序的基本思想为： **任取待排序元素序列中的某元** **素作为基准值，按照该元素所在的排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有** **元素均大于基准值，然后最左右子序列重复该过程（使用递归方法），直到所有元素都排列在相应位置上为止**。

### 快速排序之挖坑法 ###

**思路：**

1、先定义最左的和最右的元素分别为 Left 和 Right 。（Left从左往右走，Right从右往左走）

2、选出一个数据（一般是最左边或是最右边的）定义为key元素，从待排序元素序列拿出赋值给key，在该数据位置形成一个坑位。（若在最左边挖坑，则需要Right先走；若在最右边挖坑，则需要Left 先走）

3、当在最左边挖坑时，Right从右往左走时，遇到比key小的值，将该值放入坑位，此时坑位就移到了Right位置处。这时Right停止不动，Left开始从左往右走，当遇到比key大的值，将该值放入坑位，此时坑位就移到了Left位置处 ，这时Left停止不动，Right开始从右往左走，重复上述操作。

4、当Left和Right相遇时，将key元素放入坑位，此时key的左边都是小于key的数，key的右边都是大于key的数

5、将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时（即 **Left ![gif.latex?%5Cgeqslant][gif.latex_5Cgeqslant] Right** 因为正常情况下Left < Right），便停止操作，此时待排序集合已经是有序的。

**动图演示（以最左边元素定义为key值为例演示）**

![20210515183213169.gif\#pic\_center%23pic\_center][20210515183213169.gif_pic_center_23pic_center]

代码如下

import java.util.Arrays;
 
 public class QuickSort {//快速排序的挖坑法
 public static void main(String[] args) {
 int[] array={5,8,9,6,1,4,3,7,2};
 quickSort(array,0, array.length-1);
 System.out.println(Arrays.toString(array));
 }
 public static void quickSort(int[] array,int begin,int end){
 if(begin >= end){ //判断是否排序结束，正常情况是 begin 小于 end
 return;
 }
 int a = partition(array,begin,end);//划分基准值key元素
 quickSort(array,begin,a-1);//递归基准值的左子树排序
 quickSort(array,a+1,end);//递归基准值的右子树排序
 }
 public static int partition(int[] array,int left,int right){
 int key = array[left];//选定最左边元素为基准值key，坑位在left处
 while(left < right){
 
 //坑位在最左边，right先移动，从右往左，寻找小于key的元素值
 while(left < right && array[right] >= key){
 right--;
 }
 array[left] = array[right];//把right值放入坑位，此时坑位在right
 
 //坑位在right处，此时left移动，从左往右，寻找大于key的元素值
 while(left < right && array[left] <= key){
 left++;
 }
 array[right] = array[left];//把left值放入坑位，此时坑位在left
 
 }
 
 // 当left与right相遇时，把基准值key元素放入坑中
 array[left]=key;
 return left;
 }
 }

[f7333f2aaca4445694a130d54afae8f7.png]: https://img-blog.csdnimg.cn/f7333f2aaca4445694a130d54afae8f7.png
[3124c266ac21492a81ca97125b6fdb6b.png]: https://img-blog.csdnimg.cn/3124c266ac21492a81ca97125b6fdb6b.png
[9bcff90703cc48e19036a3389e380329.gif_pic_center]: https://img-blog.csdnimg.cn/9bcff90703cc48e19036a3389e380329.gif#pic_center
[gif.latex_5Cgeqslant]: https://latex.csdn.net/eq?%5Cgeqslant
[20210515183213169.gif_pic_center_23pic_center]: https://img-blog.csdnimg.cn/20210515183213169.gif#pic_center%23pic_center