归并排序

转载请注明出处。

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

假设升序排列n个元素。

1、将序列等分成两个子序列，0到第(0+n-1)/2个元素为第一个序列，第(0+n-1)/2+1元素到第n-1个元素为序列2。

2、将子序列再等分，直到子序列只含有一个元素。

3、从只含有一个元素的子序列开始，按升序两两合并，得到有序的子序列

4、将有序的子序列再两两合并，以此类推，直到合并为一个序列。

排序过程示意图​​​​

递归实现步骤：

• Divide the list into two sublists of nearly equal size.
• Mergesort both sublists.
• Merge the sorted sublists.

时间复杂度：

每次递归需要O (n)次比较，共有次递归， = 。所以共需要O(mn)次比较，,

即时间复杂度为O()。

测试代码：

#include<iostream>
#include<iterator>
using namespace std;

int divide(int list[], int first, int last)
{
     int middle( (first + last)/2 );
     return middle;
}
void merge(int list[], int temp[], int first, int middle, int last)
{
    int lastMerged, first1, first2;
    if(list[first]<list[middle+1])
    {
        lastMerged = first;
        first1 = first+1;
        first2 = middle+1;
    }
    else
    {
        lastMerged = middle+1;
        first2 = middle+2;
        first1 = first;
    }
    temp[0] = list[lastMerged];
    int i(1);
    while(first1 <= middle && first2 <= last)
    {
        if(list[first1]<list[first2])
        {
            lastMerged = first1;
            first1++;
        }
        else
        {
            lastMerged = first2;
            first2++;
        }
        temp[i] = list[lastMerged];
        i++;
    }
    if(first1 > middle)
    {
        while(first2 <= last)
        {
            temp[i] = list[first2];
            first2++;
            i++;
        }
    }
    else
    {
        while(first1 <= middle)
        {
            temp[i] = list[first1];
            first1++;
            i++;
        }
    }
    copy(temp, temp+(last - first + 1), &list[first]);
}

void mergeSort(int list[], int first, int last)
{
    if(first < last)
    {
        static int* temp = new int[last - first + 1];
        int middle( divide(list, first, last) );//divide
        mergeSort(list, first, middle);
        mergeSort(list, middle+1, last);
        merge(list, temp, first, middle, last);
    }
}

int main()
{
    ostream_iterator<int> screen(cout, ", ");
    int list[] = { 18, 8, 11, 9, 15, 20, 32, 61, 22, 48, 75, 83, 35, 3 };
    int length( sizeof(list)/sizeof(int) );
    mergeSort(list, 0, length-1);
    copy(list, list+length, screen);
    cout << endl;
    return 0;
}

参考资料：

百度百科，https://baike.baidu.com/item/归并排序/1639015?fr=aladdin

DATA STRUCTURES USING C++， SECOND EDITION， by D.S. MALIK。