分治算法的经典案例——合并排序

x33g5p2x  于2022-02-28 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(158)

一 算法设计

合并排序是采用分治策略进行排序的算法,是分治算法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略。

算法步骤如下。

1 分解

将待排序元素分成大小大致相同的两个子序列。

2 治理

对两个子序列进行合并排序。

3 合并

将排好序的有序子序列进行合并,得到最终的有序序列。

二 算法图解

首先将待排序的元素分成大小大致相同的两个子序列,然后把子序列分成大小大致相同的两个子序列,如此下去,直到分解成一个元素为止,这时含有一个元素的子序列就是有序的;然后执行合并操作,将有两个有序的子序列合并为一个有序的序列,如此下去,直到所有元素都合并为一个有序序列时为止。

三 算法详解

1 合并操作

为了进行合并,需要一个合并函数 merge(A,low,mid,high),该函数将排好序的两个子序列A[low,mid]和A[mid+1,high]进行合并。其中,low、high 代表待合并的两个子序列在数组中的下界和上界,mid 代表下界和上界的中间位置,如下图所示。

这里有3个工作指针 i、j、k 和一个辅助数组B。其中 i 和 j 分别指向两个待排序的子序列中当前待比较的元素,k 指向辅助数组 B 中待放置元素的位置。比较 A[i] 和 A[j] ,将较小的赋值给B[k],相应的指针同时向后移动。如此反复,直到所有元素都处理完毕。最后把辅助数组 B 中排好序的元素复制到数组 A 中,如下图所示。

第1次比较时,A[i] = 4, A[j] = 2,将较小的元素 2 放入数组 B 中,j++,k++。

第2次比较时,A[i] = 4, A[j] = 6,将较小的元素 4 放入数组 B 中,i++,k++。

第3次比较时,A[i] = 9, A[j] = 6,将较小的元素 6 放入数组 B 中,j++,k++。

第4次比较时,A[i] = 9, A[j] = 18,将较小的元素 9 放入数组 B 中,i++,k++。

第5次比较时,A[i] = 15, A[j] = 18,将较小的元素 15 放入数组 B 中,i++,k++。

第6次比较时,A[i] = 24, A[j] = 18,将较小的元素 18 放入数组 B 中,j++,k++。

第7次比较时,A[i] = 24, A[j] = 20,将较小的元素 20 放入数组 B 中,j++,k++。

此时,j > high 的后半部分处理完毕,但前半部分还剩余元素,该怎么办?将剩余元素照搬到数组 B 就可以了。

完成合并后,需要把辅助数组 B 中的元素复制到原来数组 A 中。

2 合并排序

将序列分为两个子序列,然后对子序列进行递归排序,再把两个已排好序的子序列合并成一个有序序列。

四 算法实现

归并排序实战_实践求真知-CSDN博客

https://blog.csdn.net/chengqiuming/article/details/114706150

相关文章