排序算法——合并排序与自底向上合并排序

在我们之前的算法设计课程中,我们学习了合并排序与自底向上合并排序算法,今天我们就来分析一下这个算法。

合并算法

无论是合并排序还是自底向上合并排序,他的实现都基于一个重要的算法:合并算法(merge算法)。Merge算法实现的功能是将两个数组合并成为一个数组,我们可以定义一个结果数组b,再分别定义两个索引p1、p2,分别指向两
个数组的头,将p1、p2指向的两个数进行比较,并将较小的那一个放入数组b

Merge算法的伪码如下:

merge(p, q, r, a[]):

s←p; t←q+1; k←p
while s≤q and t≤r
	if a[s] ≤ a[t] then
		b[k] ← a[s]
		s ←s+1
    else
        b[k]←a[t]
        t←t+1
    end if
        k←k+1
end while
if s=q+1 then b[k...r]←a[t...r]
else b[k...r]←a[s...q]
end if
a[p...r]←b[p...r]

自底向上合并排序算法

自底向上合并算法顾名思义,就是从最底部开始,将数组元素两两合并,再将合并后的数组两两合并,直到重新合并成一个完整的数组。对于数组a = {9,4,5,2,1,7,4,6}的合并过程可以用如下图来表示:

完整代码(java)

//自底向上合并排序
public class BottomUpSort {
    public static void main(String args[])
    {
        int a[] = {9,4,5,2,1,7,4,6};
        bottomUpSort(a);
        for(int i=0;i<a.length;i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
    
    public static void bottomUpSort(int a[])
    {
        int i, s, t = 1;
        while(t < a.length-1)
        {
            s = t;
            t = 2*s;
            i = 0;
            for(;i+t < a.length;i+=t)
                merge(i, i+s-1, i+t-1, a);    //自底向上进行排序
            if(i+s-1 < a.length-1)    //判断是否有落单元素
                merge(i, i+s-1, a.length-1, a);
            
        }
    }
    
    public static void merge(int low, int mid, int high, int a[])
    {
        int b[] = new int[a.length];    //    建立转存数组
        int f = low, s = mid+1, p = low;
        //f为第一个数组索引,s为第二个数组索引,p为b数组索引
        while(f<=mid && s<=high)
        {
            //在两个数组元素中值小的一方放入b数组
            if(a[f] <= a[s])
            {
                b[p] = a[f];
                f++;
            }
            else
            {
                b[p] = a[s];
                s++;
            }
            p++;
        }
        
        if(f == mid+1)    //若第一个数组中的元素全部存储进去了,那么将第二个数组中的剩余元素全部放入b数组
            for(;s <= high && p<=high;p++,s++)
                b[p] = a[s];
        else //否则将第一个数组中的元素全部放入b数组
            for(;f<=mid && p<=high;p++,f++)    
                b[p] = a[f];
        
        for(int i=low;i<=high;i++)
            a[i] = b[i];
    }
}

合并排序算法

合并排序算法与自底向上合并排序十分相似(废话!),只不过与自底向上合并排序不同的是,合并排序是一个自顶向下的过程。我们可以将一整个数组拆分成两个数组,将其中的一个数组再进行拆分,直到拆分成两个单个元素,再将他们合并…重复此过程直到整个数组都重新合并完毕。

对于数组a[]={9,4,5,2,1,7,4,6}的合并排序可以用如下图示表示:

合并排序算法伪代码如下:

mergesort(low, high, a[]):

if low<high then
	mid←(low + high)/2
    ergesort(low, mid, a)
    mergesort(mid+1, high, a)
    merge(low, mid, high, a)
end if

完整代码(Java)

//合并排序算法
public class MergeSort {
    public static void main(String args[])
    {
        int a[] = {9,4,5,2,1,7,4,6};
        mergeSort(0, a.length-1, a);
        for(int i=0;i<a.length;i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
    
    //合并排序
    public static void mergeSort(int low, int high, int a[])
    {
        if(low < high)
        {
            int mid = (low + high)/2;
            mergeSort(low, mid, a);
            mergeSort(mid+1, high, a);
            merge(low, mid, high, a);
        }
    }
    
    //合并两个数组
    public static void merge(int low, int mid, int high, int a[])
    {
        int b[] = new int[a.length];    //    建立转存数组
        int f = low, s = mid+1, p = low;
        //f为第一个数组索引,s为第二个数组索引,p为b数组索引
        while(f<=mid && s<=high)
        {
            //在两个数组元素中值小的一方放入b数组
            if(a[f] <= a[s])
            {
                b[p] = a[f];
                f++;
            }
            else
            {
                b[p] = a[s];
                s++;
            }
            p++;
        }
        
        if(f == mid+1)    //若第一个数组中的元素全部存储进去了,那么将第二个数组中的剩余元素全部放入b数组
            for(;s <= high && p<=high;p++,s++)
                b[p] = a[s];
        else //否则将第一个数组中的元素全部放入b数组
            for(;f<=mid && p<=high;p++,f++)    
                b[p] = a[f];
        
        for(int i=low;i<=high;i++)
            a[i] = b[i];
    }
}