讨论/综合讨论/执行时间和空间都超过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);
}
展开讨论
共 5 个讨论

找个小的数组自己模拟模拟就理解了。

l和r表示截取子数组排序的范围,
开头的nums[r]最后放到nums[t]上,比nums[t]小的放左边,比nums[t]大的右边。
最后左右的子数组排序。

2
    • 这个算法的本质是 选定一个标准数,这里选的是 最右侧的数。
      2.然后把所有小于这个标准数的都从左侧排队。
      3.最后一步把这个标准数与第一个大于等于他的交换
      4.从新的位置的前后,重复执行这个过程

举例5.3.1.2.4
执行第一次for循环后,为3.1.2.5.4,然后swap(nums[4],nums[5]), 3.1.2.4.5
此时t=3
然后递归排序3.1.2和5,5已经排好了。只递归3.1.2.可得到1.2.3
也排好了。结束了

1

这个就是索引t之前的元素都比索引r所在的元素小。也就是每次都以当前数组的最后一个元素为pivot。写法确实有意思,不过时间复杂度都是一样的。

1

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

看到有位兄die已经注释的很清楚了,更新下

//快速排序
//最好、平均都是O(NlogN), 最坏是一颗斜树O(N^2) 不稳定
//思想: 以最后一个元素作为划分元素,大于等于它的放右边,小的放左边
void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;

    //增加随机性,不然如果已经有序,取最左边,每次划分都只减少一个
    int m = l + (r - l) / 2;
    swap(nums[r], nums[m]);

    int t = l;//t表示最终划分元素应该在的位置
    for (int i = l; i < r; ++i) {//从从左到右扫描
        if (nums[i] < nums[r]) {//找打比划分元素小的
            swap(nums[t++], nums[i]);//所有小于t位置的元素往前靠
        }
    }
    swap(nums[t], nums[r]);//交换划分元素,现在划分元素放在t处
    quickSort(nums, l, t - 1);//排序t左边
    quickSort(nums, t + 1, r);//排序t右边
}