专栏首页猿计划分治策略之归并排序(Python实现)

分治策略之归并排序(Python实现)

一、 实验目的及任务

用分治法解决数组排序

二、 实验环境

c++或java

三、 问题描述

Input : 一个数组

Output:自小到大排列的数组

四、 编程任务

对于一个数组,用分治法的思想将其按照从小到大排列。

五、 数据输入

随机产生1000以上的数据,放入输入文件input.txt

六、 结果输出

比如数组 A ={3, 41, 52, 26, 38, 57, 9, 49},输出为{3,9,26,38,41,49.51,57}。

七、 实验报告内容

程序主要代码

import math
import ioTool

#合并
def merge(A, B, s):
    Aindex = 0 #A下标
    Bindex = 0 #B下标
    while Aindex + Bindex < len(s):
        #如果
        if Bindex == len(B) or (Aindex<len(A) and A[Aindex] > B[Bindex]):
            s[Aindex+Bindex] = A[Aindex]
            Aindex = Aindex + 1
        else:
            s[Aindex+Bindex] = B[Bindex]
            Bindex = Bindex + 1
    return s

#拆分
num = 0
def merge_soft(s):
    global  num
    n = len(s)
    #1、如果到了第1个了,或者没有就直接返回,不用排序了
    if n == 1:
        return
    #2、拆分
    mid = math.floor(n/2) #向上取整获取中间值  或者n//2可以拿到除数的整数
    A = s[0:mid]  #把0到mid的数据分到
    B = s[mid:n]  #后半部分
    merge_soft(A)
    merge_soft(B)
    # print("第:",num,"次,拆分了A", A)
    # print("第:", num, "次,拆分了B", B)
    num = num + 1
    # print("拆分了B", B)
    #3、合并
    arr =  merge(A,B,s)
    return arr

if __name__ == '__main__':
    #随机生成数据并存放在input.txt文件中
    # ioTool.randomData(1100000,-5000,182000,"input1.txt");
    #读取数据
    # s = ioTool.readLine("input1.txt");
    s = [12,5,1,9,-11]  #课本测试数据
    arr = merge_soft(s)
    ioTool.writeLine(arr,"output1.txt")
    print("排序结果:",arr)

测试结果:

正在打开 output1.txt 文件
结果写入 output1.txt 文件完毕
排序结果: [12, 9, 5, 1, -11]

ioTool.py文件

import random

#随机生成数
def randomData(n,x,y,addressURL):
    # 打开input文件
    file = open(addressURL, 'w', encoding='utf8');
    print("正在随机生成数据,写入",addressURL,"文件")
    # 产生10万个数据,从0到100000
    i = 0;
    while i < n:
        file.write(str(random.randint(x, y))+"\n")
        i = i + 1;
    file.close()
    print("写入",addressURL,"文件完毕")

#打开input.txt文件   读取文件  返回一个[]
def readLine(addressURL):
    # 行数
    count_line = 0;
    # 定义存储的元组
    arr1 = []
    file = open(addressURL, 'r', encoding='utf8')
    for line in file.read().splitlines():
        arr1.append(int(line))
        count_line = 1 + count_line  # 计算行数
    file.close()
    return arr1

#写入文件
def writeLine(A,addressURL):
    # 打开input文件
    file = open(addressURL, 'w', encoding='utf8')
    print("正在打开",addressURL,"文件")
    i = 0
    while i < len(A):
        file.write(str(A[i]) + "\n")
        i = i + 1
    file.close()
    print("结果写入",addressURL,"文件完毕")

解释

本程序所定义的方法等: #合并 merge(A, B, s) #拆分 merge_soft(s)

#程序入口 if name == ‘main’:

#随机生成数 randomData(n,x,y,addressURL): #打开input.txt文件 读取文件 返回一个[] readLine(addressURL): #写入文件 writeLine(A,addressURL):

1)定义并实现读写文件的方法 读文件方法:readLine(addressURL) 参数addressURL 指的是要读取的文件的地址

写文件方法:writeLine(A,addressURL) 参数A:排序好的数组 参数addressURL:把排序号的数组写如到那个地址下的文件中 2)定义并实现生成随机数的方法 随机生成数据:randomData(n,x,y,addressURL) 参数n:生成n个数 参数x,y:生成n个数的范围 参数addressURL:生成完后,要保存到哪里

3)定义并实现读取文件中的数据的方法 打开addressURL文件 读取文件 返回一个[]:readLine(addressURL) 参数addressURL:要读取的文件 返回值:number数组 4)拆分方法 #拆分 传过来的是一个数组 merge_soft(s) 5)合并方法 #合并,把A和B进行合并,s位置 merge(A, B, s)

实验结果

结果1:使用测试数据:[12,5,1,9,-11]进行排序

结果2:随机生成1100000个数字,从-5000到182000,存入到input1.txt文件中

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 实验四--数据库的安全性、完整性控制

    TrueDei
  • Mybatis中#{}与${}的区别

    总结: 也就是说使用#{}时,mybatis会自动加上引号。如果不想让加那么就使用${}

    TrueDei
  • Linux-远程拷贝(scp命令)

    TrueDei
  • 利用python-cdo处理气象数据

    如果你不喜欢命令行的操作方式,那么你可以尝试使用python-cdo,利用python脚本语言的优势来处理气象数据。命令行的方式有其优势,比如简单易操作,可扩展...

    bugsuse
  • TransactionScope 之分布式配置

    本文转载:http://blog.csdn.net/iwteih/article/details/4483372

    跟着阿笨一起玩NET
  • 移动端常用数据库

    程序员不务正业
  • 高效编排有状态应用——TiDB 的云原生实践与思考

    云原生时代以降,无状态应用以其天生的可替换性率先成为各类编排系统的宠儿。以 Kubernetes 为代表的编排系统能够充分利用云上的可编程基础设施,实现无状态应...

    PingCAP
  • 小编要失业了:奥运会报道已经用上机器人

    机器人写新闻也不是什么新鲜事了,在这次的里约奥运会上,《华盛顿邮报》就派出了专业的机器人团队进行报道。这支团队会在《华盛顿邮报》官网和Twitter上发布新闻,...

    机器人网
  • 面试题:能否讲讲Redis是如何做到高可用的?

    sentinel,中文名是哨兵。哨兵是 redis 集群机构中非常重要的一个组件,主要有以下功能:

    用户1263954
  • 苹果处理器的代工厂,为什么不把技术偷偷卖给同行? | 拔刺

    镁客网

扫码关注云+社区

领取腾讯云代金券