/******************************
*mergeSort
******************************/
#include "stdafx.h"
#include <vector>
using namespace std;
 
template <typename T>
void mergeSort(vector<T>& vec)
{
    vector<T> tempVec(vec.size());
    mergeSort(vec, tempVec, 0, vec.size()- 1);
}
 
template <typename T>
void mergeSort(vector<T>& vec, vector<T> tempVec, int left, int right)
{
    if (left < right)
    {
        int center = (left + right)/2;
        mergeSort(vec, tempVec, left, center);
        mergeSort(vec, tempVec, center+1, right);
        mergeFunc(vec, tempVec, left, center+1 , right);  //合并
    }
};
 
//合并函數(shù)
template <typename T>
void mergeFunc(vector<T>& vec, vector<T> tempVec, int left, int  Pos,int right)
{
    int leftPos        = left;          //左邊序列的位置，初始為左序列起點(diǎn)
    int leftEnd        = Pos-1 ;    //左邊序列的終點(diǎn)   
    int rightPos   = Pos;           //右邊序列的位置，初始為右序列起點(diǎn)
    int rightEnd   = right;   //右邊序列的終點(diǎn)
    int tempPos        = left;         //臨時(shí)數(shù)組的位置，初始為臨時(shí)數(shù)組的起點(diǎn)
    int numElements = right - left + 1;          //數(shù)組元素的個(gè)數(shù)
 
    //兩段數(shù)組合并
    //兩段數(shù)組已有序
    while (leftPos <= leftEnd && rightPos <= rightEnd) //左邊數(shù)組和右邊數(shù)組都沒(méi)有到終點(diǎn)
    {
        //比較左邊數(shù)組和右邊數(shù)組值的大小
        //把較小者放入臨時(shí)數(shù)組
        if (vec[leftPos] <= vec[rightPos])           
        {
            tempVec[tempPos++] = vec[leftPos++];
        }
        else
            tempVec[tempPos++] = vec[rightPos++];
    }
 
    // 只剩一個(gè)序列時(shí)，直接復(fù)制到臨時(shí)數(shù)組
    while (leftPos <= leftEnd)
    {
        tempVec[tempPos++] = vec[leftPos++];
    }
    while (rightPos <= rightEnd)
    {
        tempVec[tempPos++] = vec[rightPos++];
    }
 
    //將臨時(shí)數(shù)組的值復(fù)制回源數(shù)組
    int i = 0;
    for (; i< numElements; i++, rightEnd--)  //這里從后向前復(fù)制，因?yàn)榍懊嬗泻芏嗬�圾�?shù)據(jù)
    {
        vec[rightEnd] = tempVec[rightEnd];
    }
}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。