快速排序
快速排序模板题:
模板代码:
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
void quick_sort( int q[], int l , int r)
{
if ( l == r ) return;
int i = l - 1 , j = r + 1, x = q[( l + r ) / 2];
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( q, l , j);
quick_sort( q, j + 1, r);
}
int main()
{
int n ;
cin >> n;
for ( int i = 0 ; i < n ; i ++) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1 );
for ( int i = 0 ; i < n ; i ++) cout << q[i] << " ";
return 0;
}
快速排序算法原理:
快速排序的本质思想:分治
快速排序的步骤:
- 确定分界点,这个分界点可以是随机的例如
q[i]
、q[(l+r)/2]
、q[r]
,一般来说习惯性取q[(l+r)/2]
- 利用双指针来调整区间
- 递归处理左右区间
偷懒做法:
#include <iostream>
#include <algorithm>
using namespace std;
int a[100010];
int main()
{
int n;
cin >> n;
for ( int i = 0 ; i < n ; i ++)
{
scanf("%d",&a[i]);
}
sort(a, a+n);
for ( int i = 0 ; i < n ; i ++)
{
cout << a[i] << " ";
}
return 0;
}
附注:
使用scanf
进行输入,168ms左右
而使用cin >>
进行输入, 需要365ms左右
因此大数据输入时,尽量使用scanf
,不容易TLE。
但是小数据输入时,敲cin
的效率会更高