快速排序算法的实现。任意输入20个整数,对这20个整数进行快速排序。要求使用末元素作为划分基准。
时间: 2024-04-30 19:23:27 浏览: 75
快速排序算法实现
快速排序是一种常用的排序算法,其基本思想是将一个数组划分成两个子数组,其中一个子数组的所有元素都小于另一个子数组的所有元素,然后递归地对子数组进行排序。
快速排序的实现需要选择一个基准元素,一般选择数组的第一个或最后一个元素作为基准元素。在实现中,我们选择末元素作为划分基准。
下面是使用 Python 实现快速排序算法的代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[-1]
left = []
right = []
for i in range(len(arr)-1):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
# 测试代码
arr = [5, 2, 8, 4, 9, 1, 3, 7, 6, 0, 11, 15, 19, 18, 12, 14, 17, 16, 10, 13]
sorted_arr = quick_sort(arr)
print(sorted_arr)
```
输出结果:
```
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
```
在这个实现中,我们首先检查数组的长度。如果长度小于等于 1,则直接返回数组。否则,我们选择末元素作为基准元素,将数组分成两个子数组,一个子数组中的元素都小于基准元素,另一个子数组中的元素都大于等于基准元素。然后递归地对子数组进行排序,并将结果合并起来。最后返回完全排序后的数组。
在测试代码中,我们任意输入了 20 个整数,并对这 20 个整数进行了快速排序。
阅读全文