1.定义待排序表的长度为n。 2.初始化随机数发生器,产生n个随机数构成的顺序表。 3.创建输出排序表函数,取得系统时间函数,直接插入排序函数,冒泡排序函数,快速排序函数,直接选择排序函数,筛选函数,对排序函数,归并排序函数. 4.主程序调用各个排序函数,输出各排序算法对长度为n的顺序表进行排序所耗费的时间。
时间: 2023-12-10 16:38:18 浏览: 56
以下是示例代码:
```python
import random
import time
# 直接插入排序
def insert_sort(lst):
n = len(lst)
for i in range(1, n):
value = lst[i]
j = i - 1
while j >= 0 and lst[j] > value:
lst[j+1] = lst[j]
j -= 1
lst[j+1] = value
# 冒泡排序
def bubble_sort(lst):
n = len(lst)
for i in range(n-1):
for j in range(n-i-1):
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_index = i
for j in range(i+1, n):
if lst[j] < lst[min_index]:
min_index = j
if min_index != i:
lst[i], lst[min_index] = lst[min_index], lst[i]
# 筛选排序
def heap_sort(lst):
def heap_adjust(start, end):
root = start
while True:
child = root * 2 + 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
n = len(lst)
for i in range(n//2-1, -1, -1):
heap_adjust(i, n-1)
for i in range(n-1, 0, -1):
lst[0], lst[i] = lst[i], lst[0]
heap_adjust(0, i-1)
# 对排序
def shell_sort(lst):
n = len(lst)
gap = n // 2
while gap > 0:
for i in range(gap, n):
value = lst[i]
j = i - gap
while j >= 0 and lst[j] > value:
lst[j+gap] = lst[j]
j -= gap
lst[j+gap] = value
gap //= 2
# 归并排序
def merge_sort(lst):
def merge(left, right):
result = []
i = j = 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(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
# 输出排序表
def print_sort_table(lst):
print("排序前:", lst)
start_time = time.time()
insert_sort(lst.copy())
print("直接插入排序:", time.time() - start_time, "秒", lst)
start_time = time.time()
bubble_sort(lst.copy())
print("冒泡排序:", time.time() - start_time, "秒", lst)
start_time = time.time()
quick_sort(lst.copy())
print("快速排序:", time.time() - start_time, "秒", lst)
start_time = time.time()
select_sort(lst.copy())
print("直接选择排序:", time.time() - start_time, "秒", lst)
start_time = time.time()
heap_sort(lst.copy())
print("筛选排序:", time.time() - start_time, "秒", lst)
start_time = time.time()
shell_sort(lst.copy())
print("对排序:", time.time() - start_time, "秒", lst)
start_time = time.time()
merge_sort(lst.copy())
print("归并排序:", time.time() - start_time, "秒", lst)
# 主程序
if __name__ == "__main__":
n = int(input("请输入待排序表的长度:"))
random.seed(0)
lst = [random.randint(0, 10000) for _ in range(n)]
print_sort_table(lst)
```
该程序实现了对长度为n的随机数顺序表的直接插入排序、冒泡排序、快速排序、直接选择排序、筛选排序、对排序和归并排序,并输出了各排序算法对表进行排序所耗费的时间。用户可以根据需要修改排序函数或添加其他排序算法。
阅读全文