归并排序 python代码

以下是归并排序的 Python 代码：

def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

def merge(left, right):
result = []
i = j =
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(merge_sort(arr))

相关问题

归并排序python代码

以下是归并排序的 Python 代码：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_arr = arr[:mid]
        right_arr = arr[mid:]

        merge_sort(left_arr)
        merge_sort(right_arr)

        i = j = k = 0

        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] < right_arr[j]:
                arr[k] = left_arr[i]
                i += 1
            else:
                arr[k] = right_arr[j]
                j += 1
            k += 1

        while i < len(left_arr):
            arr[k] = left_arr[i]
            i += 1
            k += 1

        while j < len(right_arr):
            arr[k] = right_arr[j]
            j += 1
            k += 1
    return arr

该算法先将数组分成两部分，然后递归地对左右两个部分进行归并排序，最后将两个有序的部分合并成一个有序的数组。时间复杂度为 O(nlogn)。

归并排序Python代码

### 回答1：

def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves

mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half

i = j = k = 0

# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+=1
else:
arr[k] = R[j]
j+=1
k+=1

# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i+=1
k+=1

while j < len(R):
arr[k] = R[j]
j+=1
k+=1答：实现归并排序的 Python 代码如下：def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2 # 找到数组中间
L = arr[:mid] # 将数组元素分成两半
R = arr[mid:] #

mergeSort(L) # 对第一半元素进行排序
mergeSort(R) # 对第二半元素进行排序

i = j = k = 0

# 将数据复制到临时数组 L[] 和 R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+=1
else:
arr[k] = R[j]
j+=1
k+=1

# 检查是否有任何元素遗留
while i < len(L):
arr[k] = L[i]
i+=1
k+=1

while j < len(R):
arr[k] = R[j]
j+=1
k+=1

### 回答2：
归并排序是一种分治排序算法。它将数组分成两个子数组，对每个子数组进行递归排序，然后将两个排好序的子数组合并成一个有序数组。下面是一个用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):
    merged_arr = []
    left_index, right_index = 0, 0
    
    while left_index < len(left_arr) and right_index < len(right_arr):
        if left_arr[left_index] < right_arr[right_index]:
            merged_arr.append(left_arr[left_index])
            left_index += 1
        else:
            merged_arr.append(right_arr[right_index])
            right_index += 1
    
    merged_arr += left_arr[left_index:]
    merged_arr += right_arr[right_index:]
    
    return merged_arr

# 测试代码
arr = [6, 5, 3, 1, 8, 7, 2, 4]
sorted_arr = merge_sort(arr)
print(sorted_arr)

以上代码中，首先定义了`merge_sort`函数，它接收一个数组作为参数，并将其分成两个子数组，然后对每个子数组进行递归排序。然后定义了`merge`函数，它用于将两个排好序的子数组合并成一个有序数组。最后，通过调用`merge_sort`函数对数组进行排序，并输出排序结果。

### 回答3：
归并排序是一种分治算法，它将一个大问题拆分为小问题，然后将小问题的解合并到一起得到最终的解。

以下是使用Python实现的归并排序代码：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

首先，定义了一个`merge_sort`函数，它接收一个待排序的列表`arr`作为参数，如果列表长度小于等于1，则直接返回。接着，找到列表的中间位置`mid`，将列表一分为二，并分别保存在变量`left`和`right`中。
然后，递归调用`merge_sort`函数对`left`和`right`进行排序，得到排好序的`left`和`right`。
最后，调用`merge`函数，将排好序的`left`和`right`列表合并成一个有序的结果列表。

`merge`函数用于将两个已排序的列表`left`和`right`合并成一个有序的结果列表。它使用两个指针`i`和`j`分别指向`left`和`right`的起始位置，通过比较指针所指向的元素的大小，将较小的元素添加到结果列表`result`中，并将对应的指针向后移动。在循环结束后，将剩余的元素添加到结果列表中。

这样，通过递归调用`merge_sort`函数和合并操作`merge`函数，归并排序可以将一个无序的列表排序成一个有序的列表。