用python编写程序产生30000个随机整数,用蛮力法进行选择排序和冒泡排序,用归治法进行归并排序和快速排序,用减治法进行插入排序和堆排序;输出递增结果;统计每一种排序运行所花费的时间。
时间: 2024-05-01 11:21:58 浏览: 94
好的,我理解了你的要求。以下是 Python 代码实现:
```python
import random
import time
# 产生30000个随机整数
nums = [random.randint(1, 100000) for _ in range(30000)]
# 蛮力法 - 选择排序
def selection_sort(nums):
n = len(nums)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if nums[j] < nums[min_idx]:
min_idx = j
nums[i], nums[min_idx] = nums[min_idx], nums[i]
# 蛮力法 - 冒泡排序
def bubble_sort(nums):
n = len(nums)
for i in range(n):
for j in range(n-i-1):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
# 归治法 - 归并排序
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
res = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res += left[i:]
res += right[j:]
return res
# 归治法 - 快速排序
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 insertion_sort(nums):
n = len(nums)
for i in range(1, n):
j = i
while j > 0 and nums[j] < nums[j-1]:
nums[j], nums[j-1] = nums[j-1], nums[j]
j -= 1
# 减治法 - 堆排序
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)
# 统计每种排序运行所花费的时间
start = time.time()
selection_sort(nums)
end = time.time()
print("选择排序所花费的时间:", end-start, "秒")
start = time.time()
bubble_sort(nums)
end = time.time()
print("冒泡排序所花费的时间:", end-start, "秒")
start = time.time()
merge_sort(nums)
end = time.time()
print("归并排序所花费的时间:", end-start, "秒")
start = time.time()
quick_sort(nums)
end = time.time()
print("快速排序所花费的时间:", end-start, "秒")
start = time.time()
insertion_sort(nums)
end = time.time()
print("插入排序所花费的时间:", end-start, "秒")
start = time.time()
heap_sort(nums)
end = time.time()
print("堆排序所花费的时间:", end-start, "秒")
# 输出递增结果
print(nums)
```
希望能够帮到你!
阅读全文