回复：快速排序超时

快排的最坏情况确实是n方复杂度

在这两行交换代码之前试着判断一下 left 和 high 是否不等？
快排本身的优势就是对无序的数组进行快速排序。O(n²)我看着都怕

不感兴趣

开通SVIP免广告

谁教你这么开数组的？
快速排序在数据大部分有序的情况下极易退化成冒泡排序

把轴值换成随机的，而非第一个元素

别用vla。隔壁c艹stl虽然一般用的快排，但人家会有个保底机制，递归过多转堆排

这种算法其实没必要纠结，打算竞直接大部分情况下sort就行就是考试手写算法你这也够了

建议先学一下排序的优化。

也可以试试希尔排序，写起来也简单。我之前拿洛谷的排序模板题试过，跑得和自己手写的随机枢轴三路快排一样快——不过数据量很大的情况下还是快排的表现更好

不感兴趣

开通SVIP免广告

取中值或者随机值吧，左右作为轴都很容易被卡

你的pivot选择还有优化空间，虽然能实现排序，但是选择第一个元素这种情况下有较大可能出现子问题划分不均，导致较大子问题的复杂度仍然接近O(n)，算法最终退化为O（n²），简单的优化方法你可以随机random一个下标值作为pivot然后和你的第一位交换，多一步操作，剩下完全一样

被卡了，取中值

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

分享到: