NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 npsc 2004國決 E.排順序

作者 主題: npsc 2004國決 E.排順序  (閱讀 605 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
npsc 2004國決 E.排順序
« 於: 五月 15, 2015, 08:52:35 pm »

代碼: [選擇]
// npsc04-j2e (2004國中決 題目 E 排順序)
// 模擬 qsort 遞迴,有swap時印出所有陣列

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const int maxn = 210;
int a[maxn];
int n;   // n 筆資料
void qsort(int lt, int rt)
{
if(lt==rt) return; // 如果只有一個就排好了
int lt0=lt, rt0=rt;
int x=a[lt] , t;
while( lt <rt )
{
while(a[lt]<x) ++lt; //左手比 x 小,往右移
while(a[rt]>x) --rt; //右手比 x 大,往左移
if(lt<rt)  // 左手 在 右手 的左邊
{
t=a[lt]; a[lt]=a[rt]; a[rt]=t;  //swap , 有交換 就印
cout << a[0]; for(int i=1; i<n; ++i) cout << " " << a[i];  cout << endl;
++lt;  --rt;
}
}
// 當左手 不在 右手 的左邊,就分組
qsort(lt0 , rt);  // 將右手及其左邊 分一組
lt = rt+1;
qsort(lt , rt0);  // 將右手的右邊  分一組
}

int main()
{
  int t ;
cin >> t;
while(t--)
{
cin >> n;
for(int i=0; i<n; ++i) cin >> a[i];
qsort(0,n-1);
cout << endl; //每一組後印一空白列
}
  return 0;
}
/*
輸入範例:
2
8
4 6 7 8 5 2 3 1
4
4 3 2 1
輸出範例:
1 6 7 8 5 2 3 4
1 3 7 8 5 2 6 4
1 3 2 8 5 7 6 4
1 2 3 8 5 7 6 4
1 2 3 4 5 7 6 8
1 2 3 4 5 6 7 8

1 3 2 4
1 2 3 4

*/

記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 npsc 2004國決 E.排順序