编写快速排序函数,实现对给定的数组 vec 从下标 start 到 finish 之间的元素进行排序。
时间: 2024-02-05 21:10:58 浏览: 89
排序代码(C语言),快速排序,冒泡排序,归并排序等等
下面是一个简单的快速排序函数的实现:
```python
def quick_sort(vec, start, finish):
if start >= finish:
return
pivot = vec[start]
left = start + 1
right = finish
while left <= right:
while left <= finish and vec[left] < pivot:
left += 1
while right >= start and vec[right] > pivot:
right -= 1
if left <= right:
vec[left], vec[right] = vec[right], vec[left]
left += 1
right -= 1
vec[start], vec[right] = vec[right], vec[start]
quick_sort(vec, start, right - 1)
quick_sort(vec, right + 1, finish)
```
该函数使用递归的方式实现快速排序。首先选择一个基准元素(这里选择数组的第一个元素),然后将数组划分为两个部分,其中左边的部分都小于基准元素,右边的部分都大于基准元素。接着,对左、右两部分分别进行递归排序,最终得到一个有序的数组。
在上述代码中,我们使用了两个指针 left 和 right 分别指向数组的左右两端,然后不断地向中间移动,直到 left 和 right 相遇。在移动的过程中,如果左指针指向的元素小于基准元素,就将左指针向右移动;如果右指针指向的元素大于基准元素,就将右指针向左移动。当左右指针相遇时,说明所有的元素都已经被处理过了,此时将基准元素放到合适的位置上,并将数组分成左右两部分,然后对左右两部分分别进行递归排序即可。
使用该函数,可以对任意大小、任意类型的数组进行快速排序。例如,对一个整数数组进行排序的代码如下:
```python
vec = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
quick_sort(vec, 0, len(vec) - 1)
print(vec)
```
输出结果为:
```
[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
```
阅读全文