type
status
date
slug
summary
tags
category
icon
password
如何解决快速排序的栈溢出问题
快速排序是一种时间复杂度较低的排序方式，传统的快速排序多采用递归方式，然而这种方式会产生问题，例如在递归过深而堆栈过小时会导致溢出，另一方面一些语言不支持递归。
解决方法：
1、限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。 2、通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。
在此介绍第二种方式，采用python实现
在此采用的key值划分方法分别为首元素划分法和三数取中划分法（优化） ## 传统方法 ### 首元素划分：
三数取中划分法：
递归实现：
非递归实现
易知递归的作用是划分子区间，要实现非递归快排，可以使用栈来保存区间。 另一方面，一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。 代码如下：
完整代码：
- 作者:VON
- 链接:https://baisihan.asia/article/eba3addd-52cf-4538-90ce-85ed41b0eeb0
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。