这道题 闫总的模版和讨论区第一个可以看一下啊, 然后讨论区第一个当时有一个问题, 答主是这么回复我的.
记录一下:
问
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
- 首先 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); 不执行