排序—归并排序及动画演示

之前看了选择和插入排序,这两个算法是的时间复杂度均为O(n^2),而随着问题规模n的增大,插入和选择排序都比较慢。

     归并排序时的时间复杂度为O(nlgn) 其主要思想是分治法(divide and conquer),分就是要将n个元素的序列划分为两个序列,再将两个序列划分为4个序列,

直到每个序列只有一个元素,最后,再将两个有序序列归并成一个有序的序列。

例如两个序列:

要归并成一个有序的序列,按照我们常规的方法,我们每次从两个列表开头元素选取较小的一个,直到某一个列表到达底部,再将另一个剩下部分顺序取出。其实如果将每个元素最后添加一个最大值,则无需判断是否达到列表尽头。

代码如下:merge函数的功能为将A中[low,mid],[mid+1,high]归并成一个有序的片段。

template<class T> void merge(T A[],int low,int mid,int high)
{
    //low to mid as the left array   mid+1 to high as the right array
    int llen = mid-low+2;
    int rlen = high-mid+1;
    T *left = (T*)new T[llen];
    T *right = (T*)new T[rlen];
    //copy the low to mid to the temp array left
    for (int i=0;i<llen-1;i++)
    {
        left[i] = A[low+i];
    }
    for (i=0;i<rlen-1;i++)
    {
        right[i] = A[mid+1+i];
    }
    //set the sentinel
    left[llen-1] = numeric_limits<T>::max();
    right[rlen-1]= numeric_limits<T>::max();
    //merge the two array and copy to A[low,high];
    int j = 0;
    int k = 0;
    for (i = low; i < high+1 ;i++)
    {
        if (left[j] < right[k])
        {
            A[i] = left[j];
            j++;
        }
        else
        {
            A[i] = right[k];
            k++;
        }
    }
   delete [] left;
   delete [] right;
}

归并排序就是多次调用merge

template<class T> merge_sort(T A[],int low,int high)
{
    int mid = (low+high)/2;
    if (low < high)
    {
        merge_sort(A,low,mid);
        merge_sort(A,mid+1,high);
        merge(A,low,mid,high);
    }
}

这是一个递归算法,这个算法的理解其实可以借助下面这个图:

对于原始的数组2,1,3,8,5,7,6,4,10,在整个过程执行的是顺序是途中红色编号1-20。虽然我们描述中说的是程序先分解,再归并,但实际过程是一边分解一边归并,前半部分分先排好序,后半部分再拍好,最后整个归并为一个完整的序列,途中的merge过程它所在层的两个序列的merge过程:下图展示了每个merge过程对作用于数组的哪部分(红色)。

整个过程就像一个动态的树,执行顺序就是对树的先序遍历顺序。

 

最后实验验证,对10000个倒序的数组进行排序,直接插入排序需1024ms,二归并排序只需20ms。

动画演示

如果引用本站的原创文章,请注明原文链接:,本站保留追究责任的权利!