快排实现
时间: 2023-12-10 21:42:09 浏览: 33
快速排序(QuickSort)是一种常用的排序算法,基本思想是通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后再按此方法对这两部分记录继续进行排序,以达到整个序列有序。
以下是基于递归实现的快速排序示例代码:
```python
def quick_sort(arr):
if len(arr) <= 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) # 对左右两边再次进行快排,最终合并结果
```
另外,快速排序还有一种基于循环实现的方式,称为“三向切分快速排序”。这种方式的优点是在处理含有大量重复元素的数组时具有更好的性能。以下是示例代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
lt, eq, gt = [], [], [] # 分别存放小于、等于、大于基准值的数
pivot = arr[len(arr) // 2]
for x in arr:
if x < pivot:
lt.append(x)
elif x == pivot:
eq.append(x)
else:
gt.append(x)
return quick_sort(lt) + eq + quick_sort(gt)
```
以上两种实现方式在大多数情况下都能够快速高效地排序一个数组。