2008年11月20日 星期四

971 OOP Midterm Exam: Quicksort

1.分割步驟:選取未經過排序陣列的第一元素,並決定他最後排列之位置(也就是位置的左方比此元素小,而右方比此元素大),之後分割成兩個子陣列。
2.遞迴步驟:對未排序之子陣列執行步驟1。

------------------------------------------------<程式開頭>--------------------------------------
#include <iostream>
#include<iomanip>
using namespace std;

int QS(int, int, int);//遞迴的副程式宣告

int n[10]={0};//初始陣列
int m[10]={0};//排序用陣列

int main(void)
{
    int i=0;//迴圈計算數
   
    cout<<"Quicksort程式\n請輸入10個整數數字進行排列\n";
    for(i=0;i<10;i++)//輸入數列
    {
        cin>>n[i];
        m[i]=n[i];//拷貝一份至m陣列。n陣列為保留值,不作異動
    }
    cout<<"你輸入的數列為:\n";
    for(i=0;i<10;i++)//將輸入的數值輸出供檢視之用
    {
        cout<<setw(6)<<n[i];
    }
    cout<<endl;
   
    QS(9,0,9);//進行排序
   
   
    cout<<"排序後的數列為:\n";
    for(i=0;i<10;i++)//輸出排序後之數列
    {
        cout<<setw(6)<<m[i];
    }
    cout<<endl;
    system("pause");
}


int QS(int a, int s, int o)//a為判斷的基數,s為左邊界,o為右邊界
{
    int c=0, p=s, q=o;//c為交換數值暫存用,p為此陣列之左邊界,q為此陣列之右邊界
   
    for(;s<o;)
    {
        for(;s<o;o--)//由右方開始比較大小
        {
            if(m[s]>m[o])
            {
                c=m[o], m[o]=m[s], m[s]=c;//兩兩交換
                break;
            }
        }
        a=o;//記錄基數位置
      
        for(;s<o;s++)//由左方開始比較大小
        {
            if(m[s]>m[o])
            {
                c=m[o], m[o]=m[s], m[s]=c;//兩兩交換
                break;
            }
        }
        a=s;//記錄基數位置
    }
   
    if((p<a-1)||(a+1<q) )//分割為左右兩陣列
        QS(a,p,a-1), QS(a,a+1,q);
    return 0;
}

------------------------------------------------<程式結尾>--------------------------------------


程式執行畫面

沒有留言:

張貼留言