快速排序递归实现和非递归实现（详解）

**快速排序算法**

快速排序是一种常见的排序算法，属于分治类算法。它通过选择一个基准值，将数据集分成两个子集：小于基准值的元素和大于基准值的元素，然后递归地对这两个子集进行排序。

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

### 递归函数

def quick_sort(arr):
 """
 快速排序递归实现 :param arr: 需要排序的数组 :return: 排序后的数组 """
 # 如果数组长度小于1，直接返回，因为已经是有序的了 if len(arr) < 1:
 return arr #选择基准值（本例中为第一个元素）
 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,9,6,3,1,8,4,7]
print(quick_sort(arr)) # 输出：[1,2,3,4,5,6,7,8,9]

def quick_sort_non_recursive(arr):
 """
 快速排序非递归实现 :param arr: 需要排序的数组 :return: 排序后的数组 """
 # 如果数组长度小于1，直接返回，因为已经是有序的了 if len(arr) < 1:
 return arr # 初始化栈 stack = []
 # 将数组和下标压入栈中 stack.append((arr,0))
 while stack:
 # 取出栈顶元素 arr, low = stack.pop()
 # 如果子数组长度小于1，直接返回，因为已经是有序的了 if len(arr) < 2:
 return arr #选择基准值（本例中为第一个元素）
 pivot = arr[0]
 # 将大于基准值的元素放在右边，小于基准值的元素放在左边 left = [x for x in arr[1:] if x <= pivot]
 right = [x for x in arr[1:] if x > pivot]
 # 将左右两个子集压入栈中 stack.append((left,0))
 stack.append((right,0))
 return []

arr = [5,2,9,6,3,1,8,4,7]
print(quick_sort_non_recursive(arr)) # 输出：[1,2,3,4,5,6,7,8,9]