一個數組中求第k大的數。 4 1 1 3 9 2 求第4大的數。 時間復雜度
//4 1 1 3 9 2#include<iostream>#include<cstdio>using namespace std;int a[1001];int n,k;void qst(int l,int r){ if(l>r) return; int tmp=a[l],i=l+1,j=l+1;//a[1] a[2] a[3] a[4] while(i<=r) { if(a[i]>tmp) i++; else swap(a[i],a[j]),i++,j++;//<=交換 } j--; swap(a[l],a[j]); if(j==k) cout<<a[k]<<endl; qst(l,j-1); qst(j+1,r); }int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); qst(1,n);// for(int i=1;i<=n;i++)// cout<<a[i]<<" ";}雙路快排，一直覺得這個比較難寫
#include<iostream>#include<cstdio>using namespace std;int n,a[1001];void qst(int l,int r){ if(l>r) return; int tmp=a[l]; int i=l+1,j=r; while(1) { while(i<=r && a[i]<=tmp) i++; while(j>=l+1 && a[j]>=tmp) j--; if(i>j) break; swap(a[i],a[j]); i++; j--; } swap(a[l],a[j]); qst(l,j-1); qst(j+1,r);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); qst(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" ";}三路快排，值得一學的是它的邊界處理
#include<iostream>#include<cstdio>using namespace std;int n,a[1001];void qst(int l,int r){ if(l>r) return; int tmp=a[l]; int lt=l;//[l+1,lt]< 空 int gt=r+1;//[gt,r]>v 空 int i=l+1;//[lt+1,i)==v 空 while(i<gt) { if(a[i]<tmp){ swap(a[i],a[lt+1]),lt++,i++; } else if(a[i]>tmp) { swap(a[i],a[gt-1]),gt--; } else{ i++; } } swap(a[l],a[lt]); qst(l,lt-1); qst(gt,r);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); qst(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" ";}新聞熱點
疑難解答
