现在有多种排序算法,包括冒泡、选择、插入、希尔、归并、快速及堆排序共7种排序算法,请使用python语言对1000以内的270个随机数进行排序,同时使用柱状图完成排序的动画演示。
时间: 2024-01-27 17:06:28 浏览: 24
好的,我可以帮你实现。为了完成排序动画演示,我们需要使用matplotlib库。以下是代码实现:
```python
import random
import matplotlib.pyplot as plt
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
yield arr
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
yield arr
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i-1
while j >=0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
yield arr
def shell_sort(arr):
n = len(arr)
gap = n//2
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
arr[j] = temp
yield arr
gap //= 2
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
yield arr
def quick_sort(arr, low, high):
if low < high:
partition_index = partition(arr, low, high)
yield arr
yield from quick_sort(arr, low, partition_index - 1)
yield from quick_sort(arr, partition_index + 1, high)
def partition(arr, low, high):
i = low - 1
pivot = arr[high]
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 heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
yield arr
yield from heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n//2 - 1, -1, -1):
yield from heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
yield arr
yield from heapify(arr, i, 0)
def visualize_sorting(algo_name, arr):
fig, ax = plt.subplots()
ax.set_title(algo_name)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
ax.set_xlim(0, len(arr))
ax.set_ylim(0, int(1.07 * max(arr)))
text = ax.text(0.02, 0.95, "", transform=ax.transAxes)
iteration = [0]
def update_fig(arr, rects, iteration):
for rect, val in zip(rects, arr):
rect.set_height(val)
iteration[0] += 1
text.set_text("# of operations: {}".format(iteration[0]))
if algo_name == "Bubble Sort":
generator = bubble_sort(arr)
elif algo_name == "Selection Sort":
generator = selection_sort(arr)
elif algo_name == "Insertion Sort":
generator = insertion_sort(arr)
elif algo_name == "Shell Sort":
generator = shell_sort(arr)
elif algo_name == "Merge Sort":
generator = merge_sort(arr)
elif algo_name == "Quick Sort":
generator = quick_sort(arr, 0, len(arr)-1)
else:
generator = heap_sort(arr)
plt.show(block=False)
for i in generator:
update_fig(i, bar_rects, iteration)
plt.pause(0.1)
plt.close()
if __name__ == "__main__":
arr = [random.randint(0, 1000) for _ in range(270)]
visualize_sorting("Bubble Sort", arr)
visualize_sorting("Selection Sort", arr)
visualize_sorting("Insertion Sort", arr)
visualize_sorting("Shell Sort", arr)
visualize_sorting("Merge Sort", arr)
visualize_sorting("Quick Sort", arr)
visualize_sorting("Heap Sort", arr)
```
这个程序会生成一个随机数列表,然后分别用冒泡、选择、插入、希尔、归并、快速及堆排序算法对其进行排序,并将排序过程进行动画演示,每次演示都会生成一个柱状图,用于展示当前排序状态。