Mergesort

最近要交作業才會真正認真的開始思考合併排序的好用之處，在網路上所參考到的碼較少為template實作之，所以花了一點小功夫改寫和包裝，也還算方便，以下程式碼不算是我寫的，我只是就古狗大神找到的C code改成template型式，使用了vector，這樣子會使程式碼較為簡潔而較能夠專精於整個程式的運作程，對我而言是一個不錯的學習方式

template<class T>
void MergeSort(vector<T>& u){
    merge_sort(u,0,u.size()-1);
}

template<class T>
void merge_sort(vector<T>& u,int low, int high){
    if(high>low){
        merge_sort(u,low,(low+high)/2);
        merge_sort(u,(low+high)/2+1,high);
        Merge(u,low,high);
    }
}

template<class T>
void Merge(vector<T>& u, int low, int high){
    vector<T> temp;
    
    for(unsigned int i=low, j=(low+high)/2+1 ; i<=(low+high)/2 || j<=high;){
        if(i>(low+high)/2)  temp.push_back(u[j++]);
        else if(j>high)     temp.push_back(u[i++]);
        else if(u[i]>u[j])  temp.push_back(u[j++]);
        else if(u[i]<u[j])  temp.push_back(u[i++]);
        else{
            temp.push_back(u[i++]);
            temp.push_back(u[j++]);
        }
    }
    for(unsigned int i=low,j=0;i<=high;i++,j++) u[i]=temp[j];
}

補上在wiki找到的quick sort 轉成實際C++ code(也是使用vector實作之)

template<class T>
void QuickSort(vector<T>& u){
    quicksort(u,0,u.size()-1);
}

template<class T>
void quicksort(vector<T>& u, int left, int right){
    int l_hold=left, r_hold=right, p_pivot=0;
    T pivot = u[left];
    while(left<right){
        while((u[right]>=pivot) && (left < right)) right--;
        if(left!=right){
            u[left] = u[right];
            left++;
        }
        
        while((u[left]<=pivot) && (left<right)) left++;
        if(left!=right){
            u[right]=u[left];
            right--;
        }
    }
    u[left]=pivot;
    p_pivot=left;
    
    left = l_hold;
    right = r_hold;
    
    if(left<p_pivot)  quicksort(u,left,p_pivot-1);
    if(right>p_pivot) quicksort(u,p_pivot+1,right);
}

---
下一次可以自行試著寫寫看了，總覺得這個Merge的判斷會造成速度的問題