以最后一个数作为基准点的数组进行快速排序法过程演算
时间: 2023-06-17 14:08:36 浏览: 46
假设我们有以下数组需要进行快速排序:
```
[5, 9, 3, 7, 6, 8, 1, 2, 4]
```
我们选择最后一个数 `4` 作为基准点,然后开始排序过程:
1. 初始化左右指针 `left` 和 `right`,分别指向数组的第一个和最后一个元素。
```
left = 0
right = len(arr) - 1
```
2. 接下来,我们需要找到第一个比基准点大的数和第一个比基准点小的数,并交换它们的位置。
```
while left < right:
while left < right and arr[left] <= arr[right]:
right -= 1
if left < right:
arr[left], arr[right] = arr[right], arr[left]
while left < right and arr[left] <= arr[right]:
left += 1
if left < right:
arr[left], arr[right] = arr[right], arr[left]
```
经过第一次交换后,数组变成了:
```
[2, 9, 3, 7, 6, 8, 1, 5, 4]
```
3. 接着,我们将基准点和中间位置的数交换位置。
```
arr[left], arr[right] = arr[right], arr[left]
```
此时,数组变成了:
```
[2, 4, 3, 1, 6, 8, 9, 5, 7]
```
4. 然后,我们对基准点左侧的子数组和右侧的子数组分别递归进行快速排序。
```
quick_sort(arr, 0, left-1) # 左侧子数组
quick_sort(arr, left+1, right) # 右侧子数组
```
经过多次交换和递归,最终数组变成了有序数组:
```
[1, 2, 3, 4, 5, 6, 7, 8, 9]
```
完整的代码实现如下:
```python
def quick_sort(arr, left, right):
if left < right:
# 选择最后一个数作为基准点
pivot = arr[right]
i, j = left, right
while i < j:
while i < j and arr[i] <= pivot:
i += 1
while i < j and arr[j] >= pivot:
j -= 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
arr[i], arr[right] = arr[right], arr[i]
# 对左侧子数组和右侧子数组分别递归进行快速排序
quick_sort(arr, left, i-1)
quick_sort(arr, i+1, right)
return arr
arr = [5, 9, 3, 7, 6, 8, 1, 2, 4]
print(quick_sort(arr, 0, len(arr)-1))
```