个人制作一个网站的费用,怎么建立网站站点,如何获得网站域名,如何建设网络营销网站归并排序原理
1#xff09; 整体就是一个简单递归#xff0c; 左边排好序、 右边排好序、 让其整体有序 2#xff09; 让其整体有序的过程里用了外排序方法 3#xff09; 利用master公式来求解时间复杂度 4#xff09; 归并排序的实质 时间复杂度O(N*logN)#xff0c;额…归并排序原理
1 整体就是一个简单递归 左边排好序、 右边排好序、 让其整体有序 2 让其整体有序的过程里用了外排序方法 3 利用master公式来求解时间复杂度 4 归并排序的实质 时间复杂度O(N*logN)额外空间为O(N).
code1
from test1 import *def merge(arr, l, mid, r): # arrhelp [0] * (r - l 1)i 0p1 lp2 mid 1while p1 mid and p2 r:if arr[p1] arr[p2]: # 左侧小于等于右侧拷贝左侧 时默认拷贝右边help[i] arr[p1]i 1p1 1else:help[i] arr[p2]i 1p2 1while p1 mid: # 只剩下左侧 把左侧拷贝到help数组help[i] arr[p1]i 1p1 1while p2 r: # 只剩下右侧侧 把右侧拷贝到help数组help[i] arr[p2] i 1p2 1# help copy to arrfor i in range(r-l1):arr[li] help[i]returndef mergeSort1(arr, l, r):if l r:returnmid l ((r - l) 1)mergeSort1(arr, l, mid)mergeSort1(arr, mid 1, r)merge(arr, l, mid, r)returndef mergeSort(arr):if arr None or len(arr) 2:returnmergeSort1(arr, 0, len(arr) - 1)
test
# for test
def main():testTime 500000 # 500000maxSize 100maxValue 100succeed Truefor i in range(testTime):arr1 generateRandomArray(maxSize, maxValue)arr2 copyArray(arr1)mergeSort(arr1) # ------------------test------comparator(arr2)if (not isEqual(arr1, arr2)):succeed FalseprintArray(arr1)printArray(arr2)breakif succeed:print(Nice!)else:print(Fucking fucked!)arr generateRandomArray(maxSize, maxValue)printArray(arr)mergeSort(arr)printArray(arr)if __name__ __main__:main()时间复杂度
1. T(N) 2 T(N / 2) O(N)根据master公式 时间复杂度 O(NlongN)选择、冒泡、插入排序的比较行为没有保留下来。
归并排序的比较行为被保留下来变成了整体有序的部分。因而时间复杂为O(NlogN)
