chatGTP给出的python版快速排序
def quick_sort(arr):
"""
快速排序函数:对给定的数组 arr 进行原地排序
:param arr: 待排数组
:return: 原地排序后的数组 arr
"""
_quick_sort_helper(arr, 0, len(arr) - 1)
return arr
def _quick_sort_helper(arr, start, end):
if start < end:
# 将数组划分成两部分,并返回中间点索引 pivot_index
pivot_index = _partition(arr, start, end)
# 对左边部分进行递归排序
_quick_sort_helper(arr, start, pivot_index - 1)
# 对右边部分进行递归排序
_quick_sort_helper(arr, pivot_index + 1, end)
def _partition(arr, start, end):
"""
划分数组函数:按照 pivot_value 将数组划分成左右两部分,并返回 pivot_index 中间点索引
:param arr: 待排数组
:param start: 数组起始索引
:param end: 数组结束索引
:return: pivot_index 中间点索引
"""
# 取右端点作为枢轴值 pivot_value
pivot_value = arr[end]
# 初始化中间点索引 pivot_index 和游标 i
pivot_index = start
for i in range(start, end):
# 如果当前值小于等于 pivot_value,则交换到 pivot_index 处
if arr[i] <= pivot_value:
arr[i], arr[pivot_index] = arr[pivot_index], arr[i]
# 中间点索引加一,扩大左半部分
pivot_index += 1
# 最后交换中间点和枢轴位置的值
arr[pivot_index], arr[end] = arr[end], arr[pivot_index]
# 返回中间点索引
return pivot_index
# 测试用例
print(quick_sort([5, 3, 4, 1, 2])) # [1, 2, 3, 4, 5]
print(quick_sort([0, 0, 0, 0])) # [0, 0, 0, 0]
print(quick_sort([9, 8, 7, 6, 5, 4, 3, 2, 1])) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
以上是一个简单的快速排序实现程序。该程序使用递归算法实现、原地排序、选择最右端点作为基准元素(pivot),并利用双指针将待排数组分成左右两部分来进行划分和排序。在每次遍历过程中,如果当前值小于等于基准元素,就将其交换到左侧部分,并将中间点索引加一。最后再交换中间点与基准元素的位置,返回中间点索引即为划分后的位置。
测试用例包括了常见的升序、相等和逆序的情况,这些测试用例能够检测快速排序算法的性能和正确性。