merge sort 程式碼疑問

最近要寫一個 C++的 merge sort 程式碼...

雖然知道 merge sort是如何計算...但是要寫成C++....

卻寫不出來....不知道有沒有人可以幫忙....

可以告訴小弟一下 思考的邏輯和該怎麼設嗎??

1 Answer

Rating
  • 1 decade ago
    Favorite Answer

    你參考一下吧

    #include <iostream>

    #include <time.h>

    #define MAXSIZE 100 // 假設要排序的數量有100個

    using namespace std;

    void merge(int ar[],int pos,int size,int sort[],int sort_index){

    if(size<=0) return;

    if(size==1){

    sort[sort_index]=ar[pos];

    return;

    }

    int lindex=pos;

    int mindex=pos+size/2;

    int rindex=mindex;

    int lsize=size/2;

    int rsize=size-lsize;

    merge(ar,lindex,lsize,sort,sort_index);

    merge(ar,rindex,rsize,sort,sort_index+lsize);

    for(int i=pos;i<pos+size;i++)

    ar[i]=sort[i];

    while(lindex<mindex && rindex<pos+size){

    if(ar[lindex]<ar[rindex])

    sort[sort_index++]=ar[lindex++];

    else

    sort[sort_index++]=ar[rindex++];

    }

    while(lindex<mindex) sort[sort_index++]=ar[lindex++];

    while(rindex<pos+size) sort[sort_index++]=ar[rindex++];

    }

    void Print(int ar[]){

    int i;

    for(i=0;i<MAXSIZE;i++){

    cout << ar[i] << " ";

    if(i%10==9) cout << endl;

    }

    cout << endl;

    }

    int main(){

    int ar[MAXSIZE],sort_ar[MAXSIZE];

    int i;

    // 先產生100個亂數,介於0~9999

    srand(time(NULL));

    for(i=0; i<MAXSIZE; i++) ar[i]=rand()%10000;

    // 輸出排序前

    cout << "排序前\n";

    Print(ar);

    // merge sort

    merge(ar,0,MAXSIZE,sort_ar,0);

    // 輸出排序後的結果sort_ar

    cout << "排序後\n";

    Print(sort_ar);

    cin.get();

    return 0;

    }

    • Login to reply the answers
Still have questions? Get your answers by asking now.