1.定义待排序表的长度为n。 2.初始化随机数发生器,产生n个随机数构成的顺序表。 3.创建输出排序表函数,取得系统时间函数,直接插入排序函数,冒泡排序函数,快速排序函数,直接选择排序函数,筛选函数,对排序函数,归并排序函数。 4.主程序调用各个排序函数,输出各排序算法对长度为n的顺序表进行排序所耗费的时间。
时间: 2024-01-22 22:19:48 浏览: 52
以下是一个示例的 Python 代码,实现了上述排序算法的比较:
```python
import random
import time
# 直接插入排序
def insert_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# 冒泡排序
def bubble_sort(arr):
for i in range(len(arr) - 1):
for j in range(len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# 快速排序
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# 直接选择排序
def select_sort(arr):
for i in range(len(arr) - 1):
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
# 堆排序
def heap_sort(arr):
def heapify(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
if arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
break
for start in range((len(arr) - 2) // 2, -1, -1):
heapify(start, len(arr) - 1)
for end in range(len(arr) - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
heapify(0, end - 1)
# 归并排序
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
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.extend(left[i:])
result.extend(right[j:])
return result
# 生成随机数组
def generate_arr(n):
return [random.randint(1, n) for _ in range(n)]
# 输出排序表函数
def print_sort_time(sort_func, arr):
start_time = time.time()
sort_func(arr)
end_time = time.time()
print(f"{sort_func.__name__.capitalize()}: {end_time - start_time:.8f}s")
if __name__ == '__main__':
n = 1000
arr = generate_arr(n)
print(f"Length of array: {n}")
print_sort_time(insert_sort, arr.copy())
print_sort_time(bubble_sort, arr.copy())
print_sort_time(quick_sort, arr.copy())
print_sort_time(select_sort, arr.copy())
print_sort_time(heap_sort, arr.copy())
print_sort_time(merge_sort, arr.copy())
```
在这个示例代码中,我们定义了生成随机数组和输出排序时间的函数,然后调用了各个排序算法对随机数组进行排序,并输出了各个排序算法所花费的时间。你可以根据自己的需求和实际情况,调整代码中的参数和算法选择。
阅读全文