时间复杂度O(nlogn)
找一个基数,使得这个基数的左边都比它小,右边都比它大。
双指针实现,从左边找找到第一个比基数大下标为i, 从右边找到第一个比基数小的数下标为j,i、j交换。
i == j 时将基数与a[i]交换,分治继续对(l , i-1) 与(i+1 , r)区间进行排序。
//#include <bits/stdc++.h> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <cstdio> #include <string> #include <stdio.h> #include <queue> #include <stack> #include <map> #include <set> #include <string.h> #include <vector> #define ME(x , y) memset(x , y , sizeof(x)) #define SC scanf #define rep(i ,j , n) for(int i = j ; i < n ; i ++) #define INF 0x3f3f3f3f #define mod 1000000007 #define PI acos(-1) using namespace std; typedef long long ll ; int a[1009]; int n ; void quickp(int l , int r){ if(l > r) return ; int i = l , j = r ; while(j > i){ while(a[j] >= a[l] && i < j){ j--; } while(a[i] <= a[l] && i < j){ i++; } if(i < j) swap(a[i] , a[j]); } swap(a[l] , a[i]); quickp(l , i-1); quickp(i+1 , r); } int main() { cin >> n ; rep(i , 1 , n+1){ SC("%d" , &a[i]); } quickp(1 , n); rep(i , 1 , n+1){ cout << a[i] << " " ; } return 0 ; }
原文链接: https://www.cnblogs.com/nonames/p/12286104.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/328245
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!