可以使用快速排序或者归并排序求解问题{5,0,3,8,89,45,66,12,35}在dev中
时间: 2024-10-20 20:03:47 浏览: 29
c语言实现排序算法,快速排序,归并排序
快速排序和归并排序都是高效的排序算法,可以用来解决将列表{5,0,3,8,89,45,66,12,35}这样的整数数组按升序排列的问题。
**快速排序**(Quick Sort)是一种分而治之的策略,基本步骤是选择一个“基准”元素,将数组分为两部分,一部分的所有元素都比基准小,另一部分所有元素都比基准大,然后递归地对这两部分进行排序。在这个例子中,你可以选择第一个元素(如5),通过一趟比较交换,把小于5的元素放在左边,大于等于5的元素放在右边,然后分别对左右两边的子数组进行同样的操作。
**归并排序**(Merge Sort)则是先将数组一分为二,然后对每个子数组再进行划分,直到子数组只有一个元素,最后合并有序的子数组成整体。对于给定数组,从中间分成两个子数组,递归地排序每个子数组,然后合并这两个已排序的子数组。
以下是这两种排序算法在Python中的简单实现:
```python
# 快速排序示例
def quicksort(arr):
if len(arr) <= 1:
return arr
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)
# 归并排序示例
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
return merge(left, right)
# 合并两个已排序的数组
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left if left else right)
return result
# 使用任一函数对数组进行排序
arr = [5, 0, 3, 8, 89, 45, 66, 12, 35]
sorted_arr = quicksort(arr) or mergesort(arr)
print(sorted_arr)
```
运行上述代码后,你会得到一个已排序的数组。
阅读全文