from memory_profiler import profile
def quick_sort(l: list):
length = len(l)
if length <= 1:
return l
p_index = random.randint(0, length - 1)
p = l[p_index]
less = -1 # 小于n的区域
more = length # 大于n的区域
index = 0 # 当前索引位置
while index < more:
if l[index] < p:
less += 1 # 小于n区域右移1
l[index], l[less] = l[less], l[index]
index += 1 # 当前位置加1
elif l[index] > p:
more -= 1 # 大于n区域左移1，当前位置不变
l[index], l[more] = l[more], l[index]
else:
index += 1 # 当前位置加1
return quick_sort(l[0:less + 1]) + l[less + 1:more] + quick_sort(l[more:])
def quick_sort1(l: list):
if len(l) <= 1:
return l
left, mid, right = [], [], []
# base_index=random.randint(0,len(l)-1) # 随机选取分组对象，可以最大限度使得当前排序的时间复杂度接近O(nlogn)
base = l[0]
for i in l:
if i < base:
left.append(i)
elif i > base:
right.append(i)
else:
mid.append(i)
return quick_sort(left) + mid + quick_sort(right)
def bubble_sort(l: list):
for i in range(len(l)):
for j in range(i + 1, len(l)):
if l[i] > l[j]:
l[i], l[j] = l[j], l[i]
return l
import heapq
def heapify(arr: list, index: int, heap_size: int):
'''
堆放，使根节点值最大或最小
考察index位置的值能否往下沉，较大的孩子如果大于父，父节点往下沉，较大孩子上去，循环向下走，直到走不下去
heap_size：堆大小，可以灵活使用，控制下沉深度
'''
left = index * 2 + 1
while left < heap_size:
# 获取两个孩子中最大孩子的索引
largest = left + 1 if left + 1 < heap_size and arr[left + 1] > arr[left] else left
# 获取最大孩子跟当前头中较大的值的索引
largest = largest if arr[largest] > arr[index] else index
# 比较确认孩子的值是否更大,
if largest == index:
break
# 如果头比孩子小就交换值，继续向下比较
arr[index], arr[largest] = arr[largest], arr[index]
index = largest
left = index * 2 + 1
return arr
def heapinsert(arr: list, index: int):
'''
堆插入
大根堆：当前节点值跟父节点的值比较，如果当前位置值大于父位置值，则当前位置值跟父位置的值交换，从而实现大根堆
index:当前位置节点，
(index-1)//2:父位置节点
'''
while index and arr[index] > arr[(index - 1) // 2]:
arr[index], arr[(index - 1) // 2] = arr[(index - 1) // 2], arr[index]
index = (index - 1) // 2
return arr
def heap_sort(l: list):
print(l)
h = []
while l:
# heapq.heapify(l)
# h.append(l.pop(0))
h.append(heapq.heappop(l))
return h
def heap_sort1(l: list):
if l is None or len(l) < 2:
return
# case_1、先插入数据后排序,可以应对某些动态场景(O(N*logN));一个一个数给
# for i in range(len(l)):
# heapinsert(l, i)
# case_2、直接heapify排序(O(N*logN));一次给全部数
i = len(l) - 1
for _ in range(len(l)):
heapify(l, i, len(l))
i -= 1
heap_size = len(l)
heap_size -= 1
l[0], l[heap_size] = l[heap_size], l[0]
while heap_size > 0:
heapify(l, 0, heap_size)
heap_size -= 1
l[0], l[heap_size] = l[heap_size], l[0]
return l
@profile(precision=4, stream=open('quick_sort.log', 'w+'))
def test_quick_sort(list_length):
l = [random.randint(0, 1000) for _ in range(list_length)]
s = time.time()
res = quick_sort(l)
e = time.time()
print(e - s)
@profile(precision=4, stream=open('quick_sort1.log', 'w+'))
def test_quick_sort1(list_length):
l = [random.randint(0, 1000) for _ in range(list_length)]
s = time.time()
res = quick_sort1(l)
e = time.time()
print(e - s)
@profile(precision=4, stream=open('bubble_sort.log', 'w+'))
def test_bubble_sort(list_length):
l = [random.randint(0, 1000) for _ in range(list_length)]
s = time.time()
res = bubble_sort(l)
e = time.time()
print(e - s)
@profile(precision=4, stream=open('heap_sort.log', 'w+'))
def test_heap_sort(list_length):
l = [random.randint(0, 1000) for _ in range(list_length)]
s = time.time()
res = heap_sort(l)
print(res)
e = time.time()
print(e - s)
@profile(precision=4, stream=open('heap_sort1.log', 'w+'))
def test_heap_sort1(list_length):
l = [random.randint(0, 1000) for _ in range(list_length)]
s = time.time()
res = heap_sort1(l)
print(res)
e = time.time()
print(e - s)
@profile(precision=4, stream=open('sort.log', 'w+'))
def test_sort(list_length):
l = [random.randint(0, 1000) for _ in range(list_length)]
s = time.time()
l.sort()
# print(l)
e = time.time()
print(e - s)
list_length = 100
# test_quick_sort(list_length)
# test_quick_sort1(list_length)
# test_bubble_sort(list_length)
test_heap_sort(list_length)
# test_heap_sort1(list_length)
# test_sort(list_length)
网友评论