算法

wtxnpw

　　一、时间复杂度
　　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[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
#冒泡排序优化
def bubble_sort_1(li):
for i in range(len(li) - 1):
exchange = False
for j in range(len(li) - i - 1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
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[j] < li[min_loc]:
min_loc = j
li, li[min_loc] = li[min_loc], li
#插入排序
def insert_sort(li):
for i in range(1, len(li)):
tmp = li
j = i - 1
while j >= 0 and li[j] > tmp:
li[j+1]=li[j]
j = j - 1
li[j + 1] = 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[left]
while left < right:
while left < right and data[right] >= tmp:
right -= 1
data[left] = data[right]
while left < right and data[left] <= tmp:
left += 1
data[right] = data[left]
data[left] = tmp
return left
　　四、堆排序



def sift(data, low, high):
i = low
j = 2 * i + 1
tmp = data
while j <= high: #只要没到子树的最后
if j < high and data[j] < data[j + 1]:
j += 1
if tmp < data[j]:#如果领导不能干
data = data[j] #小领导上位
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[0], data = data, data[0]
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[j]:
ltmp.append(li)
i += 1
else:
ltmp.append(li[j])
j += 1
while i <= mid:
ltmp.append(li)
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = 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[j]:
li[j + gap] = li[j]
j -= gap
li[i - gap] = tmp
gap = gap // 2