|
发表于 2020-1-13 00:37:13
|
显示全部楼层
本帖最后由 Stubborn 于 2020-1-13 01:00 编辑
考虑下并归
- # -*- 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)
复制代码 |
评分
-
查看全部评分
|