前面的时候讲了一些时间复杂度是
的排序算法,虽然希尔排序不是
的排序算法,但是在真正的实际应用中还是比较少的,因为相对来说,排序所需的时间比较长。
今天我就给你介绍另外一种排序算法,归并排序算法。它的时间复杂度是
, 而且是稳定的排序算法,唯一美中不足的一点是它不是原地排序算法,需要使用额外的存储空间。
归并排序,采用的是分而治之的思想,将要排序的区间一分为二,当左右区间都有序后,就相当于对两个有序数组进行合并。那怎样左右区间的元素才能有序呢?这就需要再一次进行一分为二了,当左、右区间的元素只有一个的时候,自然而然就是有序的了。
从上面的描述,我们可以看出,这是一个不断将大问题划分为小问题的过程,这不正是递归算法的精髓所在嘛。没错,归并排序算法一般都是基于递归进行实现的。
好了,接下来,看下动画演示。
#!/usr/bin/python
# -*- coding:utf-8 -*-
from typing import List
def merge_sort(array: List[int]) -> None:
_merge_sort_(array, 0, len(array)-1)
def _merge_sort_(array: List[int], low: int, high: int) -> None:
if low < high:
mid = low + ((high - low) >> 1)
_merge_sort_(array, low, mid)
_merge_sort_(array, mid+1, high)
_merge(array, low, mid, high)
def _merge(array: List[int], low: int, mid: int, high: int):
# array[low:mid], array[mid, high] are sorted
tmp = []
i, j = low, mid+1
while i <= mid and j <= high:
if array[i] <= array[j]:
tmp.append(array[i])
i += 1
else:
tmp.append(array[j])
j += 1
if i <= mid:
tmp.extend(array[i:mid+1])
else:
tmp.extend(array[j:high+1])
array[low:high+1] = tmp
if __name__ == "__main__":
array1 = [3, 5, 6, 7, 8]
array2 = [2, 2, 2, 2]
array3 = [4, 3, 2, 1]
array4 = [5, -1, 9, 3, 7, 8, 3, -2, 9]
merge_sort(array1)
print(array1)
merge_sort(array2)
print(array2)
merge_sort(array3)
print(array3)
merge_sort(array4)
print(array4)
归并排序除了作为一种排序算法,合并两个有序数组的操作同样是非常经典的,而且在面试求职过程中会经常用到的。
归并排序里面是合并两个有序的数组,还可以合并两个有序的链表、合并 k 个链表等等。
LeetCode 上具体的题目链接有:
归并排序是非常高效的排序算法。
时间复杂度数
,无论要排序的数据是什么样的,性能都是稳定的。
空间复杂度是
另外,合并操作是非常高效且常用的操作,值得我们学习体会。
如果有其他的问题,可以在添加我的微信,欢迎一起交流学习。