MENU

Catalog

    排序(4):归并排序

    June 9, 2018 • 技术

    系列文章目录

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

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

    /* 把有序的 array[left]...array[mid] 和 array[mid+1]...array[right] 合并 */
    void Merge(int array[], int temp[], int left, int mid, int right)
    {
        int i = left;
        int j = mid + 1;
        int k = left;
      
        while (i <= mid && j <= right)
        {
            if (array[i] < array[j])
                temp[k++] = array[i++];
            else
                temp[k++] = array[j++];
        }
    
        while (i <= mid)
            temp[k++] = array[i++];
        while (j <= right)
            temp[k++] = array[j++];
    
        while (left <= right)
            array[left] = temp[left++];
    }
    
    /* temp[] 数组起到一个中转的作用 */
    void MergeSort(int array[], int temp[], int left, int right)
    {
        if (left >= right)
            return;
      
        int mid = ((right - left) >> 1) + left;
      
        MergeSort(array, temp, left, mid);
        MergeSort(array, temp, mid + 1, right);
      
        Merge(array, temp, left, mid, right);
    }

    Merge()耗时$O(n)$,则归并排序的时间递归式为$T(n)=2T(\frac n2)+O(n)$,解得$T(n)=O(nlogn)$。

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