用python实现归并排序详解--MYTOP

用python实现归并排序详解

归并排序：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
2.1 算法描述
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
 
 
归并排序的时间复杂度和稳定性
归并排序时间复杂度
归并排序的时间复杂度是O(n㏒n)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n㏒n)。
归并排序稳定性
归并排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
python代码实现归并排序：
 
  
   #归并排序
def merge_sort(data):
     if len(data) <= 1:
         return data
     mid = len(data)//2
     left = data[:mid]
     right = data[mid:]
     left = merge_sort(left)
     right = merge_sort(right)
     return merge(left,right)

def merge(left, right):
     ll,rr = 0,0
     result = []
     while ll < len(left) and rr < len(right):
        if left[ll] < right[rr]:
            result.append(left[ll])
            ll +=1
        else:
            result.append(right[rr])
            rr +=1
         result+=left[ll:]
         result+=right[rr:]
         return result
tesl=[1,3,45,23,23,12,43,45,33,21]
print(merge_sort(tesl))
 
  
 
 