算法---排序

uf123

　　1.常见的时间复杂度（按耗费的时间排序，时间耗费越少效率越高）
　　O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
　　循环减半就是（O(logn)）
　　2.冒泡排序



li = [6,8,9,7,5,3]
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]
　　3.冒泡排序优化



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:#如果没有执行交换，说明已经是有序状态了，无需继续排序了
return
　　4.快速排序



data = [7,9,5,3,1,4,89]
def partition(data, left, right):
　　 left = 0
　　 right = len(data)
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