请问如何改进快速排序将其变为稳定？

网上查了资料没有找到好的方法
全部评论
好像是快排有其他一些版本，你看看啊哈算法上讲快排那个，好像是可以变成稳定的
点赞 回复 分享
发布于 2017-06-08 14:58
如果非要稳定的快排，可以用另外一个和待排序一样长度的辅助数组。对待排序数组两次扫描，第一次从下标0到len把比tmp小的依次从左到右一直放到辅助数组里。然后第二次扫描待排序数组从下标len到0,把大于等于tmp的依次从右到左放到辅助数组里。最后拷贝辅助数组到原数组，这样应该就是稳定的partition了。当然第一次扫描需要记录mid的位置，而且选择比较的tmp也要数组的第一个也就是low下标的数。
5 回复 分享
发布于 2017-06-09 09:41
多开辅助空间可以实现
2 回复 分享
发布于 2017-06-13 12:28
不在乎空间的话，把原数组的元素包装一下，变成（元素，下标）的形式，比较时若元素相等，比较下标，排序完成后拆开就好了
1 回复 分享
发布于 2017-06-09 13:04
不管是不是随机选那个partition，你最后都不可能变成稳定的。面试官估计自己也不知道什么正确答案，唬你一下。
1 回复 分享
发布于 2017-06-08 16:58
不是有个三路快排可以稳定嘛，我记得是海贼王还是维维讲过
点赞 回复 分享
发布于 2021-04-24 13:15
额外记录位置属性.
点赞 回复 分享
发布于 2017-06-13 19:54
可以给元素加个位置属性，然后改变比较方法，你可以去试一下
点赞 回复 分享
发布于 2017-06-13 12:25
答案是：没有可能 。
点赞 回复 分享
发布于 2017-06-08 18:18
不可能的
点赞 回复 分享
发布于 2017-06-08 14:48

相关推荐

04-14 10:26
后端
腾讯内推码腾讯面经
腾讯内推来啦~ 热乎乎的内推码：EUTPZZRV 在腾讯，你将有机会参与具有国际影响力的项目，展示个人风采，获得全球认可。 分享一些面经： 第一轮技术面 闭包作用及实际应用场景 HTTP/1.1、HTTP/2、HTTP/3的核心差异 实现红绿灯控制效果（异步时序逻辑） React Hooks的设计动机与类组件对比 浏览器事件代理原理及实际应用 手写Promise核心逻辑（包含resolve/reject） 数组去重与高频字符统计算法 Web安全防护措施（XSS、CSRF） 浏览器渲染流程与重排/重绘优化 跨域解决方案（JSONP、CORS、代理） 第二轮技术面 低代码平台技术难点与扩展...
腾讯HR面1391人在聊
点赞 评论 收藏
分享
昨天 08:54
湖南大学 数据库工程师
步步高内推 步步高内推码
东莞市步步高实验学校&幼儿园2025春招进行中！ 🤔一、关于我们 东莞市步步高实验学校、步步高实验幼儿园是一所K15私立学校，可容纳幼儿园15个班、小学60个班、初中36个班、高中18个班。我们致力于办一所“助力生命蓬勃发展”的学校，培养具有幸福能力的人。 🙋二、招聘对象 （1）2025届毕业生，即毕业时间为2024年8月-2025年7月； （2）社招骨干教师同步进行，即24届及以前 🏠三、工作地点：东莞长安 🫡四、招聘岗位/学科： 初中部：语文、数学、英语、物理、化学、历史、地理、道法、体育、音乐、信息技术 小学部：语文、数学、英语、音乐、舞蹈、体育、美术、科学、教育戏剧 幼...
小天才公司福利 426人发布
点赞 评论 收藏
分享
02-24 14:18
北京邮电大学 Java
26界，开始准备大厂实习，之前有一段不知名小厂实习，求指教
简历还需要完善吗，boss投了一些没有面试机会。另外暑期开始，感觉自己太菜不敢投递
AAA不喝拿铁：校友好，开投就完事了！要准备面试的话更建议刷codetop，hot100有些题并不是面试常考题。另外想看刷题路线的可以看我的帖子，有讲怎么刷leetcode，除此之外可以看看我根据真实面经整理得到的最全（高/中/低频）面试题，加油
点赞 评论 收藏
分享
03-16 22:00
武汉大学 C++
选java这辈子都有了
疯了，都疯了
幸福的小熊猫想要offer：我阿里投的 c++岗，面试官说自己是做 java 的，c++这辈子才有了
点赞 评论 收藏
分享
04-14 14:56
汤臣倍健_人力_HR
汤臣倍健面经—市场管培生
其实最难的不是offer，而是进入了公司，发现累的要死，很多同学进入了工作后，朋友圈就没有更新过了，所以大家在签约的时候一定要打听清楚！ 目前的重点还是先尽量投，尽量拿到！offer就和抢演唱会票一样，抢完第一波之后等回流了，大佬拿着再多意向书，最后也只能签一个，，越厉害的，拿的offer越多，且都是非线性增长的，只要上面的人释放完意向，紧接着链式反应，大家都会有有offer的第一轮 3个人一组 面试官问问题挨个回答1.自我介绍2.简历深挖，对市场策略的内容问的非常细，问了很多候选人是如何理解xx市场的问题3.如果让你在闲鱼卖汤臣的产品，怎么写文案4.最近印象比较深的消费品5.对汤臣倍健的品...
汤臣倍健开奖32人在聊
点赞 评论 收藏
分享
评论
点赞
7
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 笔试 #
2466279次浏览 28306人参与
# 找工作时的取与舍 #
48010次浏览 294人参与
# Keep实习校招 #
29441次浏览 218人参与
# 牛友故事会 #
583827次浏览 12418人参与
# Offer比较，你最看重什么？ #
147221次浏览 969人参与
# 总结:哪家公司面试体验感最差 #
39002次浏览 197人参与
# 你的头发还好吗？一起爆改美发黑科技！ #
73509次浏览 1098人参与
# 地方国企笔面经互助 #
21030次浏览 39人参与
# 视觉/交互/设计招聘信息汇总 #
8337次浏览 564人参与
# 你知道哪些职场黑话？ #
28650次浏览 235人参与
# 招银网络求职进展汇总 #
100521次浏览 643人参与
# 国企vs私企，怎么选？ #
19352次浏览 162人参与
# 风评不好的公司，你会去吗？ #
33019次浏览 168人参与
# 不考虑转正，实习多久合适 #
20763次浏览 105人参与
# 现在还是0offer，延毕还是备考 #
973435次浏览 7401人参与
# 降低公积金和取消房补怎么选 #
13757次浏览 64人参与
# 软开人，说说你的烦心事 #
39938次浏览 269人参与
# 实习进度记录 #
91137次浏览 855人参与
# Offer比较，求稳定还是求发展 #
37165次浏览 218人参与
# 求职遇到的搞笑事件 #
100613次浏览 708人参与
# 用表情包形容我的2023 #
8469次浏览 46人参与
牛客网
牛客企业服务