当前位置：网站首页>空间复杂度为O(1)的归并排序

空间复杂度为O(1)的归并排序

2022-08-10 00:54:00 【qnner】

前言

最近楼主在刷算法题目，刷到了归并排序。自己简单实现后，再次跟常见的归并排序比较，发现空间复杂度更低。所以记录本文用于比较两种算法的实现方式。

经典实现方式：空间复杂度O(n)

这里不再赘述，贴一篇牛客网写的比较详细的帖子：https://www.nowcoder.com/discuss/968849?type=all&order=recall&pos=&page=1&ncTraceId=&channel=-1&source_id=search_all_nctrack&gio_id=8AD3C350B55856EAFE45974949E1359F-1660059896728

复杂度分析：

时间复杂度 NlogN
空间复杂度 O(N)

我的实现

思路

重点是merge函数。merge函数的作用是合并两个已经排序的数组。我这里的大致思路是，将其中一个数组作为基，把另外一个数组的每一个元素都插入到这个基里面去。

代码实现

def cmp(left, mid):
    return left > mid


def merge(arr, left, mid, right):
    while mid < right:
        for move_left in range(left, mid):
            if cmp(arr[move_left], arr[mid]):
                tmp = arr[move_left]
                for i in range(move_left, mid):
                    arr[move_left] = arr[i + 1]
                    arr[i + 1] = tmp
                    tmp = arr[move_left]
                left = move_left
                break
        mid += 1


def merge_sort(arr, l=None, r=None):
    if l is None:
        l = 0
    if r is None:
        r = len(arr)
    if l == r -1:
        return arr
    else:
        mid = int((l + r) / 2)
        merge_sort(arr, l, mid)
        merge_sort(arr, mid + 1, r)
        merge(arr, l, mid, r)


if __name__ == '__main__':
    arr = [12, 2, 3]
    merge_sort(arr)

    print(arr)

可以看见，在merge的时候，并没有使用额外的数组空间，所以空间复杂度为O(1)

原网站

版权声明
本文为[qnner]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2069335