• 欢迎光临~

acwing 785.快速排序

开发技术 开发技术 2022-10-16 次浏览

这道题 闫总的模版和讨论区第一个可以看一下啊, 然后讨论区第一个当时有一个问题, 答主是这么回复我的.
记录一下:

do i++; while(q[i] < x); 会使得 q[l..i-1] <= x, q[i] >= x
这里 q[l..i-1] <= x 可以等于吗, 循环条件是小于叭

答曰:

主要原因是与循环不变式的<=配合,原因就变成了循环不变式为什么不能是 <
因为循环不变式是q[l..i] < x的话不能描述这个快排算法
假定循环不变式是 q[l..i] < x
交换前 q[l..i-1]<x,由于 swap 的两个元素 q[i] >= x q[j] <= x,交换之后就变成 q[l..i]<=x了,所以循环不变式是q[l..i]<x不能描述这个快排算法
所以无论是循环不变式还是中间过程的q[l..i-1], 都需要是 <=x




用算法笔记中的模板, 已经做了随机取第一个数的优化之后, 当10w个数字一样的时候, 仍然会超时, 下面给出一下原因和优化方案

算法笔记, 快速排序:
int quick_sort(int a[], int l, int r) {
    int t = round(1.0 * rand()/RAND_MAX * (r - l) + l);
    swap(a[l], a[t]);
    int temp = a[l];
    while (l < r) {
        while (l < r && a[r] > temp) r--;
        a[l] = a[r];
        while (l < r && a[l] <= temp) l++;   // 注意这里和之后的不同
        a[r] = a[l];
    }
    a[l] = temp;
    return l;
}

void quick_s(int a[], int l, int r) {
    if (l < r) {
        int mid = quick_sort(a, l, r);
        quick_s(a, l, mid - 1);
        quick_s(a, mid + 1, r);
    }
}

分析:

为什么上面这个会超时呢, 我们假定a[]是全部一样的数组, 那么:
while (l < r && a[r] > temp) r--; 不会执行, r 保持为 e
然后while (l < r && a[l] < temp) l++; 执行 l 一直加到 r, 然后return一个 r
然后下一次quick_s的时候, mid是r, 这个时候只会进行quick_s(a, l, mid - 1);
那么前面一大坨, 相当于只处理了最后一个下标为r的数据, 每次处理一个, 自然承受不了




然后看到知乎有个文章
面试官:手写一个快速排序,并对其改进 (注意里面的代码有个地方是错了, 下面注释指出)
https://zhuanlan.zhihu.com/p/82671667

int quick_sort(int a[], int l, int r) {
    int t = round(1.0 * rand()/RAND_MAX * (r - l) + l);
    swap(a[l], a[t]);
    int temp = a[l];
    while (l < r) {
        while (l < r && a[r] > temp) r--;    // 记为①号,   这里没有等号哦   文章中有,是错的,通不过
        if (l < r) a[l++] = a[r];            // 记为②号,   这里加了if判断和++
        while (l < r && a[l] < temp) l++;    // 记为③号,   这里没有等号哦
        if (l < r) a[r--] = a[l];            // 记为④号,   这里加了if判断和--
    }
    a[l] = temp;
    return l;
}

void quick_s(int a[], int l, int r) {
    if (l < r) {
        int mid = quick_sort(a, l, r);
        quick_s(a, l, mid - 1);
        quick_s(a, mid + 1, r);
    }
}

分析:

这么优化的原因, 还是假设a[]全部相同, 一步一步走一遍
第一次while循环, r还是保持不懂, 然后这个时候 if判断之后, l会加上1
下一次循环时候就从加一之后的结果循环 , 注意这里是小于号不是小于等于号, 所以不会执行第二个while (l < r && a[l] < temp) l++;
然后进行if 判断, r赋值a[r--] = a[l]; 之后减一, 那么 r会减去一个1
然后l r应该是会一直往中间夹, 每次都能二分

然后看一下这个优化之后的做法, 对于普通的数列是怎么样子处理的:
假设 a[]是 3, 1, 2, 4, 5

  1. 首先 int mid = quick_sort(a, l, r);
    l 为0, r为4, temp为3
    进去之后, ①找到第一个小于等于3的数是2, r = 2
    然后执行②, a[0]变为a[r]也就是a[2], 变为2, l加一变为1
    然后执行③, l变为2
    ④的if不执行, 这里是精髓哦, 因为每次做了++ --操作, 所以赋值的时候需要进行if判断一下下标
    l r 相遇为2, 找到mid数字是2, 然后变为temp也就是3, 也就是数组变为2 1 3 4 5
    然后得到mid = 2, quick_s(a, l, mid - 1);也就是quick_s(a, 0, 1);
    quick_s(a, mid + 1, r); 也就是quick_s(a, 3, 4); 依次进行

继续分析, 看一下如果不加上两个if 会变成啥样: 这也是我之前出错的地方

下面错误的哦

int quick_sort(int a[], int l, int r) {
    int temp = a[l];
    while (l < r) {
        while (l < r && a[r] > temp) r--;    
        a[l++] = a[r];                       
        while (l < r && a[l] < temp) l++;    
        a[r--] = a[l];                       
    }
    a[l] = temp;
    return l;
}

void quick_s(int a[], int l, int r) {
    if (l < r) {
        int mid = quick_sort(a, l, r);
        quick_s(a, l, mid - 1);
        quick_s(a, mid + 1, r);
    }
}

①是一样的, r到2
②中一样的, l变为1, 序列变为2 1 2 4 5
③一样的, l变为2
④ 注意咯, 这个时候不加if判断, 赋值这里没啥问题, 但是r--之后会变成1, 那return到底是返回 l 还是 r呢, 所以错了.

继续分析, 如果有一个while 带了等号会怎么样, 这里报错的用例还是10w个相同数字的, 走一遍分析

int quick_sort(int a[], int l, int r) {
    int t = round(1.0 * rand()/RAND_MAX * (r - l) + l);
    swap(a[l], a[t]);
    int temp = a[l];
    while (l < r) {
        while (l < r && a[r] > temp) r--;    // 记为①号,   
        if (l < r) a[l++] = a[r];            // 记为②号,   
        while (l < r && a[l] <= temp) l++;    // 记为③号,   有等号哦
        if (l < r) a[r--] = a[l];            // 记为④号,   
    }
    a[l] = temp;
    return l;
}

void quick_s(int a[], int l, int r) {
    if (l < r) {
        int mid = quick_sort(a, l, r);
        quick_s(a, l, mid - 1);
        quick_s(a, mid + 1, r);
    }
}

假设a[] 全部一样, 那么
①执行之后, r不变
②执行
③执行, l增加到和r一样
然后l 和 r都是最后一个, return,
然后后面的 quick_s(a, l, mid - 1); 也就是 quick_s(a, l, r- 1); 还是处理了一个元素, 所以会报错
quick_s(a, r + 1, r); 不执行

程序员灯塔
转载请注明原文链接:acwing 785.快速排序
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com