本文最后更新于:2021年5月21日晚上6点49分
快速排序模板题: ACwing——快速排序模板题
模板代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 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]
利用双指针来调整区间
递归处理左右区间
偷懒做法: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #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
的效率会更高