排序算法(四)：归并排序

傷城~ 2022-06-01 07:50 195阅读 0赞

#### **一、算法思想** ####

归并排序的实现分为递归实现与非递归实现。  
递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。  
非递归实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。

#### **二、具体算法描述** ####

*  把长度为n的输入序列分成两个长度为n/2的子序列
 *  对这两个子序列分别采用归并排序
 *  将两个排序好的子序列合并成一个最终的排序序列

#### 归并排序主要依赖的是**归并操作**，来看看归并操作的过程 ####

*  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 *  设定两个指针，最初位置分别为两个已经排序序列的起始位置
 *  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
 *  重复步骤3直到某一指针到达序列尾
 *  将另一序列剩下的所有元素直接复制到合并序列尾

![这里写图片描述][SouthEast]

// 最差时间复杂度 ---- O(nlogn)
    // 最优时间复杂度 ---- O(nlogn)
    // 平均时间复杂度 ---- O(nlogn)
    // 空间复杂度 ------ O(n)
    // 稳定性 ------------ 稳定
    
    void Merge(int* arr, int left, int mid, int right, int* tmp)
    {
        int index1 = left;
        int index2 = mid;
        int index = left;
    
        while (index1 < mid&&index2 < right)
        {
            if (arr[index1] < arr[index2])
            {
                tmp[index++] = arr[index1++];
            }
            else
            {
                tmp[index++] = arr[index2++];
            }
        }
        while (index1 < mid)
            tmp[index++] = arr[index1++];
        while (index2 < right)
            tmp[index++] = arr[index2++];
    
        memcpy(arr + left, tmp + left, (right - left)*sizeof(int));
    
    }
    void _MergeSort(int* arr, int left, int right, int* tmp)
    {
        if (right - left <= 1)
        {
            return;
        }
        if (left < right)
        {
            int mid = left + ((right - left) >> 1);
            _MergeSort(arr, left, mid, tmp);//左边有序
            _MergeSort(arr, mid, right, tmp);//右边有序
            Merge(arr, left, mid, right, tmp);//合并两个有序序列
        }
    }
    void MergeSort(int* arr, int left, int right)
    {
        int* tmp = new int[right - left];
        _MergeSort(arr, left, right, tmp);
        delete[] tmp;
    }

#### 再来看看归并排序的非递归实现： ####

//非递归版本
    void MergeSortNoR(int* arr, int size)
    {   
        int* tmp = new int[size];
        int gap = 1;
        while (gap < size)
        {
            for (int i = 0; i < size; i += gap * 2)
            {
                int left = i;
                int mid = i + gap;
                int right = mid + gap;
                if (mid > size)
                {
                    mid = size;
                }
                if (right > size)
                {
                    right = size;
                }
                Merge(arr, left, mid, right, tmp);
            }
            gap *= 2;
        }
        delete[] tmp;
    }

[SouthEast]: /images/20220601/1e6ff5d4d0d04f89801bcd6c3c23923c.png