MENU

Catalog

    排序(4):归并排序

    June 9, 2018 • 文章

    系列文章目录

    排序(1):直接插入排序,二分查找插入排序,希尔排序
    排序(2):快速排序
    排序(3):堆排序
    排序(4):归并排序
    排序(5):基数排序
    排序(6):总结

    对于待排序数组:{ 5, 2, 4, 6, 1, 3, 2, 6 },归并排序的思路如上图,注意上图是从下往上看。

    递归法

    void MergeSortRecursive(int array[], int* buf, int left, int right)
    {
        if (left >= right)
            return;
    
        int mid    = ((right - left) >> 1) + left;
        int left1  = left;
        int right1 = mid;
        int left2  = mid + 1;
        int right2 = right;
        MergeSortRecursive(array, buf, left1, right1);
        MergeSortRecursive(array, buf, left2, right2);
    
        int i = left;
        while (left1 <= right1 && left2 <= right2)
            buf[i++] = array[left1] < array[left2] ? array[left1++] : array[left2++];
    
        while (left1 <= right1)
            buf[i++] = array[left1++];
        while (left2 <= right2)
            buf[i++] = array[left2++];
    
        for (i = left; i <= right; i++)
            array[i] = buf[i];
    }
    
    void MergeSort(int array[], int left, int right)
    {
        int* buf = new int[right - left + 1];
        MergeSortRecursive(array, buf, left, right);
        delete[] buf;
    }

    归并排序的时间复杂度很容易计算,为$O(nlogn)$。

    Archives QR Code Tip
    QR Code for this page
    Tipping QR Code