算法
一、时间复杂度O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
循环减半的过程 O(logn)
几次循环就是n的几次方的复杂度
二、冒泡排序 选择排序 插入排序
#冒泡排序
def bubble_sort(li):
for i in range(len(li) - 1):
for j in range(len(li) - i - 1):
if li > li:
li, li = li, li
#冒泡排序优化
def bubble_sort_1(li):
for i in range(len(li) - 1):
exchange = False
for j in range(len(li) - i - 1):
if li > li:
li, li = li, li
exchange = True
if not exchange:
break
#选择排序
def select_sort(li):
for i in range(len(li) - 1):
min_loc = i
for j in range(i+1,len(li)):
if li < li:
min_loc = j
li, li = li, li
#插入排序
def insert_sort(li):
for i in range(1, len(li)):
tmp = li
j = i - 1
while j >= 0 and li > tmp:
li=li
j = j - 1
li = tmp
三、快速排序
#第一步，小的在左边，大的房右边
def quick_sort_x(data, left, right):
if left < right:
mid = partition(data, left, right)
quick_sort_x(data, left, mid - 1)
quick_sort_x(data, mid + 1, right)
#左右取进行调整
def partition(data, left, right):
tmp = data
while left < right:
while left < right and data >= tmp:
right -= 1
data = data
while left < right and data <= tmp:
left += 1
data = data
data = tmp
return left
四、堆排序
def sift(data, low, high):
i = low
j = 2 * i + 1
tmp = data
while j <= high: #只要没到子树的最后
if j < high and data < data:
j += 1
if tmp < data:#如果领导不能干
data = data #小领导上位
i = j
j = 2 * i + 1
else:
break
data = tmp
def heap_sort(data):
n = len(data)
for i in range(n // 2 - 1, -1, -1):
sift(data, i, n - 1)
for i in range(n - 1, -1, -1):
data, data = data, data
sift(data, 0, i - 1)
五、归并排序
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high:
if li < li:
ltmp.append(li)
i += 1
else:
ltmp.append(li)
j += 1
while i <= mid:
ltmp.append(li)
i += 1
while j <= high:
ltmp.append(li)
j += 1
li = ltmp
def _mergesort(li, low, high):
if low < high:
mid = (low + high) // 2
_mergesort(li,low, mid)
_mergesort(li, mid+1, high)
merge(li, low, mid, high)
六、希尔排序
def shell_sort(li):
gap = int(len(li) // 2)
while gap >= 1:
for i in range(gap, len(li)):
tmp = li
j = i - gap
while j >= 0 and tmp < li:
li = li
j -= gap
li = tmp
gap = gap // 2
页:
[1]