设计一个测试程序,比较内部排序算法的关键字比较次数和移动次数以取得直观感受。
时间: 2023-12-20 14:04:51 浏览: 26
好的,以下是一个简单的测试程序,可以比较冒泡排序、插入排序、选择排序、快速排序等内部排序算法的关键字比较次数和移动次数:
```python
import random
import time
# 冒泡排序
def bubbleSort(arr):
n = len(arr)
compare_count = 0
swap_count = 0
for i in range(n):
for j in range(n-i-1):
compare_count += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swap_count += 1
return compare_count, swap_count
# 插入排序
def insertionSort(arr):
n = len(arr)
compare_count = 0
swap_count = 0
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
compare_count += 1
arr[j+1] = arr[j]
swap_count += 1
j -= 1
compare_count += 1
arr[j+1] = key
swap_count += 1
return compare_count, swap_count
# 选择排序
def selectionSort(arr):
n = len(arr)
compare_count = 0
swap_count = 0
for i in range(n):
min_idx = i
for j in range(i+1, n):
compare_count += 1
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
swap_count += 1
return compare_count, swap_count
# 快速排序
def quickSort(arr):
compare_count = 0
swap_count = 0
def partition(arr, low, high):
nonlocal compare_count, swap_count
i = low - 1
pivot = arr[high]
for j in range(low, high):
compare_count += 1
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
swap_count += 1
arr[i+1], arr[high] = arr[high], arr[i+1]
swap_count += 1
return i + 1
def quickSortHelper(arr, low, high):
nonlocal compare_count, swap_count
if low < high:
pi = partition(arr, low, high)
quickSortHelper(arr, low, pi-1)
quickSortHelper(arr, pi+1, high)
quickSortHelper(arr, 0, len(arr)-1)
return compare_count, swap_count
# 测试函数
def testSortAlgorithm(sort_func, arr):
start_time = time.time()
compare_count, swap_count = sort_func(arr)
end_time = time.time()
print(f"排序算法:{sort_func.__name__}")
print(f"排序前的数组:{arr}")
print(f"排序后的数组:{arr}")
print(f"关键字比较次数:{compare_count}")
print(f"移动次数:{swap_count}")
print(f"运行时间:{end_time - start_time:.6f}s")
print("==============================")
# 生成随机数组
arr = [random.randint(1, 100) for _ in range(10)]
# 测试冒泡排序
testSortAlgorithm(bubbleSort, arr.copy())
# 测试插入排序
testSortAlgorithm(insertionSort, arr.copy())
# 测试选择排序
testSortAlgorithm(selectionSort, arr.copy())
# 测试快速排序
testSortAlgorithm(quickSort, arr.copy())
```
该程序首先生成一个长度为10的随机数组,然后依次测试冒泡排序、插入排序、选择排序和快速排序算法,并输出它们的关键字比较次数、移动次数和运行时间。您可以根据需要自行修改数组长度和排序算法。