编写“SortCompareThree”程序以实现对插入排序、归并排序和快速排序三种算法的比较
时间: 2024-04-09 12:28:45 浏览: 16
当然,我可以帮你编写一个名为"SortCompare"的程序,用于比较插入排序、归并排序和快速排序三算法的性能。以下是一个示例实现:
```python
import random
import
def insertion_sort(arr):
for i in(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 merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
def quick_sort(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def generate_random_array(size):
return [random.randint(0, 1000) for _ in range(size)]
def measure_time(sort_func, arr):
start_time = time.time()
sort_func(arr)
end_time = time.time()
return end_time - start_time
def sort_compare_three(array_size):
arr = generate_random_array(array_size)
insertion_time = measure_time(insertion_sort, arr.copy())
merge_time = measure_time(merge_sort, arr.copy())
quick_time = measure_time(quick_sort, arr.copy(), 0, len(arr) - 1)
print(f"Array size: {array_size}")
print(f"Insertion Sort time: {insertion_time:.6f} seconds")
print(f"Merge Sort time: {merge_time:.6f} seconds")
print(f"Quick Sort time: {quick_time:.6f} seconds")
sort_compare_three(1000) # 用于测试的数组大小
```
这个程序会生成一个指定大小的随机数组,然后分别使用插入排序、归并排序和快速排序进行排序,并输出各个算法的执行时间。你可以根据需要调整测试的数组大小。请注意,这只是一个简单的示例,你可以根据自己的需求对程序进行扩展和优化。