https://zhuanlan.zhihu.com/p/53860765
stack overflow
堆栈溢出和快速排序这两个概念对开发人员来说并不陌生，但是通知都只是听说过，真正开发过程中却很少会遇到。我也是敲代码好些行后非常有幸撞上了，而且还是两个一起出现的，这其中过程的滋味还是相当酸爽，值得回味。
问题背景：
某项目中有个POI离线检索功能，比如搜索附近的加油站，底层引擎逻辑提供了一个C函数。
输入：经纬点，搜索范围半径，搜索类别。
输出：按照距离由近到远排好序的POI结果列表。
这是一个C函数，是同步接口，所以我在OC 上层做了一次封装，改成了异步调用，在子线程中执行。
问题现象：
（1）如果搜索加油站，酒店等匹配结果数据较少的类型，功能正常；
（2）如果搜索饭店，酒店这种匹配结果较多的类型时，则会导致程序Crash。Crash时线程堆栈显示crash在搜索子线程，Crash对应的代码行不固定，每次crash时都不一样，略诡异，但是都是Crash在对搜索结果进行快速排序的那个快排函数中；
（3）如果我减少搜索范围的半径，再搜索饭店或者酒店时，功能又正常了。
问题分析：
（1）只有检索结果列表中元素比较多的时候才出现问题，元素较少时功能正常；
（2）快速排序函数是非常标准的实现，而且大多数类别的搜索都是正常的，所以应该可以排除嫌疑。但是Crash线程调用堆栈却显示挂在了快速排序函数里面。说明函数的执行环境有问题；
快速排序函数代码
（3）该函数是放在子线程中执行的。难道是子线程默认堆栈空间太小，快速排序递归层级过多时因为堆栈溢出导致crash？ 特意查了一些苹果官方文档，
apple堆栈大小说明
iOS系统中子线程默认堆栈大小是512K，果然比较小。
问题解决方案：
（1）直接增大子线程的堆栈大小。我用的是Cocoa的线程NSThread，直接通过setStackSize方法配置线程堆栈大小，需要注意的是配置的stacksize最小值是16k，而且必须是4K的整数倍。需要在线程开始执行之前进行配置（NSThread 对象的start方法调用之前）。
调整堆栈大小
（2）对快速排序做优化。
问题总结：
1、关于堆栈溢出
一般情况下应用程序是不需要考虑堆和栈的大小的，但是事实上堆和栈都不是无上限的，过多的递归会导致栈溢出，过多的alloc变量会导致堆溢出。默认情况下iOS主线程1M，子线程512K。
iOS 应用程序执行时内存布局如下图所示：
内存空间
在应用程序分配的内存空间里面，最低地址位是固定的代码段和数据段，往上是堆，向上生长，用来存放全局变量，对于 ObjC对象 来说，就是 alloc 出来的变量，都会放进这里，堆不够用的时候就会往上申请空间。最顶部高地址位是栈，向下生长，局部的基本类型变量都会放进栈里，函数调用时参数、返回地址等信息都是放在栈里。 ObjC 的对象都是以指针进行操控的，局部变量的指针都在栈里，全局的变量的指针在堆里。
所以预防堆栈溢出的方法：
（1）避免层次过深的递归调用；
（2）不要使用过多的局部变量，控制局部变量的大小；
（3）避免分配占用空间太大的对象，并及时释放;
（4）实在不行，适当的情景下调用系统API修改线程的堆栈大小；
2、关于快速排序的优化
快速排序是数据结构课程中介绍的最基础的一种算法。这里单独拿出来聊这个话题，主要是想强调两个事情，第一，基础真的很重要；第二，基础算法在实际编程中确实可能用到不多，大部分情况下都是直接调用系统的封装好的接口即可，但并不代表不会遇到，并且校招面试中出现几率也是比较大的。
关于快速排序的优化，百度里面一搜能找到很多方法，甚至还有不少人用这个题目来写各种小论文。我这里也简单分享一下我觉得比较容易实现且效果较好的方法。
我们先看看快速排序的标准教科书实现：
快速排序标准实现
改进措施如下：
（1）中枢值的选取。这个很显然，如果每次都选中实际大小中中间的那个值，那么就能达到最优的排序效果，避免最坏的情况的;
（2）划分的最小数列长度。因为快速排序是对子序列不停递归的一个过程（分治法）。所以如果递归的过多，堆栈带来的性能损失也是不容小视的。还有最重要的一点就是在数据量很小的情况下，插入排序在时间上的性能要比快速排序的性能要好，所以当子序列长度小于某阈值时，调整为插入排序；
（3）对是否交换做标记，如果全过程没有发生交换，直接返回就可以了；
（4）栈的深度。要优先对小的数组进行排序，这样可以减少递归调用栈的深度。
改进后的伪代码如下:
快速排序改进