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

网上查了资料没有找到好的方法
全部评论
好像是快排有其他一些版本，你看看啊哈算法上讲快排那个，好像是可以变成稳定的
点赞 回复 分享
发布于 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-15 18:12
门头沟学院 Java
杭州观妙科技-java岗面经
技术面自我介绍一下。你做过的哪个项目最能体现你的能力。简单介绍一下这个项目。哪个模块最能体现你的能力？点赞系统中说“通过 Lua 脚本保证原子性”，保证的什么原子性？点赞并发处理能力提升了 5 倍，是基于原本什么方案提升了 5 倍？5 倍是怎么测出来的？说一下你的排行榜功能是怎么设计的，这个数据量有必要分表么？XXL-JOB 分片任务干了什么？在这个过程中有异常情况吗？你觉得你哪个方向比较突出？你在上一份工作中的收获是什么？如果不用 Redis 缓存，让你自己实现一个有 TTL 的 K-V 缓存，只能用 Java API，你会怎么设计？你会如设计测试用例来测试这个组件？你平常生活的时间安排是这...
点赞 评论 收藏
分享
头像 会员标识
04-14 13:43
哈尔滨工程大学 C++
26年社招测开面试记录
1、📍面试公司：波克城市一面🕐面试时间：20260408💻面试岗位：测试开发工程师❓面试问题（记忆较为深刻的问题）：1、埋点框架调优的内容2、商业化SDK交由其他业务使用，如果业务反馈埋点量级大幅下降要如何排查3、Kafka数据流4、算法题：最长回文子串，解决方法找到回文中心字符（奇数、偶数两种情况），向外寻找可能的最长子串🙌面试感想：个人算法能力太差 hot100再刷刷HR面🕐面试时间：20260414❓面试问题（记忆较为深刻的问题）：1、两年内主要负责的业务，为什么考虑换工作2、个人更看重什么，为什么当下觉得发展受限3、反问2、📍面试公司：小熊博望 倍孜一面：🕐面试时间：20...
查看20道真题和解析
点赞 评论 收藏
分享
03-19 10:57
已编辑
百度_Java后端开发(实习员工)
点赞 评论 收藏
分享
04-15 21:48
已编辑
郑州轻工业大学 Web前端
点赞 评论 收藏
分享
今天 14:33
门头沟学院 Java
实习时最怕听到的一句话，听完头皮发麻
我听学长说他最害怕的就是前辈突然开口，尤其是那句“有空吗？”，每次听到都头皮发麻，神经紧绷。真的，这句话绝对是实习噩梦top1，没有之一！只要前辈一开口说“有空吗？”，大概率没好事，要么是临时加活，要么是之前做的东西出问题了，要么就是去做完全没接触过的任务，根本不知道该怎么下手。学长说他之前实习的时候，刚摸鱼刷了两分钟手机，前辈就走到工位旁，轻轻说“有空吗？”，给他吓一跳，硬着头皮说“有空有空”，结果就是让他改一份紧急报表，还得半小时内交，手忙脚乱半天，差点出错。后面导致他现在只要听到这句话，条件反射就紧张，哪怕是前辈只是想让他帮忙递个东西，他都得先慌一下。有时候甚至会故意装作忙，就怕被喊到
实习时最怕听到的一句话
点赞 评论 收藏
分享
评论
点赞
7
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我的求职进度条 #
1232851次浏览 9118人参与
# 第一份工作应该选择高薪还是大平台 #
220692次浏览 1042人参与
# 华泰星战营，提前锁定校招offer #
4618次浏览 279人参与
# 你简历上最心虚的一句话 #
2008次浏览 19人参与
# 考公VS就业，你怎么选？ #
100008次浏览 523人参与
# 哪些公司对双非友好 #
230089次浏览 1236人参与
# 卷__卷不过你们，只能卷__了 #
59954次浏览 756人参与
# 校招第一份工作你干了多久？ #
150201次浏览 631人参与
# 商战，最累的是我们 #
31672次浏览 99人参与
# 小红书求职进展汇总 #
238521次浏览 1397人参与
# 找工作的破防时刻 #
289586次浏览 2065人参与
# 面试线索爆料 #
127271次浏览 699人参与
# 春节前，你还在投简历吗？ #
43074次浏览 351人参与
# 大疆求职进展汇总 #
699860次浏览 4351人参与
# 字节7000实习来了，你投了吗？ #
44266次浏览 348人参与
# AI时代还有必要刷leetcode吗？ #
50677次浏览 587人参与
# 工作中，努力重要还是选择重要？ #
286056次浏览 2587人参与
# 机械求职避坑tips #
100367次浏览 580人参与
# 为了实习逃课值吗？ #
79614次浏览 572人参与
# 国企/银行/研究所公司爆料 #
209306次浏览 920人参与
# 格力求职进展汇总 #
213533次浏览 1276人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务