[数据结构 -- 手撕排序算法第六篇] 递归实现快速排序（集霍尔版本，挖坑法，前后指针法为一篇的实现方法，很能打）

**数据结构 -- 手撕排序算法第六篇**

**递归实现快速排序（集霍尔版本）**

快速排序是一种非常常见的排序算法，它通过分治法将待排序序列分成两个子序列，然后分别对这两个子序列进行排序，最终合并得到有序序列。快速排序的平均时间复杂度为 O(n log n)，是最快的稳定性较低的排序算法之一。

在本篇中，我们将使用递归实现快速排序，具体来说，我们将使用集霍尔版本（也称为挖坑法）的方法来实现快速排序。这个方法通过在原数组中创建一个空洞（或称为"坑"），然后分别对左边和右边的元素进行排序，最终填充这个空洞。

**递归实现快速排序**

def quick_sort(arr):
 """
 递归实现快速排序 :param arr: 待排序数组 :return: 排序后的数组 """
 if len(arr) <=1:
 # 如果数组长度小于或等于1，则直接返回数组（因为它已经是有序的）
 return arr else:
 #选择一个基准元素（在本例中，我们使用第一个元素作为基准）
 pivot = arr[0]
 # 将所有小于基准元素的元素放入左边列表中 left = [x for x in arr[1:] if x <= pivot]
 # 将所有大于基准元素的元素放入右边列表中 right = [x for x in arr[1:] if x > pivot]
 # 递归地对左边和右边的元素进行排序 return quick_sort(left) + [pivot] + quick_sort(right)

# 测试快速排序函数arr = [5,2,8,3,1,6,4]
print("原始数组：", arr)
sorted_arr = quick_sort(arr)
print("排序后的数组：", sorted_arr)

原始数组： [5,2,8,3,1,6,4]
排序后的数组： [1,2,3,4,5,6,8]