合并排序python
时间: 2023-07-01 07:11:05 浏览: 46
合并排序(Merge Sort)是一种基于分治思想的排序算法,其基本思想是将待排序序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。
下面是Python实现合并排序的代码:
```
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_arr = arr[:mid]
right_arr = arr[mid:]
left_arr = merge_sort(left_arr)
right_arr = merge_sort(right_arr)
return merge(left_arr, right_arr)
def merge(left_arr, right_arr):
i = 0
j = 0
merged_arr = []
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
merged_arr.append(left_arr[i])
i += 1
else:
merged_arr.append(right_arr[j])
j += 1
merged_arr += left_arr[i:]
merged_arr += right_arr[j:]
return merged_arr
```
首先,我们将待排序序列分成两个子序列(左子序列和右子序列),然后递归地对左子序列和右子序列分别进行排序,最终将它们合并成一个有序的序列。
在合并过程中,我们用两个指针 i 和 j 分别指向左子序列和右子序列的第一个元素,比较它们的大小,将较小的元素添加到合并后的序列中,然后将指针向后移动一位。这样重复执行,直到其中一个子序列遍历完毕,将另一个子序列中剩余的元素添加到合并后的序列中,最终得到有序序列。
可以通过调用 `merge_sort` 函数来对待排序的序列进行排序,例如:
```
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr)
```
输出结果为:
```
[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
```