快速排序超时

新手写了一个快排，但是acwing输入十万个相同数的时候会超时，怎么样规避这个超时呢

新手轻喷

不感兴趣

开通SVIP免广告

顶

是不是可以先检查是不是已经有序了。虽然感觉有点可能会导致平常情况变慢

。

先把题目发出来

你知道为什么你那么慢吗，因为你相同的数列表经过onesort分割后的哨兵值就是第一个元素，也就是你10万个元素就要做10万次onesort。

为什么quicksort快就是因为他大部分时候能把数组分割成两部分，然后时间复杂度为可以NlogN。你的onesort是首元素哨兵法，那么对于有序数组只能分割成(0,0)和（1,N）两个数组，最坏情况是logN2。要么你换一种onesort方法比如选取随机值哨兵，要么在排序前先检测一下是否已经数组已经排好。

不感兴趣

开通SVIP免广告

尝试优化一下
1.数组改成全局变量，避免分配
2.在onesort函数后面加__attribute__((always_inline))
3.pivot选择median of three

最笨的方法是在quicksort函数里加一个检查是否数组有序的判断

1、解决区间所有数都相同的情况
每次onesort找出区间的最小最大值，如果它们相等返回-1表示不需要排序了
2、解决区间已经有序(升或降)
left、mid、right三数取中做枢纽

快速排序在最坏情况下的时间复杂度是(n^2). 当序列已经是有序时，就是这种情况。
若大部分数据有序时，情况也一样。

按照前面吧友提的建议，修改程序如下。这个应该能通过

三数取中，子函数取最左边最右边和中间的数返回中间数，然后用中间数做key
三路划分，将跟key相等的数放到中间。begin指向最左边，end指向最右边，cur从begin+1位置开始遍历，cur比end大时结束。当cur遇小时，跟begin交换，begin++，cur++。遇大时跟end交换，end++。再递归左区间letf，begin-1，右区间end+1，right

不感兴趣

开通SVIP免广告

哨兵的问题，最坏情况会退化到O（n^2）

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

1 2 下一页尾页
35回复贴，共2页
，跳到页

<<返回c语言吧

分享到:

日	一	二	三	四	五	六