各種排序算法的實現-10（歸並排序的實現）

歸並排序實際上也是一種選擇排序。 思路相對簡單，就不詳細的說了 下面是示例代碼

void Merge(int sourceArr[], int targetArr[], int startIndex, int midIndex, int endIndex)
{
    int i, j, k;
    for(i = midIndex+1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++)
    {
        if(sourceArr[startIndex] < sourceArr[i])
        {
            targetArr[j] = sourceArr[startIndex++];
        }
        else
        {
            targetArr[j] = sourceArr[i++];
        }
    }
	
    if(startIndex <= midIndex)
    {
        for(k = 0; k <= midIndex-startIndex; k++)
        {
            targetArr[j+k] = sourceArr[startIndex+k];
        }
    }
	
    if(i <= endIndex)
    {
        for(k = 0; k <= endIndex- i; k++)
        {
            targetArr[j+k] = sourceArr[i+k];
        }
    }
}
//內部使用遞歸，空間復雜度為n+logn
void MergeSort(int sourceArr[], int targetArr[], int startIndex, int endIndex)
{
    int midIndex;
    int tempArr[100]; //此處大小依需求更改
    if(startIndex == endIndex)
    {
        targetArr[startIndex] = sourceArr[startIndex];
    }
    else
    {
        midIndex = (startIndex + endIndex)/2;
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);

        Merge(tempArr, targetArr, startIndex, midIndex, endIndex);
    }
}

//調用
int main(int argc, char* argv[])
{
    int a[8]={50,10,20,30,70,40,80,60};
    int b[8];
    MergeSort(a, b, 0, 7);

    for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
        cout << b[i] << ' ';
    cout << endl;

    system("pause");
    return 0;
}