#include<iostream>
using namespace std;
int a[100000];
int n;
void sort(int left, int right)
{
	if (left >= right) return;
	int i, j, key;
	i = left;
	j = right;
	key = a[i];
	while (i < j) {
		while (i < j && a[j] >= key) j--;
		a[i] = a[j];
		while (i < j && a[i] <= key) i++;
		a[j] = a[i];
	}
	a[i] = key;
	sort(left, i - 1);
	sort(i + 1, right);
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(0, n - 1);
	for (int i = 0; i < n; i++) cout << a[i] << " ";
	return 0;

}

 代码如上所示，和百度百科里的C版本一模一样，而后三个点均超时。下载了第三个点的数据，发现是从1到100000。是因为我每次选择的比大小的数恰好都是最小的所以实际上还是$O(n^2)$?