讨论/综合讨论/执行时间和空间都超过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);
}
展开讨论
code047发起于 2020-01-15
最近编辑于 2020-01-15

看到有位兄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右边
}
展开全部 5 讨论