给我快速排序标杆选取,三轴排序,引入插排三种优化方式的代码
时间: 2024-10-23 09:19:42 浏览: 12
JAVA 冒泡法,选择法,插入法,快速排序法,实现代码
快速排序的标杆选取也叫“枢轴元素的选择”,有多种策略可以选择,比如:
```python
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = median_of_three(arr[0], arr[len(arr)//2], arr[-1]) # 使用三数取中法作为基准
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
```
这里`median_of_three`是一个函数,用于计算三个数的中位数作为基准。
三轴排序是一种混合排序策略,结合了快速排序和二路归并排序的优点,通过将数组划分为三部分进行排序,可以减少分区过程的不平衡,提高效率:
```python
def three_axis_sort(arr):
if len(arr) <= 10: # 当规模较小时,采用插入排序
return insertion_sort(arr)
low, mid, high = partition(arr, 0, len(arr) - 1)
return three_axis_sort(low) + three_axis_sort(mid) + three_axis_sort(high)
# ... 分区函数省略 ...
```
引入插排(插入排序)优化是在快速排序递归过程中,当子数组规模较小的时候,切换到插入排序,因为它对于小数组效率更高:
```python
def hybrid_quicksort(arr):
if len(arr) < 10: # 当规模小于这个阈值,插入排序更有效
return insertion_sort(arr)
pivot, less, greater = partition(arr)
return hybrid_quicksort(less) + [pivot] + hybrid_quicksort(greater)
# ... 分区函数省略 ...
```
阅读全文