随机产生10000个数据,进行起泡排序、快速排序、希尔排序、堆排序、基数排序,并比较各种算法的排序时间。
时间: 2023-08-21 09:03:37 浏览: 83
好的,我可以帮助你回答这个问题。首先,我们需要定义一个函数来随机生成10000个数据:
```python
import random
def generate_data():
data = []
for i in range(10000):
data.append(random.randint(1, 10000))
return data
```
接下来,我们可以定义一个函数来测试各种排序算法的时间:
```python
import time
def test_sorting_algorithms():
data = generate_data()
# Bubble Sort
start_time = time.time()
bubble_sort(data)
end_time = time.time()
bubble_sort_time = end_time - start_time
# Quick Sort
start_time = time.time()
quick_sort(data)
end_time = time.time()
quick_sort_time = end_time - start_time
# Shell Sort
start_time = time.time()
shell_sort(data)
end_time = time.time()
shell_sort_time = end_time - start_time
# Heap Sort
start_time = time.time()
heap_sort(data)
end_time = time.time()
heap_sort_time = end_time - start_time
# Radix Sort
start_time = time.time()
radix_sort(data)
end_time = time.time()
radix_sort_time = end_time - start_time
# Print results
print("Bubble Sort Time: {}".format(bubble_sort_time))
print("Quick Sort Time: {}".format(quick_sort_time))
print("Shell Sort Time: {}".format(shell_sort_time))
print("Heap Sort Time: {}".format(heap_sort_time))
print("Radix Sort Time: {}".format(radix_sort_time))
```
注意,这里我们调用了以下五种排序算法:起泡排序、快速排序、希尔排序、堆排序和基数排序。这些算法的实现可以参考以下代码:
```python
# Bubble Sort
def bubble_sort(data):
n = len(data)
for i in range(n):
for j in range(0, n-i-1):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
# Quick Sort
def quick_sort(data):
if len(data) <= 1:
return data
pivot = data[0]
left = []
right = []
for i in range(1, len(data)):
if data[i] < pivot:
left.append(data[i])
else:
right.append(data[i])
return quick_sort(left) + [pivot] + quick_sort(right)
# Shell Sort
def shell_sort(data):
n = len(data)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = data[i]
j = i
while j >= gap and data[j-gap] > temp:
data[j] = data[j-gap]
j -= gap
data[j] = temp
gap //= 2
# Heap Sort
def heap_sort(data):
def heapify(data, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and data[i] < data[l]:
largest = l
if r < n and data[largest] < data[r]:
largest = r
if largest != i:
data[i],data[largest] = data[largest],data[i]
heapify(data, n, largest)
n = len(data)
for i in range(n//2 - 1, -1, -1):
heapify(data, n, i)
for i in range(n-1, 0, -1):
data[i], data[0] = data[0], data[i]
heapify(data, i, 0)
# Radix Sort
def radix_sort(data):
def counting_sort(data, exp1):
n = len(data)
output = [0] * (n)
count = [0] * (10)
for i in range(0, n):
index = data[i] // exp1
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = data[i] // exp1
output[count[index % 10] - 1] = data[i]
count[index % 10] -= 1
i -= 1
i = 0
for i in range(0, len(data)):
data[i] = output[i]
max1 = max(data)
exp = 1
while max1 // exp > 0:
counting_sort(data, exp)
exp *= 10
```
最后,我们只需要调用 `test_sorting_algorithms()` 函数即可测试各种排序算法的时间。
阅读全文