分治策略之归并排序(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文件中
