首页 > 编程语言 > 详细

分治法 实现归并排序

时间:2018-11-02 23:06:46      阅读:194      评论:0      收藏:0      [点我收藏+]

分治法 实现归并排序

1 问题描述

  二路归并排序,不仔细详解了。之所以记录是因为被坑了, 详细看代码

2 python 实现

def merge(row_data, result_data, start, center, end):
    i = start
    j = center + 1
    k = start

    while i <= center and j <= end:
        if result_data[i] <= result_data[j]:
            row_data[k] = result_data[i]
            k = k + 1
            i = i + 1
        else:
            row_data[k] = result_data[j]
            k = k + 1
            j = j + 1
    if i <= center:
        while i <= center:
            row_data[k] = result_data[i]
            k = k + 1
            i = i + 1

    if j <= end:
        while j <= end:
            row_data[k] = result_data[j]
            k = k + 1
            j = j + 1
    print("合并结果")
    print(row_data)
    # result 的 值 也要改变; 如果不改变,下次 比较时,会出错;
    for x in range(start, end + 1):
        result_data[x] = row_data[x]   # row_data 是排序号的数据; 将排好序的数据 赋值给 result_data;


# row_data: 原始数据, result_data: 结果数据
def merge_sort(row_data, result_data, start, end):
    if start == end:
        result_data[start] = row_data[start]
    else:
        center = (start + end) // 2
        merge_sort(row_data, result_data, start, center)
        merge_sort(row_data, result_data, center+1, end)
        merge(row_data, result_data, start, center, end)


def test_data():
    data = [23, 13, 49, 6, 31, 19, 28]  # 数组是 引用;
    result = list(range(len(data)))
    print(result)
    merge_sort(data, result, 0, len(data)-1)
    print("运行结果")
    print("排序结果:")
    print(result)


test_data()

 

分治法 实现归并排序

原文:https://www.cnblogs.com/generalLi/p/9898581.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!