快速排序导致栈溢出的问题
javascript 中使用快速排序时，有时会出现调用栈溢出的问题，即超出最大调用栈大小。本文将分析这个问题的常见原因和解决方法。
问题描述
给定数组 arr = [33,77,88,44,55,11,66,99,22,44]，使用以下快速排序函数对其排序：
立即学习“Java免费学习笔记（深入）”；
var quicksort = function(arrtemp) { if(arrtemp.length < 2) { return arrtemp; } var middle = math.floor(arrtemp.length / 2); var midkey = arrtemp[middle]; // 方式 1 // var midkey = arrtemp.splice(middle, 1)[0]; // 方式 2 var left = []; var right = []; for(var i = 0 ; i < arrtemp.length; i ++) { if(arrtemp[i] < midkey) { left.push(arrtemp[i]); }else { right.push(arrtemp[i]); } } return quicksort(left).concat([midkey],quicksort(right))}
当使用方式 1 时，调用 quicksort() 后会产生栈溢出错误，而使用方式 2 则不会。
问题分析
栈溢出是由于函数调用过多导致堆栈空间不足造成的。对于快速排序，当数组长度较大时，以下情况会导致栈溢出：
方式 1 中，获取中间键值未同时从数组中移除，导致 subsequent 比较一直成立，造成无限递归调用。方式 2 中，获取中间键值时同时从数组中移除，将 midkey 独立出来，后续比较不会将它作为比较元素，从而避免无限递归调用。
解决方法
根据以上分析，解决栈溢出问题的方法是：
采用方式 2，在获取中间键值时同时从数组中移除。
建议实现
var middle = Math.floor(arrTemp.length / 2);var midKey = arrTemp.splice(middle, 1)[0];
以上就是JavaScript 快速排序如何避免栈溢出？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1496905.html
微信扫一扫 
支付宝扫一扫 
