讨论/综合讨论/执行时间和空间都超过100%的紧凑快排算法/
执行时间和空间都超过100%的紧凑快排算法
  1. 排序数组

大家分析分析这个快速排序算法怎么做到的,代码写的特别紧凑,执行时间最快24ms,内存17.6M。都超过100%提交

感觉有点难理解,谁能解释一下?

void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;
    int t = l;
    for (int i = l; i < r; ++i) {
        if (nums[i] < nums[r]) {
            swap(nums[t++], nums[i]);
        }
    }
    swap(nums[t], nums[r]);
    quickSort(nums, l, t - 1);
    quickSort(nums, t + 1, r);
}
展开讨论

这和算法导论给的快排好像,只不过人家是伪代码,而且把t的取值封装掉了。
还有这个快排不是最好的吧,我记得有一道题一开始写了快排速度不快,然后加上随机算法速度快了好多,可能那题的示例比较毒。
你这个t取的是最右边的那个,那如果给你的示例都是右边的最大或者右边的最小,你这算法就退化到O(n^2)了。。。。

展开全部 5 讨论