时间戳

首页 > 解决方案 > 为什么在归并排序算法中需要递归

python - 为什么在归并排序算法中需要递归

问题描述

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

def printList(arr): 
    for i in range(len(arr)):         
        print(arr[i], end = " ") 
    print() 
 

if __name__ == '__main__': 
     arr = [12, 11, 13, 5, 6, 7]  
     print("Given array is", end = "\n")  
     printList(arr) 
     mergeSort(arr) 
     print("Sorted array is: ", end = "\n") 
     printList(arr)

在上面的代码中使用mergeSort(L)和有什么意义，mergeSort(R)即使你删除了这个递归，我们也可以获得排序列表。那为什么这是必要的？上面的代码直接取自geeks for geeks，而且我在许多其他地方也看到了合并排序中的这种递归。使用它有什么意义。

另一个问题是：如何在没有任何语句的情况下mergeSort(L)甚至返回任何内容，因为它只是失败并且当长度为 < 1 时什么也不返回。mergeSort(R)returnarr

标签： pythonalgorithmsortingmergesort

解决方案

没有递归的 mergeSort 函数不对数组进行排序，它只是合并（因此得名）应该已经排序的两半。这就是为什么在合并两者之前需要在数组的每一半上调用函数的原因。

此外，mergeSort 不会返回任何内容，它只是对数组进行排序，并且不会对长度小于 1 的数组执行任何操作，因为这样就没有要排序的元素了。

推荐阅读