题目描述
快速排序
样例
blablabla
算法1
时间复杂度
平均情况:O(nlogn)
最好/最坏情况(顺序/逆序):
选取最左、最右元素为轴点:O(n^2),退化为暴力算法
选取随机轴点、中点:O(nlogn)
C++ 代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
using namespace std;
const int N = 1e5;
int q[N];
void quicksort(int q[], int l, int r)
{
if (l >= r)return;
int m = q[rand() % (r - l+1)+l];//随机选取轴点
//int m = q[(r + l)>>1];//选取中点为轴点
int i = l-1;
int j = r+1;
while (i < j)
{
do
i++;
while (q[i] < m);//>还是>=
do
j--;
while (q[j] > m);//错误一:若先判断后do会有问题
if (i < j)swap(q[i], q[j]);//错误二:注意此处要判断是否i<j,此处为改进
/*
int t = q[i];
q[i] = q[j];
q[j] = t;//交换
*/
}
quicksort(q, l, j-1);
quicksort(q, i+1, r);//此处i,j中间元素为等于轴点的元素集合,减少了时间开销
}
int main()
{
int n;
cin >> n;
int i=0;
while (i != n)
{
cin >> q[i];
i++;
}
quicksort(q, 0, n - 1);
i = 0;
while (i != n)
{
cout << q[i]<<" ";
i++;
}
}
关于>还是>=的问题:
考察以下数组
2 4 3 5 1 3 2 5 7 6 9
以5为轴点
若用>=:
第一轮扫描结果
2 4 3 5 1 3 2 5 7 6 9
一次也没有交换