现在有多种排序算法,包括冒泡、选择、插入、希尔、归并、快速及堆排序共7种排序算法,请使用python语言对1000以内的一定随机数进行排序,随机数的个数是这样定义的,如你的学号是:20214075109,则生成的随机数个数为20+21+40+75+109=265,即对1000以内的265个随机数进行排序,同时使用柱状图完成排序的动画演示。
时间: 2024-03-27 13:38:14 浏览: 63
七种排序算法(包括直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,归并排序)
5星 · 资源好评率100%
好的,我可以帮你实现这个任务。首先,我定义一个函数来生成指定数量的随机数:
```python
import random
def generate_random_numbers(num):
numbers = []
for i in range(num):
numbers.append(random.randint(1, 1000))
return numbers
```
接下来,我定义一个函数来实现冒泡排序:
```python
def bubble_sort(numbers):
n = len(numbers)
for i in range(n):
for j in range(0, n-i-1):
if numbers[j] > numbers[j+1]:
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
return numbers
```
然后,我定义一个函数来实现选择排序:
```python
def selection_sort(numbers):
n = len(numbers)
for i in range(n):
min_index = i
for j in range(i+1, n):
if numbers[j] < numbers[min_index]:
min_index = j
numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
return numbers
```
接下来,我定义一个函数来实现插入排序:
```python
def insertion_sort(numbers):
n = len(numbers)
for i in range(1, n):
key = numbers[i]
j = i - 1
while j >= 0 and key < numbers[j]:
numbers[j+1] = numbers[j]
j -= 1
numbers[j+1] = key
return numbers
```
然后,我定义一个函数来实现希尔排序:
```python
def shell_sort(numbers):
n = len(numbers)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = numbers[i]
j = i
while j >= gap and numbers[j-gap] > temp:
numbers[j] = numbers[j-gap]
j -= gap
numbers[j] = temp
gap //= 2
return numbers
```
接下来,我定义一个函数来实现归并排序:
```python
def merge_sort(numbers):
if len(numbers) > 1:
mid = len(numbers) // 2
left_half = numbers[:mid]
right_half = numbers[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]:
numbers[k] = left_half[i]
i += 1
else:
numbers[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
numbers[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
numbers[k] = right_half[j]
j += 1
k += 1
return numbers
```
然后,我定义一个函数来实现快速排序:
```python
def quick_sort(numbers):
if len(numbers) <= 1:
return numbers
else:
pivot = numbers[0]
less_than_pivot = [x for x in numbers[1:] if x <= pivot]
greater_than_pivot = [x for x in numbers[1:] if x > pivot]
return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)
```
最后,我定义一个函数来实现堆排序:
```python
def heapify(numbers, n, i):
largest = i
left_child = 2 * i + 1
right_child = 2 * i + 2
if left_child < n and numbers[left_child] > numbers[largest]:
largest = left_child
if right_child < n and numbers[right_child] > numbers[largest]:
largest = right_child
if largest != i:
numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heap_sort(numbers):
n = len(numbers)
for i in range(n // 2 - 1, -1, -1):
heapify(numbers, n, i)
for i in range(n - 1, 0, -1):
numbers[i], numbers[0] = numbers[0], numbers[i]
heapify(numbers, i, 0)
return numbers
```
现在,我们可以使用上述函数来对随机数进行排序,并且使用matplotlib库来实现排序的动画演示:
```python
import matplotlib.pyplot as plt
import matplotlib.animation as animation
num = 265
numbers = generate_random_numbers(num)
fig, ax = plt.subplots()
ax.set_xlim(0, len(numbers))
ax.set_ylim(0, 1000)
bars = ax.bar(range(len(numbers)), numbers)
sort_functions = [bubble_sort, selection_sort, insertion_sort, shell_sort, merge_sort, quick_sort, heap_sort]
def update(func):
global numbers
numbers = func(numbers)
for i, rect in enumerate(bars):
rect.set_height(numbers[i])
return bars
ani = animation.FuncAnimation(fig, update, frames=sort_functions, repeat=False)
plt.show()
```
运行上述代码,你就可以看到排序的动画演示了。
阅读全文