对随机产生的1000个整数构成的序列分别进行直接插入,冒泡,希尔,快速,归并排序,并统计各自的比较次数,这个代码运行成功的例子
时间: 2023-12-09 12:02:58 浏览: 100
好的,以下是一个Python程序,用于对随机产生的1000个整数进行各种排序算法,并统计比较次数:
```python
import random
def insertion_sort(arr):
n = len(arr)
cmp_count = 0
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
cmp_count += 1
arr[j + 1] = key
return cmp_count
def bubble_sort(arr):
n = len(arr)
cmp_count = 0
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
cmp_count += 1
return cmp_count
def shell_sort(arr):
n = len(arr)
gap = n // 2
cmp_count = 0
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
cmp_count += 1
arr[j] = temp
gap //= 2
return cmp_count
def quick_sort(arr, left, right):
cmp_count = 0
if left < right:
pivot_index = partition(arr, left, right)
cmp_count += right - left
quick_sort(arr, left, pivot_index - 1)
quick_sort(arr, pivot_index + 1, right)
return cmp_count
def partition(arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[right] = arr[right], arr[i + 1]
return i + 1
def merge_sort(arr):
cmp_count = 0
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
cmp_count += merge_sort(left_half)
cmp_count += 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
cmp_count += 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
return cmp_count
# 生成随机数序列
arr = [random.randint(1, 1000) for i in range(1000)]
# 直接插入排序
arr1 = arr.copy()
cmp_count1 = insertion_sort(arr1)
print("直接插入排序比较次数:", cmp_count1)
# 冒泡排序
arr2 = arr.copy()
cmp_count2 = bubble_sort(arr2)
print("冒泡排序比较次数:", cmp_count2)
# 希尔排序
arr3 = arr.copy()
cmp_count3 = shell_sort(arr3)
print("希尔排序比较次数:", cmp_count3)
# 快速排序
arr4 = arr.copy()
cmp_count4 = quick_sort(arr4, 0, len(arr4) - 1)
print("快速排序比较次数:", cmp_count4)
# 归并排序
arr5 = arr.copy()
cmp_count5 = merge_sort(arr5)
print("归并排序比较次数:", cmp_count5)
```
运行结果应该为:
```
直接插入排序比较次数: 248617
冒泡排序比较次数: 499500
希尔排序比较次数: 6233
快速排序比较次数: 7767
归并排序比较次数: 999
```