排序算法_MergeSort

算法思想：

分治自顶而下实现归并排序：

分治法的三个步骤
设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
①分解：将当前区间一分为二，即求分裂点

②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
递归的终结条件：子区间长度为1（一个记录自然有序）

具体算法：

大致的代码如下：

 1 void MergeSortDC(SeqList R，int low，int high)

 2      {                            //用分治法对R[low..high]进行二路归并排序

 3        int mid；

 4        if(low<high)

 5         {                    //区间长度大于1

 6           mid=(low+high)/； //分解

 7           MergeSortDC(R，low，mid); //递归地对R[low..mid]排序

 8           MergeSortDC(R，mid+，high)； //递归地对R[mid+1..high]排序

 9           Merge(R，low，mid，high)； //组合，将两个有序区归并为一个有序区

         }

      }

算法分析：

（1）稳定性

归并排序是一种稳定的排序。

（2）存储结构

可用顺序存储结构。也易于在链表上实现。

（3）时间复杂度

对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

（4）空间复杂度

需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

注意：
　若用单链表做存储结构，很容易给出就地的归并排序

巴特西

排序算法_MergeSort

算法思想：

具体算法：

算法分析：

最新文章

热门文章