python 快速排序书写逻辑
时间: 2023-11-01 20:59:34 浏览: 40
快速排序(Quick Sort)是一种常用的排序算法,其基本思想是通过选择一个元素作为基准(通常选择第一个元素),将数组分割为两部分,使得左边的元素都小于等于基准值,右边的元素都大于等于基准值,然后递归地对左右两部分进行排序。
下面是Python快速排序的实现逻辑:
1. 定义一个函数 quicksort,接受一个数组参数 arr 和两个整数参数 low、high 分别表示待排序部分的起始索引和结束索引。
2. 在函数内部,首先判断如果 low 大于等于 high,则说明待排序部分只有一个元素或者为空,直接返回。
3. 否则,选择数组的第一个元素 arr[low] 作为基准值。
4. 定义两个指针 i 和 j,分别指向待排序部分的起始位置和结束位置。
5. 从 j 开始向前遍历,直到找到一个小于等于基准值的元素,将其与 arr[i] 交换,并更新指针 i。
6. 从 i 开始向后遍历,直到找到一个大于等于基准值的元素,将其与 arr[j] 交换,并更新指针 j。
7. 重复步骤 5 和步骤 6,直到 i 和 j 相遇。
8. 将基准值 arr[low] 与 arr[j] 交换,此时基准值的位置已经确定。
9. 递归地对基准值左边的部分(即 arr[low:j-1])和右边的部分(即 arr[j+1:high])进行排序,调用 quicksort 函数。
10. 完成排序后,返回排序后的数组。
以下是快速排序的Python代码实现:
```python
def quicksort(arr, low, high):
if low >= high:
return
pivot = arr[low]
i = low
j = 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
quicksort(arr, low, i-1)
quicksort(arr, i+1, high)
return arr
# 示例
arr = [4, 2, 7, 1, 3]
sorted_arr = quicksort(arr, 0, len(arr)-1)
print(sorted_arr)
```