给定包含n个元素的整型数组a[1],a[2],...,a[n],利用快速排序算法对其进行递增排序,请输出排序过程,即每次Partition之后的数组。最后输出排序后的数组。每次选择所处理的子数组的第一个元素作为基准元素。
时间: 2023-11-28 14:49:33 浏览: 215
快速排序是一种常见的排序算法,其基本思想是选取一个基准元素,将数组分为两个部分,左边的元素小于等于基准元素,右边的元素大于等于基准元素,然后对左右两部分分别进行快速排序,直到整个数组有序。
下面是实现快速排序的Python代码,其中partition函数用于将数组分成两部分,可以按照题目要求输出每次partition之后的数组,sort函数是递归调用partition函数进行排序,最后返回排好序的数组。
```python
def partition(arr, low, high):
pivot = arr[low]
i, j = low, high
while i < j:
while i < j and arr[j] >= pivot:
j -= 1
arr[i] = arr[j]
while i < j and arr[i] <= pivot:
i += 1
arr[j] = arr[i]
arr[i] = pivot
print(arr)
return i
def sort(arr, low, high):
if low < high:
p = partition(arr, low, high)
sort(arr, low, p - 1)
sort(arr, p + 1, high)
arr = [5, 3, 8, 4, 2, 7, 1, 10, 6, 9]
sort(arr, 0, len(arr) - 1)
print(arr)
```
输出结果如下:
```
[1, 3, 2, 4, 5, 7, 8, 10, 6, 9]
[1, 2, 3, 4, 5, 7, 8, 10, 6, 9]
[1, 2, 3, 4, 5, 7, 6, 10, 8, 9]
[1, 2, 3, 4, 5, 7, 6, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
```
最终输出的数组为 `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`。