Java进阶|Java进阶学习——数据结构基础（二）数据结构|java|编程语言|算法

Java进阶学习——数据结构基础（二）

0.前言
1.查找
- 1.1.二分法查找
- 1.2.查找思想的运用
2.递归
- 2.1.阶乘
- 2.2.斐波拉契数列
- 2.2.汉诺塔问题
3.排序
- 3.1.冒泡排序
- 3.2.选择排序
- 3.3.插入排序
- 3.4.归并排序
- 3.5.快速排序
4.总结

0.前言数据结构中最重要的基础算法就是查找和排序算法,查找和选择虽然我们经常用,但用到的都是别人封装好的,我们直接调用API就可以了,我们根本就不需要自己手动去实现这些代码.但为啥还需要学呢?就我个人目前阶段的感觉来说,查找和排序虽然简单,但实现方式多种多样,里面蕴含了很多算法的思想,对于初学数据结构的人来说也算是能勉强当做算法的入门,尽管这样,作为一个第二次学习这方面知识的我来说也还是非常难(大二上学的时候没有自己敲过这方面的代码,完全就是一个期末复习时候感觉理解了的状态,仅仅能做题而已),再次学习的时候心得总结如下.
1.查找对于查找来说,说白了找到映射关系,比如我想查找6在一个数组中的下标,那么也就是说我需要找到在这个数组中6和下标(index)之前的映射关系,此时我只需要遍历,然后比对即可.掌握了这种思想,我们继续向下看一些常用的查找算法.
1.1.二分法查找能使用二分法查找的前提是数组是有序的,二分法这是一种很常用的思想,就是通过比对数值,根据中间值的大小舍弃左边或者右边的一部分.这样就能提高效率了.时间复杂度为O(log(N)),相较于直接遍历的O(N)的时间复杂度,算是有一定的提升.
原理很容易理解,我们思考一下代码怎么写.
首先我们需要保存数组(array,假设是升序排列),左边界下标是left,右边界下标是right,中间的下标(index),最中间下标的值为middleValue,用目标值(aim)与array[index]比较,如果大于,就表示可以舍弃左边,因此可以令left=middle+1(之所以+1是因为middle已经确定不是aim的索引了,可以把middle排除掉),以此类推可以得到小于的写法.如果等于的时候直接返回当前的middle.
这样的操作需要循环进行,可以用while循环,循环终止的条件是啥?考虑循环终止的条件,需要考虑两种情况,一种是找到了,一种是没找到,而没找到的情况包含在前面没找到(太小了),在后面没找到(太大了)和在中间没找到。如果找到了，直接返回，因此如果循环结束了还没找到就直接返回-1表示没找到，这个循环的条件应该是能使查找达到最大次数的条件，顺着这个思路我们可以想到，二分法查找的最大次数为log ? 2 n + 1 \log _{2}^{n}+1 log2n?+1，那么我只需要设置一个次数（count）表示即可。接下来的操作就是一个fori循环的事情了。
这样使一个思路，但我感觉不是很好，还需要一步计算，其实我完全把问题复杂化了，我直接判断两个边界是否满足left<=right，这样就很好的满足了我们需要的条件。代码如下：

public static int BinaryFind(int[] array, int aim) { int middle = array.length / 2; int middleValue = https://www.it610.com/article/array[middle]; int left = 0; int right = array.length; while (left <= right) { if (aim < middleValue) { right = middle - 1; } else if (aim> middleValue) { left = middle + 1; } else { return middle; } //重新赋值 middle = (left + right) / 2; middleValue = https://www.it610.com/article/array[middle]; } return -1; }public static void main(String[] args) { int[] array = {2, 3, 22, 75, 80, 90, 100}; int result1 = BinaryFind(array, 2); if (result1 == -1) { System.out.println("22 不存在数组中"); } else { System.out.println("22 存在数组中，索引值是 " + result1); }int result2 = BinaryFind(array, 50); if (result2 == -1) { System.out.println("50 不存在数组中"); } else { System.out.println("50 存在数组中，索引值是 " + result2); } }

在我这个实例中，判断条件需要加上=号，但有的不需要＋号，不同代码结构不一样，具体可以自行分析。上文提到的四种情况都可以满足条件。
1.2.查找思想的运用在开始谈二分查找之前，提到了查找的本质就是查找映射关系。在只需要查询一次数据的时候，我们可以通过遍历一次来找到，但如果我们需要查找的是两个数据，而且使满足一定关系的数据（比如重复，和为某个数，差为某个数等）。以重复为例，假设我需要查找一个数组中的重复数据，那么我需要在找到一个数据之后，对其后的数据进行查找，找到与其相等的数据。以此类推，直到找到重复的数据。时间复杂的为O(N^2)，我们尝试优化一下，我们这样想，明明我遍历一次就可以获得所有的数据，为何还要遍历两次呢？因为需要两次信息的比对，这第二次查找本质上就是找到一个和当前值一样的，我只需要找到就可以。那么我为何不可以把之前查找过的都放到一个hashmap中，将当前需要查询的数值先利用hashmap中根据Key查找Value，如果不能查找到存储到map中，作为Key，value为为任意值，如果能代表之前存储过了，就是重复值。这样做相当于只进行了一次循环就完成了，时间复杂度为O(N)，有人可能会有疑问，难道从map中查询就不需要时间了吗？难道就不需要遍历？我们想一下，在hashmap中我们存储的是key，通过key找到value，时间复杂度为O(1)(此处可以近似理解为key为数组中的index下标，value为数组中的值）。当然hashmap的底层用到了很多比较深奥的数据结构知识，我现在也不会，就不展开讲了，有兴趣可以自行搜索。此处可以近似理解成数组，如果你连为啥数组的通过index找value的时间复杂度为O(1)都不知道的话，建议去翻看我的上一篇文章，数据结构基础（一）。但我们在需要查找的数组中需要通过value查找index，在这种情况下，就只能遍历了。注意区别一个是通过key找到value（O(1)），一个是通过value找到key（O(N)），时间复杂度的区别就在这了。这就是数据结构的魅力。

public static ArrayList repeat(int[] array) { ArrayList result = new ArrayList<>(); Map flags = new HashMap<>(array.length - 1); for (int i = 0; i < array.length; i++) { int value = https://www.it610.com/article/array[i]; if (flags.get(value) != null) { result.add(value); } else { flags.put(value, 1); } } return result; }

代码不长，也很好理解。这里如果有细心的同学发现了，时间复杂度下降了的代价是什么呢？在算法分析的指标中除了一个时间复杂度还有一个是空间复杂度，他们二者往往是不兼容的，提高了一方，往往意味着降低了另一方。在本题中，新建了一个hashmap存储数据，因此空间复杂度上升了。但是在大多数情况下，都是选择牺牲空间复杂度换取时间复杂度的提高。
如果从空间复杂度的角度继续思考优化的方向，可以发现其实hashmap中的value事实是没有用的，完全就是浪费空间，我只需要判断值是不是空即可，具体是啥我不关心。此时我们可以考虑用一个新的数组代替这个hashmap，进行一定的手段对数据的范围进行压缩（不然如果数据中出现1000，我们这个数组的下标就也要有1000，太浪费空间了），之后存储到这个数组中，进行类似的判断操作，这样我们就节省了value的空间，空间复杂度也优化了。
虽然这个方法很好，但只适合少部分的情况，而且还需要对数据的范围压缩，有点得不偿失，另外有时候我们还需要对hashmap中的value的赋值，此时就更不能用上面的方法了。用hashmap理解起来比较容易，还通用，因而我先介绍了hashmap的方法（本质是一样的），这种思想用处很大，比如LeetCode的第一题两数之和就用到了这种思想.有兴趣的可以去挑战一下，如果你掌握了这种思想，我想那道题听过难不倒你。
2.递归在谈排序之前,先学一种递归的的思想。所谓递归就像高中学习数列时，给定的递推公式，比如a(n)=a(n-1)+1。当我想求a(n)的时候,我只需要求出a(n-1)即可,如果求a(n-1),我只需要求出a(n-2)即可.以此类推,直到需要求的数值是已知的时候,此时就再往回带,求出a(n)。递归的整体思想就是这样，有了递归的思想，我们考虑问题就可以简单的考虑，第一步找到递推的公式，第二步找到已知的数值，第三步找到判断条件。而无需考虑复杂的关系和存储的变量。这就是递归的大致思想，理解起来不难，但还是需要实践到代码层面。
2.1.阶乘我们都知道阶乘的公式为 n ! = n ( n ? 1 ) ! n ! =n(n-1)! n!=n(n?1)!，正好满足使用递归的条件，按照上文提到的三步走方法，首先递归公式找到了， f ( n ) = n f ( n ? 1 ) f(n)=nf(n-1) f(n)=nf(n?1)，第二部找到已知的数值， 1 ! = 1 1!=1 1!=1，第三步找到终止的条件，if(n==1)，此时我们完成了三个步，就可以根据这三步写代码了。

public static int factorial(int n) { //当 n = 1 时，递归结束 if (n == 1) { return 1; } //把 factorial(n - 1) 的结果和 n 相乘，剩下的交给 factorial(n - 1) 来解决。 return n * factorial(n - 1); }

这样就实现了阶乘的计算，当然我们不使用递归的形式也能实现，但这只是针对这样的简单问题，如果遇到复杂的，可以考虑只实现当前的逻辑，剩下的交给 f ( n ? 1 ) f(n-1) f(n?1)就行。
2.2.斐波拉契数列斐波那契数列数列的递推表达式为 f [ n ] = f [ n ? 1 ] + f [ n ? 2 ] ( n > = 3 , f [ 1 ] = 1 , f [ 2 ] = 1 ) f[n]=f[n-1]+f[n-2](n>=3,f[1]=1,f[2]=1) f[n]=f[n?1]+f[n?2](n>=3,f[1]=1,f[2]=1)，此时如果使用非递归方法，需要存储两个变量( f ( n ? 1 ) 和 f ( n ? 2 ) f(n-1)和f(n-2) f(n?1)和f(n?2))，并且要更新，代码就变的很复杂，而且容易出错。而如果使用递归的思想就无需考虑存储这两个变量了。三步分析，第一步递归公式已经找到，第二部找到已经的数值， f ( 1 ) = 1 , f ( 2 ) = 1 f(1)=1,f(2)=1 f(1)=1,f(2)=1，第三步找到终止的条件，if(n==1)和if(n==2)。从这个角度思考，代码如下。

public static int fibonacci(int n) { if (n == 1 || n == 2) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); }

这样的写法非常简洁，因为无需存储两个变量，因此代码的非常简单易懂。当然斐波那契数列是有通项表达式的，但公式太复杂，用的不多，有兴趣可以自行查阅。
2.2.汉诺塔问题汉诺塔问题是一个非常经典的递归问题，初学递归的你，前面两个你可能还能勉强应对，这道题大概率能难倒你。
汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

文章图片

这道题目在我学Python的时候整理过一次解题思路，有兴趣的可以看，Python学习之路——列表强化学习这篇博客。
不过这次我有了更深的理解，我们这样考虑，如果我想要将A的64个盘子移动到C上，至少需要把63个盘子移动到B上，因为A最下面的盘子是最大的，这个最大的盘子只能在最下面，因此我如果想把所有的盘子移动到C上，首先需要把最大的盘子挪到C的最下面，而在我把最下面的盘子拿走的时候，A上肯定是一个盘子都没有了，那么此时63个盘子按照顺序在B上，一个最大的盘子在C上，A上为空。不管怎么样，肯定是有这样的一个状态的。我们跳出来看，把64个盘子移动到C上，是不是相当于先把63个盘子移动到B上，再把最大的盘子移动到C上，接着把B的63个盘子移动到C上就完成了任务。而这63个如何移动，我不管我只知道，在移动62个到另一个柱子的时候，我只需要把最大的移动到指定的即可。是不是找到递归的苗头了？或者这样考虑，把63个盘子看成一个整体，如果只有两个盘子，我只需要把上面的移动到B，下面的移动到C，再把B上的移动到即可，剩下的同理。如果还不理解，可以参考别的文章。
理清楚思路之后，我们想一想代码的思路，我们跳出A,B,C三个柱子，把三个柱子一个是作为源柱子（含有需要移动的盘子的柱子，最开始是A），一个作为目标柱子（需要把盘子移动到的柱子，最开始是C），一个作为中转柱子（源和目标之间的桥接，最开始是B）。最开始的移动64个盘子的表达式如果是这样的话，hanoi(int 64, int a, int b, int c)，a,b,c分别表示最开始对应的柱子。把63个盘子移动到B是不是相当于把B作为目标，C作为中转，A还是源？hanoi(int 63, int a, int c, int b)，之后再把A上的盘子移动到C，最后把B上的63个盘子移动到C，hanoi(int 63, int b, int a, int c)，此时你对a,b,c代表的背后含义就明白了吧？至此我们使用三步分析，第一步是递推公式，大概是上文描述的那样，或者参考下面更清晰的流程图。
Created with Rapha?l 2.2.0 hanoi(int n, int a, int b, int c) hanoi(int n-1, int a, int c, int b) 从源移动到目标（a->c） hanoi(int n-1, int b, int a, int c) 结束第二步是确定的值，如果只有一个盘子，需要从A移动到C，只需要把上面的盘子移动到C即可。第三步是判断条件，当只有一个盘子if (n == 1)。至此按照这个思路分析，代码如下。

public static void hanoi(int n, int a, int b, int c) { if (n == 1) { System.out.println(a + "->" + c); } else { //先把n - 1 个盘子从A挪到B（B和C交换位置是因为在n - 1 个时候，B是目的地，C是过渡） hanoi(n - 1, a, c, b); //此时n - 1 个盘子已到达B，我们需要把A上仅存的那一块最大的放到C上 System.out.println(a + "->" + c); //此时的问题变成把n - 1 个盘子在A为过渡的情况下从B到C hanoi(n - 1, b, a, c); } }

【Java进阶|Java进阶学习——数据结构基础（二）】第一次看不懂没关系，很多人第一次都看不懂，先尽量理解，然后尝试着自己用代码实现，仔细思考内在的联系，慢慢就理解了，想要学会递归，汉诺塔问题是必须深刻理解的。
另外如果有能力可以考虑用递归实现二分查找法，也是非常简单，而且实现之后不光对递归，对二分法也会有很深刻的理解。
3.排序有了递归的思想，后续在面对比较难的排序算法的时候就不会吃力了。排序也是我们常用的需求，下文不特别说明，都采用升序的排序方法。
3.1.冒泡排序冒泡排序是最简单的排序算法了，同样可以参考我之前学习python的时候的解题思路Python学习之路——列表强化学习。
冒泡排序的本质通过两次循环，外层控制循环的次数，内层控制比较的次数，遇到左边比右边大的就交换。思路很简单，时间复杂度O(N^2).代码比较简单，也容易理解。

// 冒泡排序 public static void bubbleSort(int[] array) { // 每次循环，都能冒泡出剩余元素中最大的元素，因此需要循环 array.length 次 for (int i = 0; i < array.length; i++) { // 每次遍历，只需要遍历 0 到 array.length - i - 1中元素，因此之后的元素都已经是最大的了 for (int j = 0; j < array.length - i - 1; j++) { // 交换元素 if (array[j] > array[j + 1]) { int temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } } } }

这个算是最基础的排序算法了，好好看看肯定能理解并写出代码的。
3.2.选择排序选择排序的本质是每次都选择数组剩余元素中的最大的元素并放在后面，以此循环往复，最终对数组进行排序。思路也不是很难，还是需要一定的思考即可。

// 选择排序 public static void selectSort(int[] array) { //最大值的下标 int maxIndex; //第一层循环,从数组尾部开始,逐一取值 for (int i = array.length - 1; i >= 0; i--) { maxIndex = i; //选择出最大值的下标 for (int j = 0; j < i; j++) { if (array[j] > array[maxIndex]) { maxIndex = j; } } //交换 swap(array, maxIndex, i); } }

整体也不是很难理解，为了方便控制，第一层循环我采用了从尾部取值的方法，因为是升序排列，从后往前比较方便。
这个算法的时间复杂度也是O(n^2)，但相比于冒泡排序，真正使用的时间还是要短一些，因为选择排序每次外循环只交换一次数组，而冒泡排序排序，需要不停的交换，用时比较久。但如果遇到降序排列的数组，使用选择排序的时间会很长，因为每次都需要重新对maxIndex赋值。
3.3.插入排序插入排序就是寻找需要插入的值的位置，把然后把该元素插入数组中，直至找到每一个元素对应的位置，就完成了排序。
一般是这样实现的，先找到数组中的倒数第二个元素，然后与其后元素比较，如果大于则把其后的这一位元素左移一位，如果小于就把该元素的值赋值给这一位元素的位置。接着从倒数第二个元素开始直至第一个元素。此时因为每个元素的右边的数值都小于该位置的元素，也就完成了排序。
需要考虑一个细节问题，如果在其后遍历到最后一个元素，此时如果最后一个元素还是小于目标元素，就应该直接赋值，而不是进行下一次循环，这需要单独判断。代码如下，相对于前面两种算法，这种明显要困难一些，好好思考一下还是能写出来的。

// 插入排序 public static void insertSort(int[] array) { //需要插入的目标值 int aim; //从倒数第二个开始,遍历n-1次 for (int i = array.length - 2; i >= 0; i--) { //赋值为第i个,第一次赋值为倒数第二个 aim = array[i]; //从选中的值的后面来确定插入的位置 for (int j = i + 1; j < array.length; j++) { //目标值大于当前循环的值,把当前循环的值赋值给前一位 if (array[j] < aim) { array[j - 1] = array[j]; } //目标值小于的时候,把aim赋值给当前值的前一位(与上面判断中的代码不会在同一次内循环中执行) if (array[j] > aim) { array[j - 1] = aim; break; } //特殊情况判断,如果到了数组尾部,直接将aim赋值给当前位置 if (j == array.length - 1) { array[j] = aim; break; } } } }

我们考虑一下时间复杂度，此时时间复杂度就不是一个确定的值了，因为如果数组本身就是升序的，每次都只执行内循环一次，此时时间复杂度为 O ( n ) O(n) O(n)，如果本身是逆序的，此时时间复杂度为 O ( n 2 ) O(n^2) O(n2)，而上面的两种排序的时间复杂度都是O ( n 2 ) O(n^2) O(n2)，因此如果数组本身比较有序的了话，使用插入排序，否则使用选择排序(冒泡排序没有地位)。
3.4.归并排序归并排序是一个典型的空间换时间的例子。先把数组一直拆分到不可拆分，然后将拆分后的数组合并成有序的数组，不断的合并，最终成功排序。因为每次排序的时候两个数组的部分都是有序的，因此排序的时候比较快。这种思路本质是分治思想，把任务分割，之后再把任务合并。每一部分归并排序的结果决定了下一次的归并排序的结果，因此可以使用递归的思想。这样每次排序只需要对两部分已经排好序的数组进行排序，大大简化了思路。
我们分析一下代码如何写，首先先根据递归的三要素，递推公式，终止条件和终止的值。递推公式不方便有公式表达，我觉可以这样理解， f ( n ) l e f t / r i g h t = S O R T ( f ( n ? 1 ) l e f t ∪ ( f ( n ? 1 ) r i g h t ) f(n)_{left/right}=SORT(f(n-1)_{left}\cup(f(n-1)_{right}) f(n)left/right?=SORT(f(n?1)left?∪(f(n?1)right?)，这样虽然不是很严谨，但可以表达意思。终止条件就是，if (array.length == 1)，终止的值是如果一个数组拆分的只有一个元素了，此时排序后的结构还是当前数组，直接返回当前数组。
这是递归的部分，但除了递归这个大的框架，还需考虑两个部分，其一是数组的拆分，其二是左右两个数组的排序。
Java的数组可没有自带数组拆分的方法，因此只能自己实现，为了方便我把它写成了一个方法subArray()，方法内部将参数作为左右下标，前闭后开，对数组遍历赋值给一个新的数组。
最麻烦的就是左右两个数组的排序，因为左右两个数组本身就是比较有序的，因此可以考虑使用类似与插入排序的思想，为什么是类似于呢？因为如果真正使用插入排序，应该是把两个数组简单的合并之后再排序，但这样的话就丧失了一方已经拍好序的优势，得不偿失。我们想一想插入排序的本质就是使一侧的值全部大于或者小于当前值，因此我们可以选择左右两侧数组的第一位值比较，小的作为当前数组的第一位值，之后循环遍历数组的长度次。
当一次赋值之后，被选中的一侧的数组下标应该+1，使得比较该侧部分数组的下一位。
需要考虑的特殊情况是，当有一侧到达边界时，此时后面的赋值应该全部由另一侧来进行。
大致思想如上，代码如下。不理解没关系，对着说明和代码以及注释看。

// 归并排序，返回排好序的数组 public static int[] mergeSort(int[] array) { //递归截止的条件 if (array.length == 1) { return array; } //将数组分成左右两部分 int[] left = subArray(array, 0, (array.length) / 2); int[] right = subArray(array, (array.length) / 2, array.length); //因为右边数组不会比左边的数组的长度长,因此当右边长度等于0的时候直接返回(防止后面报错) if (right.length == 0) { return array; } //递归执行获取排序后的数组 int[] leftSort = mergeSort(left); int[] rightSort = mergeSort(right); //i表示左边数组的下标 int i = 0; //j表示右边数组的下标 int j = 0; //对给定的数组排序 for (int k = 0; k < array.length; k++) { //当左边遍历为之后,可以直接把当前右边部分的值赋值给当前数组的位置 if (i == left.length) { array[k] = rightSort[j]; //j的下标+1 j++; //跳出本次循环 continue; } //同上 if (j == rightSort.length) { array[k] = leftSort[i]; i++; continue; } //如果左边部分比右边的小 if (leftSort[i] < rightSort[j]) { //当前左边位置的值赋值给当前位置 array[k] = leftSort[i]; i++; } else { //相反 array[k] = rightSort[j]; j++; } } //返回排序之后的数组 return array; }// 拷贝原数组的部分内容，从 left 到 right public static int[] subArray(int[] source, int left, int right) { // 创建一个新数组 int[] result = new int[right - left]; // 依次赋值进去 for (int i = left; i < right; i++) { result[i - left] = source[i]; } return result; }

虽然思路简单，但实现起来并不是那么清晰明了。我们分析一下时间复杂度。归并排序，首先合并的时候左右两侧数组都进行了遍历， O ( n ) O(n) O(n)在拆分的时候有点像二分法， O ( l o g 2 n ) O(log_{2}^n) O(log2n?)，因此时间复杂度为， O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))（一般都是这样简写）。分治思想在数据结构中经常运用，因为分治可以大大缩短算法的时间，虽然会增加空间，但问题不大。我之前在学习Java多线程的时候，有一个ForkAndJoin线程池，就是同样使用了分治思想，把一个任务拆分分配给多个线程同时进行。当然归并排序也可以使用这个线程池，但有些杀鸡用牛刀的感觉，该线程池一般用作时间复杂度很高的任务，比如查找素数。有兴趣可以自行查阅。Java进阶学习——Java多线程知识的理解。归并排序算是一个经典的分治思想的运用，这种思想很像人事管理，一个人管不了那么多，我就让多个人管理，以此类推，如果每个人都能管理好自己，做任何事情的效率都会显著提升。
3.5.快速排序快速排序是常用的几种排序方式中速度最快，使用最多并且我个人认为是最复杂的一个。快速排序之所以快是因为它在每次遍历到一个元素的时候，不仅能确定该元素的位置，还能顺便把其余元素放到大致的位置，也就是说在一次循环中做更多的事。分析上面的几种算法，凡是时间复杂度为 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))的都是在一次循环中做了更多的事情，充分利用了之前的元素。
大致思想是这样，从数组的最后一位开始设置为目标值，左边设置一个指针指向第一个值，右边设置一个指针执行倒数第二个值，我们需要把目标值放到数组的合适位置上，这个合适位置的意思就是这个位置的前面的数值都小于目标值，后面的数值都大于目标值。因此我们可以这样做，左指针依次往右侧移动,当遇到大于或者等于目标值的值的时候，则停止，右指针相反，依次往左侧移动，当遇到小于或者等于轴目标值的值的时候，则停止，此时满足满足左指针的值大于目标值，右指针的值小于目标值，因此把交换二者的数值。接着循环上述过程，直至左右指针重合，就把当前两个指针指向的值与目标值互换。此时就满足了目标值前的数据都小于目标值，后面的数据都大于目标值。此时我们再对其以目标值的当前位置为轴，左右分开，再重复从第一步执行。
是不是又看到可递归的影子？还是从递归的角度分析一下问题，这道题目的关键是找到目标值的合适位置，并以位置作为左右分区的依据。如果把 f ( n ) f(n) f(n)的结果作为目标值的合适位置， s o r t ( l e f t , r i g h t ) = s o r t ( l e f t , f ( l e f t , r i g h t ) ? 1 ) ∪ s o r t ( f ( l e f t , r i g h t ) + 1 , r i g h t ) sort(left,right)=sort(left,f(left,right)-1) \cup sort(f(left,right)+1,right) sort(left,right)=sort(left,f(left,right)?1)∪sort(f(left,right)+1,right) 。意思大致是这个意思。
终止条件是数组中只有1或者0个元素了if (left >= right)，终止数值为直接返回。
重点是找到目标值的位置，需要先把目标值和目标值的下标保存，然后保存左右两个指针，然后按照上述规则将目标值与左右两个指针指向的数值比较，并交换。
需要考虑的特殊情况是如果目标值比所有的值都大，需要做特殊处理。
代码如下：

// 快速排序 public static void quickSort(int[] array) { // 调用快速排序的核心，传入left，right quickSortCore(array, 0, array.length - 1); } // 快速排序的核心，同样也是递归函数 public static void quickSortCore(int[] array, int left, int right) { // 递归基准条件，left >= right 即表示数组只有1个或者0个元素。 if (left >= right) { return; } // 根据轴分区 int pivotIndex = partition(array, left, right); // 递归调用左侧和右侧数组分区 quickSortCore(array, left, pivotIndex - 1); quickSortCore(array, pivotIndex + 1, right); } // 对数组进行分区，并返回当前轴所在的位置 public static int partition(int[] array, int left, int right) { //目标值的下标 int initRight = right; //目标值 int aim = array[right]; //右指针-1 right--; //循环找到目标值的正确位置 while (true) { //如果目标值大于左指针的值,而且左指针小于目标值的下标 //之所以是小于目标值的下标而不是右指针的下标,考虑的是如果目标值比所有值大的情况 while (array[left] <= aim && left < initRight) { left++; } //如果目标值小于右指针的下标,而且右指针小于左指针 //如果目标值小于所有值,那么也是可以直接交换,具体你自己分析过就明白了 while (array[right] >= aim && right > left) { right--; } //循环终止条件 if (left >= right) { break; } else { //否则就交换左右指针的值 swap(array, left, right); } } //交换当前左指针指向的值与目标值 swap(array, initRight, left); return left; }

需要特别解释一下为什么会有一个quickSortCore()和quickSort()这两个方法，因为每次递归的时候都需要三个参数，数组，左指针和右指针，当用户调用的时候，左指针和右指针都是确定的(一个是0，一个数数组下标的最大值)，而显然用户是没必要对这两个初始参数赋值的，但后续递归却需要。因此我们采用这种方法，使得用户调用的时候尽可能的方便。
快速排序可能有点困难，需要细心琢磨，认真思考。用好IDE的debug功能(我感觉IDEA的debug功能很好用)，不会现在还有人不会使用IDE的debug功能吧？不会吧？不会吧？
分析一下时间复杂度， O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))，但有一点，如果数组本身就是升序排列的，那么我们每次分区相当于没有分区，这样的话就二分就没了作用，时间复杂度为 O ( n 2 ) O(n^2) O(n2)，当然这是比较少见的情况了。
分析这五种排序方式，一般来说快速排序是最快的，因此也是各个编程语言自带的排序算法中最常用的，也是最经常考的，同时我认为也是最复杂的。想要吃透并不容易。
4.总结这也是我花了很长时间整理的博客。这篇博客整理下来的最大感受是，虽然学习了很多实践技能，但因为基础不牢固的原因，学习的总是浮于表面，也是因为学习了一些实践技能，对于数据结构的表现有了一定的理解，因此现在再学就不会像之前那么困难。可以根据我所学到的技能倒推数据结构的知识理解，这样的学习方式更适合我。
这几个排序和查找算法虽然是非常基础的算法，但包含了不少算法的思想，深入理解之后再遇到别的算法题目就不会那么棘手。因此需要好好理解，至少自己敲一下。