编写一个实验程序,采用快速排序完成一个整数序列的递增排序,要求输出每次划分结果,并用相关数据进行测试。python代码实现
时间: 2024-03-01 13:49:45 浏览: 68
好的,下面是基于Python的快速排序实验程序,代码如下:
```python
def quick_sort(arr, left, right):
if left < right:
pivot = partition(arr, left, right)
print(arr)
quick_sort(arr, left, pivot - 1)
quick_sort(arr, pivot + 1, right)
def partition(arr, left, right):
pivot = arr[left]
while left < right:
while left < right and arr[right] >= pivot:
right -= 1
arr[left] = arr[right]
while left < right and arr[left] <= pivot:
left += 1
arr[right] = arr[left]
arr[left] = pivot
return left
arr = [6, 8, 1, 4, 3, 9, 5, 2, 7]
quick_sort(arr, 0, len(arr) - 1)
print(arr)
```
这里我们定义了两个函数:`quick_sort` 和 `partition`。其中,`quick_sort` 函数用于递归调用 `partition` 函数,实现快速排序。`partition` 函数则是实现了快速排序中的划分操作。
在 `quick_sort` 函数中,我们首先调用 `partition` 函数进行划分,并输出每次划分后的结果。然后,我们将左半部分和右半部分分别递归调用 `quick_sort` 函数,直到排序完成。
在 `partition` 函数中,我们首先选择第一个元素作为枢轴元素 `pivot`,然后从右往左寻找第一个小于 `pivot` 的元素,再从左往右寻找第一个大于 `pivot` 的元素,最后将这两个元素交换。不断重复这个过程,直到左右指针相遇,最后将枢轴元素 `pivot` 放到正确的位置上,返回其下标。
最后,我们定义了一个整数序列 `arr`,并调用 `quick_sort` 函数对其进行排序,并输出排序后的结果。
你可以根据需要修改排序序列 `arr`,并运行程序进行测试。
阅读全文