递归与分治法实现快速排序算法,输入一串以英文字符逗号隔开的数字,按升序排列法实现快速排序算法
时间: 2023-04-18 18:01:11 浏览: 151
采用递归分治算法写的快速排序
3星 · 编辑精心推荐
快速排序算法是一种基于递归和分治法的排序算法。它的基本思想是将一个序列分成两个子序列,其中一个子序列的所有元素都比另一个子序列的元素小,然后对这两个子序列分别进行排序,最后将它们合并起来。
具体实现时,我们可以选择一个元素作为基准值,将序列中小于基准值的元素放在左边,大于基准值的元素放在右边,然后递归地对左右两个子序列进行排序。
下面是一个使用递归和分治法实现快速排序算法的示例:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# 示例输入
input_str = "3,1,4,1,5,9,2,6,5,3,5"
input_list = [int(x) for x in input_str.split(",")]
# 输出排序结果
print(quick_sort(input_list))
```
以上代码将会输出 `[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]`,即输入的数字序列按升序排列的结果。
阅读全文