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

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

相关推荐

评论
点赞
7
分享

创作者周榜

更多
牛客网
牛客企业服务