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

网上查了资料没有找到好的方法
全部评论
好像是快排有其他一些版本，你看看啊哈算法上讲快排那个，好像是可以变成稳定的
点赞 回复 分享
发布于 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

相关推荐

昨天 00:13
南方科技大学 后端工程师
百度日常实习后端二面凉经
得不感叹面试真是很看运气，每个面试官的风格都不一样，这次面试官就不是很好说话，感觉不是很喜欢我，估计是挂了。上来就要手撕sql，这次发挥不佳，主要是被上来就让写sql吓到了，第一次遇到，没有准备好，导致后面问问题的发挥也不是很好，深入问的问题都没答上来1go与Java的线程模型的核心区别2用的什么ai工具开发代码3设计一个数据库系统查一个用户过去三十天的流水：表设计，sql查询，索引设计4外键的作用5这样设计有什么问题，如果有一亿用户，每个用户一亿流水，这么设计好吗，有数据泄露的风险嘛？6有外键还需要join嘛7如果查很多很多条数据很慢怎么办，我撤了一堆分库分表，explain，面试官一句直接...
查看16道真题和解析
点赞 评论 收藏
分享
01-16 09:29
已编辑
厦门大学 驱动开发
入职一年了,才总结出这些潜规则....
职场从来都不存在什么公平，雇主通常都是优势方而雇员是弱势方（行业大神除外），再加上我们国家人口众多，所以很正常的，公司作为雇主在面试应聘者的时候都是趾高气昂、高高在上（面试过n家公司的在一旁泣血控诉）。  人有三六九等，公司也有三六九等，而面试官也有，有不少渣渣公司在面试求职者的时候，往往瞅准了求职者急于找到工作的心理，用各种手段把求职者耍的团团转，最后求职者还得对他们说一句：谢谢！  下面是几种求职者经常会遇到的坑:  第一种：打着招人的幌子实际上是为了解决公司项目上遇到的技术难题 在我们求职过程中，有的公司动机不纯，通过各种理由欺瞒，将求职者在面试时的经验成果据为己有。最常见的就是以笔试为...
点赞 评论 收藏
分享
01-12 17:45
门头沟学院 Java
这hr给我气笑了
这就是不想好好聊呗
叁六玖：这样的应该钱不多，以前我也被问，我在问他们实习公工资多少，一般都是2200-2800
找实习记录
点赞 评论 收藏
分享
2025-12-25 16:58
门头沟学院 Java
点赞 评论 收藏
分享
01-12 16:48
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
7
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 为了入行xx岗，我学了__ #
7606次浏览 117人参与
# 26届校招投递进展 #
586690次浏览 3776人参与
# 简历第一个项目做什么 #
8691次浏览 126人参与
# 被说“做题家”，你的反应是_____？ #
3332次浏览 106人参与
# 参加哪些竞赛对找工作有帮助？ #
9780次浏览 151人参与
# 你都见过什么样的草台班子？ #
11135次浏览 87人参与
# Prompt分享 #
3689次浏览 99人参与
# 找实习记录 #
42246次浏览 601人参与
# 工作压力大，你会干什么？ #
15738次浏览 337人参与
# 从哪些方向判断这个offer值不值得去？ #
48798次浏览 342人参与
# 找工作前vs找工作后的心路变化 #
37342次浏览 301人参与
# AI让你的思考变深了还是变浅了？ #
6235次浏览 153人参与
# 多益网络求职进展汇总 #
62322次浏览 281人参与
# 如果不上班，你会去做什么 #
8760次浏览 299人参与
# 入职以后才知道的校招谎言 #
117331次浏览 747人参与
# 去年你投递实习了吗？ #
28254次浏览 335人参与
# 大家每天通勤多久？ #
75528次浏览 537人参与
# 今年秋招还有金九银十吗 #
71496次浏览 502人参与
# 邪修省钱套路 #
8760次浏览 270人参与
# 校招入职后的感受 #
466811次浏览 3629人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务