各种算法集合讲解合并排序.pdfVIP

合并排序  算法思想  合并排序是采用分治策略实现对n个元素进行排序的 算法，是分治法的一个典型应用和完 现。它是 一种平衡、简单的二分分治策略，其计算过程分为 三大步：  （1）分解：将待排序元素分成大小大致相同的两个 子序列。  （2 ）求解子问题：用合并排序法分别对两个子序列 递归地进行排序。  （3）合并：将排好序的有序子序列进行合并，得到 符合要求的有序序列。 算法设计  合并过程  合并排序的关键步骤在于如何合并两个已排好序的有序子 序列。为了进行合并，引入一个辅助过程 Merge(A,low,middle,high)，该过程将排好序的两个子序 列A[low:middle]和A[middle+1:high]进行合并。其中， low、high表示待排序范围在数组中的上界和下界， middle表示两个序列的分开位置，满足low≤middle＜ high；由于在合并过程中可能会破坏原来的有序序列，因 此，合并最好不要就地进行，本算法采用了辅助数组 B[low:high]来存放合并后的有序序列。 算法设计  合并方法 设置三个工作指针i，j ，k。其中，i和j指示两 个待排序序列中当前需比较的元素，k指向辅 助数组B中待放置元素的位置。比较A[i]和A[j] 的大小关系，如果A[i]小于等于A[j] ，则 B[k]=A[i]，同时将指针i和k分别推进一步；反 之，B[k]=A[j]，同时将指针j和k分别推进一步。 如此反复，直到其中一个序列为空。最后，将 非空序列中的剩余元素按原次序全部放到辅助 数组B的尾部。 算法描述及分析  从算法的描述中，不难发现语句 if((!s[j])&&(dist[j]<temp))对算法的运行时间贡献 最大，因此选择将该语句作为基本语句。当外层循 环标号为1时，该语句在内层循环的控制下，共执行 n次，外层循环从1~n，因此，该语句的执行次数为 2 2 n*n=n ，算法的时间复杂性为O(n ) 。  实现该算法所需的辅助空间包含为数组s和变量i、j 、 t和temp所分配的空间，因此，Dijkstra算法的空间 复杂性为O(n)。 算法描述 void Merge(int A[] ，int low，int middle，int high)  {  int i,j,k; int *B=new int[high-low+1];  i=low; j=middle+1; k=low;  while(i<=middle&&j<=high) //两个子序列非空  if(A[i]<=A[j]) B[k++]=A[i++];  else B[k++]=A[j++];  while (i<=middle) B[k++]=A[i++];  while (j<=high) B[k++]=A[j++];  for(i=low;i<=high;i++) A[i++]=B[i++];  } 算法描述——递归形式  void MergeSort (int A[] ，int low，int high)  { int middle;  if (low<high)  {  middle=(low+high)/2; //取中点  MergeSort(A,low,middle); 