关键词：
1. 二分查找算法
要求
- 能够用自己语言描述二分查找算法
- 能够手写二分查找代码
- 能够解答一些变化后的考法
1.1 二分查找算法介绍
二分查找也是一种在数组中查找数据的算法。它只能查找已经排好序的数据。二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。因此，比较一次就可以把查找范围缩小一半。重复执行该操作就可以找到目标数据，或得出目标数据不存在的结论。
现在我们来试试查找6这个元素。
首先找到数组中间的数字，此处为5。
将5和要查找的数字6进行比较。
把不需要的数字移出查找范围。
在剩下的数组中找到中间的数字，此处为7。
比较7和6。
把不需要的数字移出查找范围。
在剩下的数组中找到中间的数字，此处为6。
6=6，成功找到目标数字。
1.2 二分查找说明
1.3 算法描述
-
前提：有已排序数组 array（假设已经做好）
-
定义左边界 lIndex、右边界 rIndex，确定搜索范围，循环执行二分查找（3、4两步）
-
获取中间索引 mIndex = Floor((lIndex+rIndex) /2)
-
中间索引的值 array[mIndex] 与待搜索的值 target 进行比较
① array[mIndex] == target 表示找到，返回中间索引
②array[mIndex] > target，中间值右侧的其它元素都大于 target，无需比较，中间索引左边去找，mIndex - 1 设置为右边界，重新查找
③ array[mIndex] < target，中间值左侧的其它元素都小于 target，无需比较，中间索引右边去找， mIndex + 1 设置为左边界，重新查找
-
当 lIndex > rIndex 时，表示没有找到，应结束循环
1.4 算法实现
/**
* 二分查找算法
*
* @param array 待查找的数据
* @param target 目标元素
* @return target在array中的索引值，如果没有匹配的元素则返-1。
*/
public static int binarySearch(int[] array, int target)
int lIndex = 0, rIndex = array.length - 1, mIndex;
while (lIndex <= rIndex)
/*
* 无符号右移动1位，相当于 /2。
* 这样可以防止lIndex + rIndex溢出整数最大值。
* 因为移位运算符是接近于计算机硬件的，所以相比于 / 效率也会有所提高。
*/
mIndex = (lIndex + rIndex) >>> 1;
if (target == array[mIndex])
return mIndex;
else if (target < array[mIndex])
rIndex = mIndex - 1;
else
lIndex = mIndex + 1;
// 如果没有匹配的元素则返-1
return -1;
测试代码：
public static void main(String[] args)
int[] array = 1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50;
int target = 8;
int idx = binarySearch(array, target);
System.out.println(idx);
运行结果：
1.5 相关面试题
1.6 二分查找小结
2. 冒泡排序（稳定）
要求
- 能够用自己语言描述冒泡排序算法
- 能够手写冒泡排序代码
- 了解一些冒泡排序的优化手段
2.1 冒泡排序介绍
在序列的最右边放置一个天平，比较天平两边的数字。如果右边的数字较小，就交换这两个数字的位置。
由于6＜7，所以交换这两个数字。
完成后，天平往左移动一个位置，比较两个数字的大小。此处4＜6，所以无须交换。
继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。
不断对数字进行交换，天平最终到达了最左边。通过这一系列操作，序列中最小的数字就会移动到最左边。
最左边的数字已经归位。
将天平移回最右边，然后重复之前的操作，直到天平到达左边第2个位置为止。
当天平到达左边第2个位置时，序列中第2小的数字也就到达了指定位置。
将天平再次移回最右边，重复同样的操作直到所有数字都归位为止。
排序中……
排序中……
排序完成。
2.2 冒泡排序说明
2.3 算法描述
- 依次比较数组中相邻两个元素大小，若 array[j] > array[j+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后。
- 重复以上步骤，直到整个数组有序。
2.4 算法实现
/**
* 冒泡排序
*
* @param array 待排序的数组
*/
public static void bubbleSort(int[] array)
int n = array.length - 1;
while (true)
int last = 0; // 表示最后一次交换索引位置
for (int i = 0; i < n; i++)
// 如果 array[i] > array[i + 1] 则交换这2个元素的位置 目的是把较大的元素冒泡到后面
if (array[i] > array[i + 1])
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
last = i;
// last 则位最近一次冒泡最后交换位置的起始索引i，因为i后面都是排好序的 所以不需要排序
n = last;
// 如果上一次没有发生交换，则数组已经排好顺序，可以退出外层循环了
if (n == 0)
break;
测试代码：
public static void main(String[] args)
int[] array = 1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50;
bubbleSort(array);
System.out.println(Arrays.toString(array));
运行结果：
3. 选择排序（不稳定）
要求
- 能够用自己语言描述选择排序算法
- 能够比较选择排序与冒泡排序
- 理解非稳定排序与稳定排序
3.1 选择排序介绍
选择排序就是重复 从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换 这一操作的算法。在序列中寻找最小值时使用的是线性查找。
对数字1～9进行排序。
使用线性查找在数据中寻找最小值，于是我们找到了最小值1（线性查找的详细说明在3-1节）。
将最小值1与序列最左边的6进行交换，最小值1归位。不过，如果最小值已经在最左端，就不需要任何操作。
在余下的数据中继续寻找最小值。这次我们找到了最小值2。
将数字2与左边第2个数字6进行交换，最小值2归位。
重复同样的操作直到所有数字都归位为止。
排序完成。
3.2 选择排序说明
3.3 选择排序算法描述
-
将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集
-
重复以上步骤，直到整个数组有序
3.4 选择排序代码实现
/**
* 选择排序算法实现
*
* @param array 待排序数组
*/
public static void selection(int[] array)
// 选择排序需要排序 n - 1 轮
for (int i = 0; i < array.length - 1; i++)
/*
* i 代表每轮选择最小元素要交换到的目标索引
* m 代表每轮最小元素的索引
*/
int m = i;
for (int j = i + 1; j < array.length; j++)
/*
* j 元素比 元素还要小, 更新 m
*/
if (array[m] > array[j])
m = j;
/*
* 优化点：为减少交换次数，每一轮可以先找最小的索引，在每轮最后再交换元素
*/
if (m != i)
int temp = array[m];
array[m] = array[i];
array[i] = temp;
测试代码：
public static void main(String[] args)
int[] array = 1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50;
selection(array);
System.out.println(Arrays.toString(array));
3.5 选择排序与冒泡排序比较
- 二者平均时间复杂度都是 O ( n 2 ) O(n^2) O(n2)。
- 选择排序一般要快于冒泡，因为其交换次数少。
- 但如果集合有序度高，冒泡优于选择。
- 冒泡属于稳定排序算法，而选择属于不稳定排序。
- 稳定排序指，按对象中不同字段进行多次排序，不会打乱同值元素的顺序。
- 不稳定排序则反之。
4. 插入排序（稳定）
要求
- 能够用自己语言描述插入排序算法
- 能够比较插入排序与选择排序
4.1 插入排序介绍
插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。
此处对数字1～9进行排序。
首先，我们假设最左边的数字5已经完成排序，所以此时只有5是已归位的数字。
接下来，从待排数字（未排序区域）中取出最左边的数字3，将它与左边已归位的数字进行比较。若左边的数字更大，就交换这两个数字。重复该操作，直到左边已归位的数字比取出的数字更小，或者取出的数字已经被移到整个序列的最左边为止。
由于5＞3，所以交换这两个数字。
对数字3的操作到此结束。此时3和5已归位，还剩下右边7个数字尚未排序。
接下来是第3轮。和前面一样，取出未排序区域中最左边的数字4，将它与左边的数字5进行比较。
由于5＞4，所以交换这两个数字。交换后再把4和左边的3进行比较，发现3＜4，因为出现了比自己小的数字，所以操作结束。
于是4也归位了。此时3、4、5都已归位，已排序区域也得到了扩大。
遇到左边的数字都比自己小的情况时……
不需要任何操作即可完成排序。
重复上述操作，直到所有数字都归位。
对所有数字的操作都结束时，排序也就完成了。
4.2 插入排序说明
4.3 插入排序算法描述
-
将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需保证顺序）。
-
重复以上步骤，直到整个数组有序。
4.4 插入排序代码实现
/**
* 插入排序代码实现
*
* @param a 待排序的数组
*/
public static void insertSort(int[] a)
// i 代表待插入元素的索引
for (int i = 1; i < a.length; i++)
// temp 代表待插入的元素值
int temp = a[i];
int j = i;
while (j >= 1)
// a[j-1] 是a[i]上一个元素索引，如果 > temp，后移
if (temp < a[j - 1])
a[j] = a[j - 1];
j--;
else
// 如果 a[j-1] 已经 <= t, 则 j 就是插入位置
break;
a[j] = temp;
测试代码：
public static void main(String[] args)
int[] array = 1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50;
insertSort(array);
System.out.println(Arrays.toString(array));
运行结果：
4.5 插入排序与选择排序比较
- 二者平均时间复杂度都是 O ( n 2 ) O(n^2) O(n2)
- 大部分情况下，插入都略优于选择
- 插入属于稳定排序算法，而选择属于不稳定排序
提示
插入排序通常被同学们所轻视，其实它的地位非常重要。小数据量排序，都会优先选择插入排序
5. 希尔排序（插入排序的改进算法）
要求
- 能够用自己语言描述希尔排序算法
5.1 算法描述
-
首先选取一个间隙序列，如 (n/2，n/4 … 1)，n 为数组长度
-
每一轮将间隙相等的元素视为一组，对组内元素进行插入排序，目的有二
① 少量元素插入排序速度很快
② 让组内值较大的元素更快地移动到后方
-
当间隙逐渐减少，直至为 1 时，即可完成排序
5.2 代码实现
private static void shell(int[] a)
int n = a.length;
for (int gap = n / 2; gap > 0; gap /= 2)
// i 代表待插入元素的索引
for (int i = gap; i < n; i++)
int t = a[i]; // 代表待插入的元素值
int j = i;
while (j >= gap)
// 每次与上一个间隙为 gap 的元素进行插入排序
if (t < a[j - gap]) // j-gap 是上一个元素索引，如果 > t，后移
a[j] = a[j - gap];
j -= gap;
else // 如果 j-1 已经 <= t, 则 j 就是插入位置
break;
a[j] = t;
System.out.println(Arrays.toString(a) + " gap:" + gap);
6. 快速排序
要求
- 能够用自己语言描述快速排序算法
- 掌握手写单边循环、双边循环代码之一
- 能够说明快排特点
- 了解洛穆托与霍尔两种分区方案的性能比较
6.1 快速排序介绍
快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。
[比基准值小的数] 基准值 [比基准值大的数]
接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序。
下面我们就来看看快速排序的步骤。
在序列中随机选择一个基准值。这里选择了4。
将其他数字和基准值进行比较。小于基准值的往左移，大于基准值的往右移。
首先，比较3和基准值4。
因为3＜4，所以将3往左移。
接下来，比较5和基准值4。
因为5＞4，所以将5往右移。
对其他数字也进行同样的操作，最终结果如上图所示。
把基准值4插入序列。这样，4左边就是比它小的数字，右边就是比它大的数字。
分别对左边和右边的数据进行排序后，就能完成整体的排序。
随机选择一个基准值。这次选择6。
把其余数据分别和基准值6进行比较，小于基准值的就往左移，大于的就往右移。
完成了大小比较和位置移动。
和前面一样，对左右两边分别进行排序，进而完成整体排序。但是此时左边只有5，所以已经是排序完成的状态，不需要任何操作。而右边就和前面一样，先选出基准值。
选择8作为基准值。
将9和7分别与基准值8进行比较后，两个数字的位置便分好了。8的两边都只有一个数据，因此不需要任何操作。这样7、8、9便完成排序了。
回到上一行，由于7、8、9完成了排序，所以5、6、7、8、9也完成了排序。
于是，最初选择的基准值4的右边排序完毕。
左边也以相同的操作进行排序，整体的排序工作也就完成了。
6.2 快速排序说明
6.3 算法描述
- 每一轮排序选择一个基准点（pivot）进行分区
- 让小于基准点的元素的进入一个分区，大于基准点的元素的进入另一个分区
- 当分区完成时，基准点元素的位置就是其最终位置
- 在子分区内重复以上过程，直至子分区元素个数少于等于 1，这体现的是分而治之的思想 （divide-and-conquer）
- 从以上描述可以看出，一个关键在于分区算法，常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案
6.4 快速排序代码实现
单边循环快排（lomuto 洛穆托分区方案）
-
选择最右元素作为基准点元素
-
j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
-
i 指针维护小于基准点元素的边界，也是每次交换的目标索引
-
最后基准点与 i 交换，i 即为分区位置
public static void quick(int[] a, int l, int h)
if (l >= h)
return;
int p = partition(a, l, h); // p 索引值
quick(a, l, p - 1); // 左边分区的范围确定
quick(a, p + 1, h); // 左边分区的范围确定
private static int partition(int[] a, int l, int h)
int pv = a[h]; // 基准点元素
int i = l;
for (int j = l; j < h; j++)
if (a[j] < pv)
if (i != j)
swap(a, i, j);
i++;
if (i != h)
swap(a, h, i);
System.out.println(Arrays.toString(a) + " i=" + i);
// 返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界
return i;
双边循环快排（不完全等价于 hoare 霍尔分区方案）
- 选择最左元素作为基准点元素
- j 指针负责从右向左找比基准点小的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交
- 最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置
要点
-
基准点在左边，并且要先 j 后 i
-
while( i < j && a[j] > pv ) j-- -
while ( i< j && a[i] <=pv ) i++
private static void quick(int[] a, int l, int h)
if (l >= h)
return;
int p = partition(a, l, h);
quick(a, l, p - 1);
quick(a, p + 1, h);
private static int partition(int查看详情
笔试算法题:冒泡排序(bubblesort),二分查找,二叉树三种遍历(代码片段)
https://img.136.la/20210614/6f4c925813974a33a92fc2f0fdea0310.jpg冒泡排序:基本思想:冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。直观表达，每一趟遍历... 查看详情
java八股文面试题(重点)
Java面试题大全（2020版）JAVA面试八股文Java八股文2021互联网大厂面试问题集合《剑指offer》Java版全系列题解（2021版，持续更新！）2020最新-精选基础算法100题（面试必备）Java基础知识面试题（202... 查看详情
java八股文面试题(重点)
Java面试题大全（2020版）JAVA面试八股文Java八股文2021互联网大厂面试问题集合《剑指offer》Java版全系列题解（2021版，持续更新！）2020最新-精选基础算法100题（面试必备）Java基础知识面试题（202... 查看详情
⭐算法入门⭐《二分枚举》中等02——leetcode面试题10.09.排序矩阵查找(代码片段)
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述 给定m×nm\\timesnm×n矩阵，每一行、每一列都按升序排列，... 查看详情
14java常用类（stringbuffer）排序算法（冒泡排序选择排序插入排序快速排序）查找算法（二分查找）
统计大串中小串出现的次数（新的解决方案）classMyTest{publicstaticvoidmain(String[]args){Stringsource="woyaoxuejava,xihuanjava,aijava,javajavawozuiai";Stringtarget="java";intlength=source.length();Strin 查看详情
java基础冒泡选择排序二分查找
冒泡排序的思路就是前一个和后一个进行比较，如果大的就交换位置 大的数字后浮 如 12 8 5 31第一轮 8 5 12 31第二轮 5 8 12 31........代码如下 package 查看详情
面试之基础算法题：求一个数字在给定的已排序数组中出现的起始终止索引号（java版）
题目给定一个升序的整数数组，查找某一个值在数组中出现的索引号，例如，输入数组[2,3,3,4,4,5]；查找的数是3，则返回[1,2]。时间复杂度要求为O(logN)。思路基本上大致思考一番，就知道可以用二分查找法求... 查看详情
java冒泡排序和二分查找（预习）
经查阅，将资料整理如下：一、冒泡排序1、算法简介它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完... 查看详情
滴滴2019年php高级研发工程师面试题总结
滴滴2019年php高级研发工程师面试题总结一算法基本排序算法要会写,时间复杂度要会推算,主要是冒泡排序,快速排序,选择排序.查找算法,要会写二分查找法,实际场景要会应用.实例算法思路要明白,基本算法看多了,我觉得是几种思... 查看详情
数据结构和算法-面试题(代码片段)
##########################################"""数据结构：1，用Python代码简单实现一个栈。实现pop/push及max方法，要求能在O(1)时间内取得最大值。排序算法：写个快速排序热热身，分析一下复杂度，如果不使用额外的空间，应该怎么写？快... 查看详情
排序算法（冒泡，选择，插入，快速）查找算法（二分，快速）
四种排序算法1.冒泡排序 思路分析：从前往后相邻的两个数一次进行比较,大的往下沉,小的网上冒。当相邻的两个数的比较后发现他们的排序与排序要求相反,就互换。 ... 查看详情
❤️互联网大厂面试高频算法题汇总❤️——❤️二分专场❤️(代码片段)
文章目录1、前言2、题目汇总3、二分模板4、二分流程5、二分高频题详解5.1、LeetCode33.搜索旋转排序数组5.2、LeetCode704.二分查找5.3、LeetCode69.x的平方根5.4、LeetCode4.寻找两个正序数组的中位数5.5、LeetCode153.寻找旋转排序数组中的最... 查看详情
算法基础（面试）(代码片段)
...多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序，并且经常有面试官... 查看详情
二分查找专题总结-基础篇(代码片段)
...是一个常考的知识点。同时，它也是非常容易出错的一道面试题。左右指针的位置，取值，比较是大于还是大于等于。里面细节很多。死记硬背往往容易出错，只有真正理解思路和多多练习，才能掌握不出错的”二分算法“。本... 查看详情
java面试题常见算法总结(代码片段)
常见算法1、7种常见排序算法1.1、冒泡排序1.2、简单选择排序1.3、直接插入排序1.4、希尔排序1.5、归并排序1.6、快速排序1.7、堆排序1、7种常见排序算法7种常见排序算法的时间复杂度、辅助空间以及稳定性对照表。排序算法平均... 查看详情
面了50次阿里，把50篇面试经历都搞下来了，长记性了
...也能替你查漏补缺，毕竟现在这么卷，该掌握的八股文还是得掌握。面试无非就是考察计算机基础+算法+语言特性+项目 查看详情
面了50次阿里，把50篇面试经历都搞下来了，长记性了
...也能替你查漏补缺，毕竟现在这么卷，该掌握的八股文还是得掌握。面试无非就是考察计算机基础+算法+语言特性+项目 查看详情