算法分析與設計實驗一 分治政策

                                            實驗一  分治政策

實驗目的：

  了解分治法的算法思想，閱讀實作書上已有的部分程式代碼并完善程式， 加深對分治法的算法原理及實作過程的了解。

實驗内容：

  用分治法實作一組無序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，程式設計實作分别用這兩種方法将輸入的一組無序序列排序為有序序列後輸出。

實驗代碼：

//分治法實作兩路合并排序和快速排序
//包含所需各種頭檔案 
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

class SortableList
{
public:
    SortableList(int mSize)  //構造函數
    {
        maxSize=mSize;
        l=new int[maxSize];
        n=0;
    }
    ~SortableList()   //析構函數
    {
        delete []l;
    }
    
    void Iuput();   //輸入待排序列
    void Output();  //輸出已經排序好的序列

    void MergeSort();   //合并排序
    void MergeSort(int left,int right);
    void Merge(int left,int mid,int right);

    void QuickSort();  //快速排序
    void Swap(int i,int j);    //交換下标為 i 和 j 的數組元素
    void QuickSort(int left,int right);
    int Partition(int left,int right);  //分化函數 
private:
    int *l;
    int maxSize;    
    int n;          //數組已有元素個數
};

void SortableList::MergeSort()  //Merge函數
{
    MergeSort(0,n-1);
}

void SortableList::MergeSort(int left,int right)  //兩路合并排序
{
    if (left<right)
    {
        int mid=(left+right)/2;
        MergeSort(left,mid);
        MergeSort(mid+1,right);
        Merge(left,mid,right);
    }
}

void SortableList::Merge(int left,int mid,int right)   //Merge函數
{
    int *temp=new int[right-left+1];
    int i=left,j=mid+1,k=0;
    while((i<=mid)&&(j<=right))
       if (l[i]<=l[j]) temp[k++]=l[i++];
       else temp[k++]=l[j++];
    while (i<=mid)  temp[k++]=l[i++];
    while (j<=right) temp[k++]=l[j++];
       for (i=0,k=left;k<=right;) 
           l[k++]=temp[i++];
}

void SortableList::Swap(int i,int j)  //值交換
{
    int c=l[i];
    l[i]=l[j];
    l[j]=c;
}

int SortableList::Partition(int left,int right)  //分化函數
{
    int i=left,j=right+1;
    do{
         do i++; while (l[i]<l[left]);
         do j--; while (l[j]>l[left]);
         if (i<j) Swap(i,j);
    }while (i<j);
    Swap(left,j);
    return j;
}

void SortableList::QuickSort()  //快速排序
{
    QuickSort(0,n-1);
}
void SortableList::QuickSort(int left,int right)  //快速排序
{
    if (left<right)
    {
        int j=Partition(left,right);
        QuickSort(left,j-1);
        QuickSort(j+1,right);
    }
}

//輸入函數
void SortableList::Iuput()
{
    int num;
    cout<<"請輸入數組元素個數:";
    cin>>num;
    n=num;
    cout<<"請輸入"<<n<<"個整數:";
    int i;
    for(i=0;i<n;i++)
    {
        cin>>l[i];
    }
}

//輸出函數
void SortableList::Output()
{
    int i;
    for(i=0;i<n;i++)
    {
        cout<<l[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    SortableList sortablelist(100);   //自動調用構造函數初始化最大數組大小,此處mSize指派100

    sortablelist.Iuput();  //輸入待排序列
   
    getchar();
    cout<<"請做出選擇（選擇合并排序請輸入字元'm',快速排序請選擇字元'q')"<<endl;
    char c;   
    c=getchar();
    if(c=='m'){
    //合并排序
    sortablelist.MergeSort();
    cout<<"合并排序之後:";
    sortablelist.Output();
    }
    
    if(c=='q')
    {
    //快速排序
    sortablelist.QuickSort();
    cout<<"快速排序之後:";
    sortablelist.Output();
    }
    
    return 0;
}      

運作截圖：