(1)产生 1000 个伪随机数,并依次存储在一个数据文件中; (2)对此 1000 个伪随机数序列分别用冒泡排序、快速排序、希尔排序、 堆排序、归并排序方法进行排序,并比较它们的运行时间。
时间: 2024-02-17 11:05:15 浏览: 69
插入排序 冒泡法排序 快速排序 直接选择排序 堆排序 归并排序 希尔排序 7种排序算法及时间比较
5星 · 资源好评率100%
好的,可以使用Python内置的time模块来计算各种排序算法的运行时间,并将排序后的结果分别存储在不同的文件中。具体实现如下所示:
```python
import random
import time
# 产生1000个随机数,并保存到文件中
with open('data.txt', 'w') as f:
nums = [random.randint(1, 1000) for _ in range(1000)]
f.write('\n'.join(map(str, nums)))
# 冒泡排序
def bubble_sort(nums):
n = len(nums)
for i in range(n):
for j in range(0, n - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
# 快速排序
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[0]
left = [x for x in nums[1:] if x < pivot]
right = [x for x in nums[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# 希尔排序
def shell_sort(nums):
n = len(nums)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = nums[i]
j = i
while j >= gap and nums[j - gap] > temp:
nums[j] = nums[j - gap]
j -= gap
nums[j] = temp
gap //= 2
# 堆排序
def heap_sort(nums):
def heapify(nums, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and nums[l] > nums[largest]:
largest = l
if r < n and nums[r] > nums[largest]:
largest = r
if largest != i:
nums[i], nums[largest] = nums[largest], nums[i]
heapify(nums, n, largest)
n = len(nums)
for i in range(n // 2 - 1, -1, -1):
heapify(nums, n, i)
for i in range(n - 1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
heapify(nums, i, 0)
# 归并排序
def merge_sort(nums):
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = nums[:mid]
right = nums[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
# 读取数据文件中的随机数
with open('data.txt', 'r') as f:
nums = [int(x) for x in f.read().splitlines()]
# 冒泡排序
start_time = time.time()
bubble_sort(nums.copy())
end_time = time.time()
with open('bubble_sort.txt', 'w') as f:
f.write('\n'.join(map(str, nums)))
print('Bubble sort time:', end_time - start_time)
# 快速排序
start_time = time.time()
sorted_nums = quick_sort(nums.copy())
end_time = time.time()
with open('quick_sort.txt', 'w') as f:
f.write('\n'.join(map(str, sorted_nums)))
print('Quick sort time:', end_time - start_time)
# 希尔排序
start_time = time.time()
shell_sort(nums.copy())
end_time = time.time()
with open('shell_sort.txt', 'w') as f:
f.write('\n'.join(map(str, nums)))
print('Shell sort time:', end_time - start_time)
# 堆排序
start_time = time.time()
heap_sort(nums.copy())
end_time = time.time()
with open('heap_sort.txt', 'w') as f:
f.write('\n'.join(map(str, nums)))
print('Heap sort time:', end_time - start_time)
# 归并排序
start_time = time.time()
sorted_nums = merge_sort(nums.copy())
end_time = time.time()
with open('merge_sort.txt', 'w') as f:
f.write('\n'.join(map(str, sorted_nums)))
print('Merge sort time:', end_time - start_time)
```
在这个示例代码中,我们首先使用文件操作将1000个随机数保存到文件中,然后分别读取数据文件中的随机数,并使用各种排序算法进行排序。在排序过程中,我们使用Python内置的time模块来计算每种排序算法的运行时间,并将排序后的结果保存到不同的文件中。最后,我们打印每种排序算法的运行时间。
阅读全文