请问如何改进快速排序将其变为稳定？
网上查了资料没有找到好的方法
2017-06-08 14:30 已编辑 Université Catholique de Lille C++
关注
全部评论
舍甫琴科
中华女子学院 Java
好像是快排有其他一些版本，你看看啊哈算法上讲快排那个，好像是可以变成稳定的
sillyeye
西南石油大学 Java
如果非要稳定的快排，可以用另外一个和待排序一样长度的辅助数组。对待排序数组两次扫描，第一次从下标0到len把比tmp小的依次从左到右一直放到辅助数组里。然后第二次扫描待排序数组从下标len到0,把大于等于tmp的依次从右到左放到辅助数组里。最后拷贝辅助数组到原数组，这样应该就是稳定的partition了。当然第一次扫描需要记录mid的位置，而且选择比较的tmp也要数组的第一个也就是low下标的数。
送快递的小谍
杭州电子科技大学 Java
多开辅助空间可以实现
未填写 Java
不在乎空间的话，把原数组的元素包装一下，变成（元素，下标）的形式，比较时若元素相等，比较下标，排序完成后拆开就好了
hell0Arys
University College Dublin Java
不管是不是随机选那个partition，你最后都不可能变成稳定的。面试官估计自己也不知道什么正确答案，唬你一下。
一条小团团(Ovo)
门头沟学院 Java
不是有个三路快排可以稳定嘛，我记得是海贼王还是维维讲过
卡卡Lucas
中国人民大学 Java
额外记录位置属性.
黎明R
Java
可以给元素加个位置属性，然后改变比较方法，你可以去试一下
jogging
滴滴_研发
答案是：没有可能 。
hell0Arys
University College Dublin Java
不可能的
相关推荐
查看9道真题和解析