数据结构与算法(java版)第二季 - 3 归并排序

目录

归并排序（Merge Sort）

merge细节

merge情况的出现

归并排序的复杂度

常见递推式和复杂度

---

归并排序（Merge Sort）

 1945年由约翰·冯·诺伊曼（John von Neumann）首次提出.

首先对大佬表示缅怀,保佑我找到好工作.

然后归并排序的过程是如下所示:

 执行流程:

merge细节

◼ 需要merge的2个序列是存在于同一个数组之中,并且是挨在一起的.

◼ 为了更好地完成 merge 操作，最好将其中 1 组序列备份出来，比如 [begin, mid) 

首先进行相应的li的一个赋值,相应的li=0,le=mid-begin.ri=mid,re=end.

其中使用相应的ai代表往其中的位置进行一个覆盖的过程,过程是比较简单的,就是需要进行相应的逻辑分析.

merge情况的出现

当左边是提前结束的,那么是就是右边是什么也不用干的

当右边是提前结束的,左边是仍然是需要进行一个拿出的过程.

具体实现的代码如下所示:

public class MergeSort extends Comparable> extends Sort{
    private E[] leftArray;
    protected void sort() {
        leftArray = (E[]) new Object[array.length >> 1];
        sort(0,array.length);
 
        //[0,array.lenth)
        //[0,array.lenth>>1)    [array.length>>1,array.length)
 
    }
 
    /**
     * 对[begin,end)范围内的数据进行一个归并排序
     *
     */
    //首先进行的是devide
    private void sort(int begin,int end)
    {
        if(end - begin < 2) return;
 
        int mid = (begin+end)>>1;
        sort(begin,mid);
        sort(mid,end);
        merge(begin,mid,end);
    }
 
    /**
     * 将[begin,mid)和[mid,end)范围进行一个合并的过程
     */
    private void merge(int begin,int mid,int end)
    {
        int li = 0,le = mid -begin;//左边
        int ri = mid,re = end;//右边
        int ai = begin;//对于右边的起始进行一个初始化的过程,这里应当是从begin开始的,老师这个地方出现了问题.
 
        //备份左边的数组
        for (int i = li;i < le;i++)
        {
            leftArray[i] = (E) array[begin + i];//这里应当注意的是相应的begin + i的原因
        }
 
        //只有是左边是没有结束的情况下,进行相应的操作(进行比对的前提)
        //如果左边是没有结束的
        while(li < le)
        {
            if(cmp((Integer) leftArray[li],array[ri]) > 0 && ri < re)
            {
                array[ai++] = (Integer) leftArray[li++];
            }
            else
            {
                array[ai++] = array[ri++];
            }
        }
    }
}

归并排序的复杂度

常见递推式和复杂度