用Python编写一个实验程序,采用快速排序完成一个整数序列的递增排序,要求输出每次划分结果,并用相关数据进行测试。
时间: 2023-07-18 07:24:49 浏览: 75
好的,下面是Python代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print("Original array:", arr)
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
```
运行结果如下:
```
Original array: [9, 8, 7, 6, 5, 4, 3, 2, 1]
Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
```
为了输出每次划分结果,可以对快速排序算法进行一些修改,加入一些打印语句,如下所示:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
print("Pivot:", pivot)
print("Left partition:", left)
print("Right partition:", right)
return quick_sort(left) + [pivot] + quick_sort(right)
arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print("Original array:", arr)
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
```
运行结果如下:
```
Original array: [9, 8, 7, 6, 5, 4, 3, 2, 1]
Pivot: 9
Left partition: [8, 7, 6, 5, 4, 3, 2, 1]
Right partition: []
Pivot: 8
Left partition: [7, 6, 5, 4, 3, 2, 1]
Right partition: []
Pivot: 7
Left partition: [6, 5, 4, 3, 2, 1]
Right partition: []
Pivot: 6
Left partition: [5, 4, 3, 2, 1]
Right partition: []
Pivot: 5
Left partition: [4, 3, 2, 1]
Right partition: []
Pivot: 4
Left partition: [3, 2, 1]
Right partition: []
Pivot: 3
Left partition: [2, 1]
Right partition: []
Pivot: 2
Left partition: [1]
Right partition: []
Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
```
可以看到,每次划分的结果都被打印出来了。
阅读全文