快速排序（Quick Sort）是一种高效的排序算法，采用分治法策略。以下是快速排序的三种常见实现方式（经典、双指针优化、三数取中优化）以及非递归实现。

1. 经典快速排序实现

经典快速排序选择一个基准元素（pivot），然后将数组划分为两部分：小于基准的部分和大于基准的部分，递归排序两部分。

```python
def quicksortclassic(arr):
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 quicksortclassic(left) + [pivot] + quicksortclassic(right)

示例

arr = [3, 6, 8, 10, 1, 2, 1]
print(quicksortclassic(arr))
```

2. 双指针优化（原地排序）

通过双指针法，在数组内部完成分区，避免创建新的子数组，从而节省空间。

```python
def quicksortinplace(arr, low, high):
if low < high:
pivotindex = partition(arr, low, high)
quicksortinplace(arr, low, pivotindex - 1)
quicksortinplace(arr, pivotindex + 1, high)

def partition(arr, low, high):
pivot = arr[high] # 选择最后一个元素作为基准
i = low - 1 # i是小于pivot的区域的最后一个元素的索引
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] # 将pivot放到正确位置
return i + 1

示例

arr = [3, 6, 8, 10, 1, 2, 1]
quicksortin_place(arr, 0, len(arr) - 1)
print(arr)
```

3. 三数取中优化

通过选择数组首、尾、中间三个数的中位数作为基准，减少因基准选择不当导致的性能退化。

```python
def quicksortmedianofthree(arr, low, high):
if low < high:
pivotindex = medianofthreepartition(arr, low, high)
quicksortmedianofthree(arr, low, pivotindex - 1)
quicksortmedianofthree(arr, pivotindex + 1, high)

def medianofthreepartition(arr, low, high):
mid = (low + high) // 2
# 三数取中，将中位数放到high-1位置
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
# 使用high-1作为pivot（避免high被覆盖）
pivot = arr[mid]
arr[mid], arr[high - 1] = arr[high - 1], arr[mid]
return partitionwith_pivot(arr, low, high - 1) # 调用普通分区函数

def partitionwithpivot(arr, low, high):
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

示例（需要调整，因为三数取中逻辑较复杂，这里简化调用方式）

完整实现需要调整medianofthree_partition调用方式

```

4. 非递归实现（使用栈模拟递归）

通过显式栈来模拟递归调用，避免函数调用的开销。

```python
def quicksortnonrecursive(arr):
stack = [(0, len(arr) - 1)] # 栈中存储待处理的区间
while stack:
low, high = stack.pop()
if low < high:
pivotindex = partition(arr, low, high) # 使用前面定义的partition函数
stack.append((low, pivotindex - 1)) # 左区间
stack.append((pivotindex + 1, high)) # 右区间

def partition(arr, low, high):
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