AcWing 785. 快速排序
原题链接
简单
作者:
计算机协会专用
,
2021-01-23 09:53:26
,
所有人可见
,
阅读 170
题目描述
样例
算法1
(暴力枚举) $O(n^2)$
时间复杂度
参考文献
C++ 代码
算法2
(暴力枚举) $O(n^2)$
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
#define N 1000000
int a[N];
void quick_sort(int arr[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1;
int x = arr[l + r >> 1];
while(i < j)
{
do {i ++; } while(arr[i] < x);
do {j --; } while(arr[j] > x);
if(i < j) swap(arr[i], arr[j]);
}
quick_sort(arr ,l ,j ),quick_sort(arr, j+1, r);
}
int main()
{
int count, i;
cin >> count;
for(i = 0; i < count; i++)
{
cin >> a[i];
}
quick_sort(a,0, count - 1);
for(i = 0; i < count; i++)
{
cout << a[i] << " ";
}
return 0;
}