归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表。

流程

  1. # 如数据  [1,5,3,7,2,6,4,8]
  2. # 开始分割：
  3. """
  4.        [1,5,3,7] | [2,6,4,8]
  5.        [1,5]|[3,7] | [2,6] | [4,8]
  6.        [1] | [5] | [3] | [7] |  [2] |  [6] |  [4] |  [8]
  7. 开始合并:
  8.        [1,5] [3,7] [2,6] [4,8]
  9.        [1,3,5,7] [2,4,6,8]
  10.        [1,2,3,4,5,6,7,8]
  11. """

代码实现

  1. class MergeSort:
  2.     """
  3.     如数据  [1,5,3,7,2,6,4,8]
  4.     开始分割：
  5.            [1,5,3,7] | [2,6,4,8]
  6.            [1,5]|[3,7] | [2,6] | [4,8]
  7.            [1] | [5] | [3] | [7] |  [2] |  [6] |  [4] |  [8]
  8.     开始合并:
  9.            [1,5] [3,7] [2,6] [4,8]
  10.            [1,3,5,7] [2,4,6,8]
  11.            [1,2,3,4,5,6,7,8]
  12.     """
  14.     def __init__(self, data: list):
  15.         self.data = data
  16.         # self.sort_data = []
  18.     def sort(self):
  19.         self.data = self.__merge_sort(self.data)
  21.     def __merge_sort(self,data:list):
  22.         """归并排序"""
  23.         print(f"分割数组 {data}")
  24.         #  优化点 如果当数组中的元素达到指定大小就可以使用其他排序方式直接进行排序
  25.         if len(data) == 1:
  26.             return data
  28.         # if len(data) == 3:
  29.         #     print("---")
  30.         #     return insert_sort(data)
  31.         # elif len(data)==1:
  32.         #     return data
  34.         # 使用二分法将数列分两个
  35.         mid = len(data) // 2
  37.         left = data[:mid]
  38.         right = data[mid:]
  39.         # 使用递归运算
  40.         return self.marge(self.__merge_sort(left), self.__merge_sort(right))
  42.     def marge(self, left: list, right: list):
  43.         """排序合并两个数列"""
  44.         print(f"合并数据 {left} {right}")
  45.         result = []
  46.         # 优化 如果当存在两数组中第一个值比另一个最后的值小，不用再行比较
  47.         if len(left) > 0 and len(right) and left[-1] < right[0]:
  48.             result = left + right
  49.         elif len(left) > 0 and len(right) and left[0] > right[-1]:
  50.             result = right + left
  51.         else:
  52.             while len(left) > 0 and len(right) > 0:
  53.                 # 左右第一个开始做比较
  54.                 if left[0] <= right[0]:
  55.                     result.append(left.pop(0))
  56.                 else:
  57.                     result.append(right.pop(0))
  58.             # 只有一个数列中还有值，直接添加
  59.             result += left
  60.             result += right
  61.         return result
  63.     def datas(self):
  64.         return self.data

时间复杂度分析

O(nlogn),如果数据是近乎有序的，则时间复杂度变成O(n)，因为有序的数据中merge的过程不会进行