1.定义待排序表的长度为n。 2.初始化随机数发生器,产生n个随机数构成的顺序表。 3.创建输出排序表函数,取得系统时间函数,直接插入排序函数,冒泡排序函数,快速排序函数,直接选择排序函数,筛选函数,对排序函数,归并排序函数。 4.主程序调用各个排序函数,输出各排序算法对长度为n的顺序表进行排序所耗费的时间。
时间: 2024-02-03 11:15:34 浏览: 54
以下是一个示例代码实现:
```python
import random
import time
# 直接插入排序
def insert_sort(lst):
n = len(lst)
for i in range(1, n):
j = i - 1
key = lst[i]
while j >= 0 and lst[j] > key:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
# 冒泡排序
def bubble_sort(lst):
n = len(lst)
for i in range(n - 1):
for j in range(n - 1 - i):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
# 快速排序
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[0]
left = [x for x in lst[1:] if x < pivot]
right = [x for x in lst[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# 直接选择排序
def select_sort(lst):
n = len(lst)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if lst[j] < lst[min_idx]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
# 筛选排序
def heap_sort(lst):
def sift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 <= end and lst[child] < lst[child + 1]:
child += 1
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child
else:
break
for start in range((len(lst) - 2) // 2, -1, -1):
sift_down(start, len(lst) - 1)
for end in range(len(lst) - 1, 0, -1):
lst[0], lst[end] = lst[end], lst[0]
sift_down(0, end - 1)
# 对排序
def shell_sort(lst):
n = len(lst)
gap = n // 2
while gap > 0:
for i in range(gap, n):
j = i
while j >= gap and lst[j - gap] > lst[j]:
lst[j - gap], lst[j] = lst[j], lst[j - gap]
j -= gap
gap //= 2
# 归并排序
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
def merge(left, right):
res = []
i, j = 0, 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 print_sort_time(lst):
start_time = time.time()
insert_sort(lst.copy())
end_time = time.time()
print("直接插入排序时间:", end_time - start_time)
start_time = time.time()
bubble_sort(lst.copy())
end_time = time.time()
print("冒泡排序时间:", end_time - start_time)
start_time = time.time()
quick_sort(lst.copy())
end_time = time.time()
print("快速排序时间:", end_time - start_time)
start_time = time.time()
select_sort(lst.copy())
end_time = time.time()
print("直接选择排序时间:", end_time - start_time)
start_time = time.time()
heap_sort(lst.copy())
end_time = time.time()
print("筛选排序时间:", end_time - start_time)
start_time = time.time()
shell_sort(lst.copy())
end_time = time.time()
print("对排序时间:", end_time - start_time)
start_time = time.time()
merge_sort(lst.copy())
end_time = time.time()
print("归并排序时间:", end_time - start_time)
# 主程序
if __name__ == '__main__':
n = 10000
lst = [random.randint(0, 10000) for _ in range(n)]
print_sort_time(lst)
```
以上代码中,我们随机生成了一个长度为n的待排序表,然后依次调用各个排序算法,并输出排序算法所耗费的时间。如果你想测试不同长度的待排序表,只需修改n的值即可。
阅读全文