# -*- coding: utf-8 -*-
# !/usr/bin/python3
"""
@ version: ??
@ author: Alex
@ file: Algorithm
@datetime: 2020/1/13 - 0:53
@explain:
"""
import random
from functools import wraps
import time
def thisTime(func):
@wraps(func)
def wrapper(funcc, count):
start = time.time()
print(f"{count} This result-> {func(funcc(count))}")
print(f"{count} This time -> {start - time.time()}")
return wrapper
def create_random(count):
"""Create random unordered data"""
data = list(range(count))
random.shuffle(data)
return data
def create_reversed(count):
"""Create reversed data"""
return list(range(count, 0, -1))
@thisTime
def func304(array:list):
"""归并"""
def merge(arr, left, mid, right, res):
"""合并"""
l,r,start = left, mid + 1, left
Array = [0 for _ in range(len(arr))]
while l <= mid and r <= right:
if arr[l] < arr[r]:Array[start],l,start = arr[l],l+1 , start+1
else:Array[start], r, start,res = arr[r], r+1, start +1, res + mid - l + 1
while l <= mid:Array[start],l, start = arr[l], l+1, start+1
while r <= right:Array[start], r, start = arr[r], r+1, start+1
for i in range(left, right + 1):arr[i] = Array[i]
return res
def sort(arr, left, right, res):
if left >= right: return res # 出口
mid = (left + right) >> 1
# 分
l = sort(arr, left, mid, res)
r = sort(arr, mid+1, right, res)
# 并
return merge(arr, left, mid, right, l + r)
return sort(array, 0, len(array)-1, 0)
func304(create_random, 1000)
func304(create_reversed, 1000)
func304(create_random, 5000)
func304(create_reversed, 5000)