讨论/综合讨论/执行时间和空间都超过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);
}
展开讨论
    • 这个算法的本质是 选定一个标准数,这里选的是 最右侧的数。
      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
展开全部 5 讨论