[算法基础]快排、归并、堆排序比较
2021-05-17 15:29
标签：for 分析 div 空间 调用 += 快速排序 时间复杂度 分而治之 1、快速排序，上代码： 分析一哈： 当不考虑最差情况(O(n^2))时，快排时间复杂度为O(nlogn):因为层数为O(logn)即调用栈的高度是O(logn)，而每层的时间是O(n) 采用分而治之的方法，先把数组分成一个个长度为1的数组，再将数组分别按顺序组合成一个数组 因此涉及到两个过程：切分、组合 时间复杂度：最好和最差都是O(nlogn) 空间复杂度：O(logn) 以空间换时间的典型栗子 [算法基础]快排、归并、堆排序比较 标签：for 分析 div 空间 调用 += 快速排序 时间复杂度 分而治之 原文地址：https://www.cnblogs.com/halleluyah/p/9746305.htmldef quickSort(arr):
if len(arr) :
return arr
v = arr[0]
high = [i for i in arr[1:] if i>=v]
low = [i for i in arr[1:] if iv]
return quickSort(low) + [v] + quickSort(high)
2、合并排序1.组合过程：两个有序数组按顺序合并为一个数组
def merge(a, b):
i, j = 0, 0
c = []
while i and j len(b):
if a[i] b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
c.extend(a[i:])
c.extend(b[j:])
return c
2.切分过程：只要数组长度大于1就由上而下切割数组，最后自下而上合并
def merge_sort(arr):
print(arr)
if len(arr) :
return arr
mid = len(arr) / 2
# dividing the array up to bottom
back = merge_sort(arr[:mid])
fore = merge_sort(arr[mid:])
# merge every 1 length array to the complete
return merge(back, fore)