admin 管理员组文章数量: 887021
2024年1月27日发(作者：migrant workers)
快速排序算法的代码实现
快速排序是一种常见的排序算法，其时间复杂度为O（nlogn），在大多数排序场合都可以胜任。它的思路是：先确定一个基准值，然后根据基准值，将数组分为两部分，一部分是小于基准值的，另一部分是大于基准值的。再对这两部分分别递归地用同样的方法进行排序，最终达到整个数组有序的目的。下面将介绍快速排序的代码实现。
1. 快速排序的基本形式
快速排序算法的基本形式类似于二分查找，它的思路是：先选择数组中的一个数作为基准值，将比它小的数放在基准值左边，比它大的数放在基准值右边。然后将数组分成两部分，分别对这两部分进行递归。最后将所有的子数组合并起来。
代码实现如下：
```python
def quicksort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0] # 以第一个元素作为基准值
less = [i for i in arr[1:] if i <= pivot] # 小于等于基准值的数组部分
greater = [i for i in arr[1:] if i > pivot] # 大于基准值的数组部分
return quicksort(less) + [pivot] + quicksort(greater)
```
2. 快速排序的优化
上述代码实现虽然简单，但是在处理大数组时会出现时间复杂度较高的情况。原因在于每次递归都会开辟新的数组空间，同时容易出现数组顺序不稳定的情况。
为了优化快速排序算法，有以下几个方案：
（1）随机选择基准值
在每次递归时，随机从数组中选择一个元素作为基准值，这样可以增加程序的随机性，从而达到更好的排序效果。代码实现如下：
```python
import random
def quicksort(arr):
if len(arr) < 2:
return arr
else:
pivot = (arr) # 选择随机数作为基准值
less = [i for i in arr[1:] if i <= pivot] # 小于等于基准值的数组部分
greater = [i for i in arr[1:] if i > pivot] # 大于基准值的数组部分
return quicksort(less) + [pivot] + quicksort(greater)
```
（2）三数取中法
三数取中法是指在选择基准值时，取数组中的左端、右端和中间三个数，然后将这三个数排序，将排在中间的数字作为基准值。这样可以减少程序的波动性，从而达到更好的排序效果。代码实现如下：
```python
def quicksort(arr, left, right):
if left >= right:
return
mid = partition(arr, left, right)
quicksort(arr, left, mid - 1)
quicksort(arr, mid + 1, right)
def partition(arr, left, right):
# 三数取中法
mid = (left + right) // 2
if arr[left] > arr[right]:
arr[left], arr[right] = arr[right], arr[left]
if arr[mid] > arr[right]:
arr[mid], arr[right] = arr[right], arr[mid]
if arr[left] < arr[mid]:
arr[left], arr[mid] = arr[mid], arr[left]
pivot = arr[left] # 取左端元素作为基准值
while left < right:
while left < right and arr[right] >= pivot:
right -= 1
arr[left] = arr[right]
while left < right and arr[left] <= pivot:
left += 1
arr[right] = arr[left]
arr[left] = pivot
return left
```
（3）插入排序优化
当数组的规模比较小时，可以使用插入排序来代替快速排序。这样可以减少递归过程中新建数组的开销，从而提高排序效率。代码实现如下：
```python
def quicksort(arr, left, right):
if left >= right:
return
if right - left <= 5: # 当数组规模小于5时，使用插入排序
insert_sort(arr, left, right)
else:
mid = partition(arr, left, right)
quicksort(arr, left, mid - 1)
quicksort(arr, mid + 1, right)
def partition(arr, left, right):
# 三数取中法
mid = (left + right) // 2
if arr[left] > arr[right]:
arr[left], arr[right] = arr[right], arr[left]
if arr[mid] > arr[right]:
arr[mid], arr[right] = arr[right], arr[mid]
if arr[left] < arr[mid]:
arr[left], arr[mid] = arr[mid], arr[left]
pivot = arr[left] # 取左端元素作为基准值
while left < right:
while left < right and arr[right] >= pivot:
right -= 1
arr[left] = arr[right]
while left < right and arr[left] <= pivot:
left += 1
arr[right] = arr[left]
arr[left] = pivot
return left
def insert_sort(arr, left, right):
for i in range(left + 1, right + 1):
key = arr[i]
j = i - 1
while j >= left and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
```
总结：
从上述代码实现来看，快速排序算法是一种非常高效的排序算法，在实际应用中被广泛使用。我们可以根据实际情况灵活选择优化措施，以达到更好的排序效果。
版权声明：本文标题：快速排序算法的代码实现 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1706344108h505606.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论