【数据结构算法】：Python实现归并排序

小咪咪 2022-05-16 00:38 255阅读 0赞

### 动图展示 ###

算法时间复杂度o(n\*logn)  
![849589-20171015230557043-37375010.gif][]

### python ###

归并的思路在于先分再和，分的过程如下：  
先将数组进行一半一半的拆分，直到不能再拆分未知。

![742678-20161104134542080-1593140807.png][]

之后进行合并的操作，这个合并的操作主要是合并另个有序数组。我们先比较两个有序数组的第一个元素，将小的放到一个空数组中，然后将这个小的数据原始所在的那个数组的指针往后移一个。继续与另一个数组进行比较，继续将小的放到空数组的下一个中。直到任何一个数组全部的元素出完之后，将另一个数组的所有元素放到空数组接下来的位置。

def merge(left_arr, right_arr);
        empty = []
        left_index = right_index = 0
        #当两个数组都有元素的时候
        while left_index < len(left_arr) and right_index < len(right_arr):
            if left_arr[left_index] < right_arr[right_index]:
                empty.append(left_arr[left_index])
                left_index += 1
            else:
                empty.append(right_arr[right_index])
                right_index+= 1
    
        #当left数组的元素归并完了
        if left_index == len(left_arr):
            for num in right_arr[right_index:]:
                empty.append(num)
    
        #当right数组的元素归并完了
        else:
            for num in left_arr[left_index:]:
            empty.append(num)
    
    def merge_sort(arr):
        if len(arr)<=1:
            return arr
        middle_index = len(arr)/2
        left_arr = merge_sort(arr[:middle_index])
        right_arr = merge_sort(arr[middle_index:])
        return merge(left_arr, right_arr)
    
    
    if __name__ == '__main__':
        arr = [1,3,5,7,9,2,8,0,-1,-2]
        output = merge_sort(arr)
        print output

[849589-20171015230557043-37375010.gif]: /images/20220516/b804593dbe6848e38928c07a5716de6b.png
[742678-20161104134542080-1593140807.png]: /images/20220516/90dc76f532014f029afb777362a12c65.png