快排板子
从小到大排序
以j分界
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int l, int r){
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1]; // 1
while(i < j){
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
quick_sort(0, n - 1);
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
return 0;
}
注意1处的x只能取q[l + r >> 1]
,如果取q[l]
,由于测试数据中存在完全升序/降序的序列,这个时候,取q[l]
会使得快排复杂度变成\(O(n^2)\)从而被卡掉,而取q[r]
,用下面的数据会出现无限递归
2
1 2
以i分界
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int l, int r){
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r + 1 >> 1]; // 1
while(i < j){
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(l, i - 1);
quick_sort(i, r);
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
quick_sort(0, n - 1);
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
return 0;
}
注意1处的x只能取q[l + r + 1 >> 1]
,如果取q[r]
,由于测试数据中存在完全升序/降序的序列,这个时候,取q[r]
会使得快排复杂度变成\(O(n^2)\)从而被卡掉,而取q[l]
,用下面的数据会出现无限递归
2
1 2
复杂度
最坏情况下,第一层总复杂度为n,第二层总复杂度为n-1,...一共n层,所以总复杂度为\(n(n-1)/2\),而平均情况下,举一个最优的例子就是每一层都将当前序列均分成两个部分
每层的总复杂度均为\(n\),假设\(logn\)是整数,那么总层数就是\(logn+1\)(最后一层的总结点数为\(n\),假设层数为\(k\),则\(2^{k-1}=n\))所以快排最好情况下的复杂度为\(O(nlogn)\)。