＜数据结构＞NO10.快速排序|递归|非递归|优化

**快速排序**

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

**快速排序的优点**

1. **平均时间复杂度**: O(n log n)
2. **空间复杂度**: O(log n)（由于递归调用栈）
3. **稳定性**: 不稳定**快速排序的缺点**

1. **最坏情况下的时间复杂度**: O(n^2)，当数据已经有序时，基准值选择不合理时。
2. **额外空间需求**: 递归调用栈会占用一定的内存。

### 递归实现

def quick_sort(arr):
 """
 递归快速排序函数 :param arr: 需要排序的数组 :return: 排序后的数组 """
 if len(arr) <=1:
 # 如果数组长度小于或等于1，直接返回（因为已经有序）
 return arr pivot = arr[len(arr) //2]
 #选择基准值为中间值 left = [x for x in arr if x < pivot]
 # 将小于基准值的元素放入左子集 middle = [x for x in arr if x == pivot]
 # 将等于基准值的元素放入中间子集 right = [x for x in arr if x > pivot]
 # 将大于基准值的元素放入右子集 return quick_sort(left) + middle + quick_sort(right)
# 递归函数，返回排序后的数组

def quick_sort_non_recursive(arr):
 """
 非递归快速排序函数 :param arr: 需要排序的数组 :return: 排序后的数组 """
 if len(arr) <=1:
 # 如果数组长度小于或等于1，直接返回（因为已经有序）
 return arr stack = [(0, len(arr) -1)]
 # 初始化栈，存储起始和结束索引 while stack:
 start, end = stack.pop()
 # 弹出栈顶元素，获取当前子集的起始和结束索引 if start < end:
 pivot_index = partition(arr, start, end)
 # 将基准值放置在正确位置，并返回其索引 stack.append((start, pivot_index -1))
 # 将左子集压入栈中 stack.append((pivot_index +1, end))
 # 将右子集压入栈中 return arrdef partition(arr, low, high):
 """
 分区函数，将基准值放置在正确位置 :param arr: 需要排序的数组 :param low: 子集起始索引 :param high: 子集结束索引 :return: 基准值索引 """
 pivot = arr[high]
 #选择基准值为子集最后一个元素 i = low -1 # 初始化小于基准值的索引 for j in range(low, high):
 if arr[j] < pivot:
 i +=1 # 如果当前元素小于基准值，交换它们，并更新小于基准值的索引 arr[i], arr[j] = arr[j], arr[i]

 arr[i +1], arr[high] = arr[high], arr[i +1]
 # 将基准值放置在正确位置 return i +1# 分区函数，返回基准值索引

def quick_sort_optimized(arr):
 """
优化快速排序函数 :param arr: 需要排序的数组 :return: 排序后的数组 """
 if len(arr) <=1:
 # 如果数组长度小于或等于1，直接返回（因为已经有序）
 return arr stack = [(0, len(arr) -1)]
 # 初始化栈，存储起始和结束索引 while stack:
 start, end = stack.pop()
 # 弹出栈顶元素，获取当前子集的起始和结束索引 if start < end:
 pivot_index = partition(arr, start, end)
 # 将基准值放置在正确位置，并返回其索引 stack.append((start, pivot_index -1))
 # 将左子集压入栈中 stack.append((pivot_index +1, end))
 # 将右子集压入栈中 return arrdef partition_optimized(arr, low, high):
 """
优化分区函数，将基准值放置在正确位置 :param arr: 需要排序的数组 :param low: 子集起始索引 :param high: 子集结束索引 :return: 基准值索引 """
 pivot = arr[high]
 #选择基准值为子集最后一个元素 i = low -1 # 初始化小于基准值的索引 for j in range(low, high):
 if arr[j] < pivot:
 i +=1 # 如果当前元素小于基准值，交换它们，并更新小于基准值的索引 arr[i], arr[j] = arr[j], arr[i]

 arr[i +1], arr[high] = arr[high], arr[i +1]
 # 将基准值放置在正确位置 return i +1#优化分区函数，返回基准值索引

import randomdef test_quick_sort():
 """
 测试快速排序函数 :return: None """
 arr = [random.randint(0,100) for _ in range(10)]
 #生成一个随机数组 print("原始数组：", arr)
 # 输出原始数组 sorted_arr = quick_sort(arr)
 # 使用快速排序函数对数组进行排序 print("排序后的数组：", sorted_arr)
 # 输出排序后的数组def test_quick_sort_non_recursive():
 """
 测试非递归快速排序函数 :return: None """
 arr = [random.randint(0,100) for _ in range(10)]
 #生成一个随机数组 print("原始数组：", arr)
 # 输出原始数组 sorted_arr = quick_sort_non_recursive(arr)
 # 使用非递归快速排序函数对数组进行排序 print("排序后的数组：", sorted_arr)
 # 输出排序后的数组def test_quick_sort_optimized():
 """
 测试优化快速排序函数 :return: None """
 arr = [random.randint(0,100) for _ in range(10)]
 #生成一个随机数组 print("原始数组：", arr)
 # 输出原始数组 sorted_arr = quick_sort_optimized(arr)
 # 使用优化快速排序函数对数组进行排序 print("排序后的数组：", sorted_arr)
 # 输出排序后的数组test_quick_sort()
# 测试快速排序函数test_quick_sort_non_recursive()
# 测试非递归快速排序函数test_quick_sort_optimized()
# 测试优化快速排序函数