以前学算法的时候用的《啊哈！算法》，关于算法的各类书籍对于新手都很不友好，这本书绝对是新手第一本书。
当然啦，如果你是大佬天才，直接跳过这本书。
下面介绍《啊哈！算法》中关于快排的讲解并简单回答 作者 对读者 提出的问题。由于快排用到了递归，这里顺便解释一下栈溢出的问题。
快速排序
介绍快速排序
快排——分治的递归算法。
先来看看《数据结构与算法分析》对快排步骤的解释：
1、说明特殊情况，在代码里体现了递归的出口。
2、在S这组数据中随便找一个数作为基准(pivot)
3、将S这组数据中除开基准数的其他数据分成两份，一份数据全小于基准数，一份数据全大于基准数。
4、递归上面的步骤。
具体步骤
对于一组数据，视为一个区域，在此区域随便找一个数作为 基准数A（不过就是一个参照数而已），将这片区域中小于基准数A的放左边，大于 基准数A 的放右边。
（上面这一步姑且称为基准数归位）
以 基准数A 为界，划分左右两片区域，分别再找基准数B、C，重复上面的动作，将基准数B、C归位。直到分不出左右两片区域。
第一步 统一取最左边数为基准数，同时在最左边和最右边派出两个哨兵，相向而行。 一定要是右哨兵先动
图取自—-《啊哈！算法》
第二步 右哨兵负责找到小于基准数的位置，左哨兵负责找到大于基准数的位置，交换！
第三步 重复第二步直到两哨兵相遇，交换基准数和哨兵脚下数的位置。此时完成了基准数归位
第四步 以归位后的基准数为界，对左右两片区域分别找基准数，分别设置左右哨兵重复执行基准数归位。
Java代码
1 public static void quickSort(int[] arr, int left, int right){
2 if (left >= right) {
3 return; //递归的出口---无法再分出左右两片区域
4 }
5 int i = left; //定义本区域左哨兵
6 int j = right; //定义本区域右哨兵
7 int temp = arr[left]; //设本片区域最左边的数为基准数
8 int swap; //用于交换数的中间数
9 while (i!=j){ //循环直到本区域左右哨兵相遇
10 while (i=temp){ //一定要右哨兵先动，找到小于基准数的位置停下
11 j--;
12 }
13 while (i//左哨兵动，找到大于基准数的地方停下
14 i++;
15 }
16 if (i < j){ //交换左右哨兵脚下的数
17 swap = arr[i];
18 arr[i] = arr[j];
19 arr[j] = swap;
20 }
21 }
22 //退出循环，本区域的左右哨兵相遇了
23 arr[left] = arr[i];
24 arr[i] = temp; //交换基准与哨兵脚下的数，基准数归位
25 quickSort2(arr, left, i-1); //划分左区域，递归
26 quickSort2(arr, j+1, right); //划分右区域，递归
27 }
28 }
作者提出的问题
为什么定义最左边的数为基准一定要右哨兵先动。
取极限情况
右哨兵先动可以保证两哨兵相遇时，脚下数小于基准数。
栈溢出
概述
在递归中，一定要往出口靠近，不然就会出现栈溢出的问题。
这里的栈是什么
可以理解为有一个栈，里面是放方法的，方法一直递归，栈就溢出了
从虚拟机（HotSpot）角度来看：
虚拟机是软件层面的
.java文件编译为.class文件后，开始了虚拟机之旅，首先是类加载、链接、初始化，然后就进入了运行时数据区（每个虚拟机实例一份），
一个Java程序就是一个进程，一个进程对应一个虚拟机实例。
————《深入理解Java虚拟机》第三版
在运行时数据区中有虚拟机栈（每个线程一份），栈由栈帧组成，一个栈帧对应着一个方法，方法不断进栈，栈就溢出了
虚拟机栈先进后出，没有gc，栈顶的方法称为当前方法，当前方法执行完，出栈，才能执行下一个方法。
具体的栈帧结构、方法调用本质不展开说，学习JVM一定要看看《深入理解Java虚拟机》哪怕看不懂也没关系。
Original: https://www.cnblogs.com/tyt0o0/p/16746657.html
Author: 长寿奉孝
Title: 快速排序和栈溢出
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587433/
转载文章受原作者版权保护。转载请注明原作者出处！