1.实现合并排序算法。要排序的整型数组元素可以用随机数生成器生成,运行程序,分别记录对十万,一百万,一千万,五千万个数据排序所用的时间,列出表格显示统计出来的时间。并单独显示一个100个数据的排序结果。
时间: 2024-03-14 07:45:20 浏览: 67
好的,我理解了你的问题。下面是使用 Python 实现合并排序算法的代码:
```python
import random
import time
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
def main():
sizes = [100000, 1000000, 10000000, 50000000]
for size in sizes:
arr = [random.randint(-10000, 10000) for _ in range(size)]
start_time = time.time()
merge_sort(arr)
end_time = time.time()
print(f"Size: {size}, Time: {end_time - start_time}")
arr = [random.randint(-10000, 10000) for _ in range(100)]
print(f"Original Array: {arr}")
merge_sort(arr)
print(f"Sorted Array: {arr}")
if __name__ == "__main__":
main()
```
这个代码会生成一个包含不同数量的随机整数的数组,并使用 `time` 模块记录排序算法的运行时间。最后,它会输出排序所需的时间,以及排序结果。
你可以在你的本地机器上运行这个代码,并用 Excel 或其他类似的工具来创建一个表格来显示排序所需的时间。
阅读全文