东软睿道老师直接接听

400-029-09** 400-029-0997 转 199128
查看完整号码
扫码拨号
微信扫码拨号

详解Java八大经典内排序算法——归并排序

2023/12/29 17:51:37

详解Java八大经典内排序算法——归并排序

 今天我们来介绍下一位朋友，归并排序！

归并排序

-排序思路

      归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。简单的归并排序是直接将两个有序的子表合并成一个有序的表即二路归并。

      将 Data[0..n-1] 看成是 n 个长度为 1 的有序序列，然后进行两两归并，得到 [n/2] 个长度为 2（最后一个有序序列的长度可能为 1）的有序序列，再进行两两归并，得到 [n/4] 个长度为 4（最后一个有序序列的长度可能小于 4）的有序序列，…… ，直到得到一个长度为 n 的有序序列。

※说明：归并排序每趟产生的有序区只是局部有序的，也就是说在最后一趟排序结束前，所有元素并不一定归位了。

归并排序

-排序实例

      设待排序的表有 10 个元素，其关键字为 {18,2,20,34,12,32,6,16}。以下为归并排序的排序过程：

     采用二路归并排序时，需要进行 3 趟归并排序，其过程如图5.1所示。第 1 趟将每两个各含有一个元素的子表归并成一个新表，如将 {18} 和 {2} 排好序变为 {2,18}。第 2 趟将每两个各含有两个元素的子表归并成一个新表，如将 {2,18} 和 {20,34} 归并为{2,18,20,34}。  

      第 3 趟将每两个各含有 4 个元素的子表归并成一个新表，产生最终有序表。

归并排序

-算法分析

时间复杂度：O(nlog2n)；

空间复杂度：O(n)；

稳定性：稳定；

复杂性：较复杂。


“沈阳东软睿道实训”是沈阳东软育道教育服务有限公司在教育宝平台开设的店铺，若该店铺内信息涉嫌虚假或违法，请点击这里向教育宝反馈，我们将及时进行处理。

机构评分

环境：4.0师资：4.0服务：4.0效果：4.0

公示信息

店铺名称：沈阳东软睿道实训

单位名称：沈阳东软育道教育服务有限公司

账号名称：drrdjyfwyxgs（131******21）

所属城市：辽宁沈阳

入驻时长：13年

在线客服：在线聊

相关课程

微信咨询

返回顶部