冒泡排序
1，思路首先列表每两个相邻的数比较大小，如果前面比后面的大，那么这两个数就互换位置，就像冒泡一样
2代码关键：趟数：n-1趟 无序区
def bubblr_sort(li):
for i in range(1,len(li)-1):#表示趟数
change = True
for j in range(len(li)-i): #表示无序区，无序区的范围为0,len(li)-i
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
change = True
if not change:
return
li = list(range(10))
import random
random.shuffle(li)
print(li)
bubblr_sort(li)
print(li)
快速排序
1思路：取一个元素p(第一个元素），是元素p归位（去他该去的地方）
列表被p分成两部分，左边都比p小，右边的都比p大
递归完成排序
2，算法的关键点：归位，递归
3，图示说明
import time
def wrapper(func):
def inner(*args,**kwargs):
start = time.time()
ret = func(*args,**kwargs)
end = time.time()
print('%s running time :%s'%(func.__name__,start-end))
return ret
return inner
def partition(li,left,right):
'''归位函数'''
tmp = li[left] #先把5取出来
while left < right:
while left < right and li[right] >= tmp: #如果降序排列修改li[right] <= tmp
right -= 1 #从右边找比5小的数，填充到5的位置
li[left] = li[right]
while left < right and li[left] <= tmp: #如果降序排列修改li[right] >= tmp
left += 1# 从左边找比5大的数字放在右边的空位
li[right] = li[left]
li[left] = tmp #当跳出循环条件的时候说明找到了，并且把拿出来的5在放进去
return left
def _quick_sort(li,left,right):
'''快速排序的两个关键点：归位，递归'''
if left < right: #至少有两个元素，才能进行递归
mid = partition(li,left,right) #找到归位的位置
_quick_sort(li,left,mid-1) #递归，右边的-1
_quick_sort(li,mid+1,right) #递归，左边的+1
@wrapper
def quick_sort(li):
return _quick_sort(li, 0, len(li)-1)
@wrapper
def sys_sort(li):
'''系统排序'''
li.sort()
import random
li = list(range(100000))
random.shuffle(li)
# print(li)
quick_sort(li)
# print(li)
sys_sort(li)
#结论：系统的排序要比快排的时间快的多
# quick_sort running time :-0.6240355968475342
# sys_sort running time :-0.002000093460083008
快速排序算法
堆排序
1，堆排序过程
建立堆
得到堆顶元素
去掉堆顶，将堆最后一个元素放在堆顶，此时可通过一次调整重新使堆有序
堆顶元素为第二大元素
重复步骤三，直到堆变空
import random
def _sift(li, low, high):
"""
:param li:
:param low: 堆根节点的位置
:param high: 堆最有一个节点的位置
:return:
"""
i = low # 父亲的位置
j = 2 * i + 1 # 孩子的位置
tmp = li[low] # 原省长
while j <= high:
if j + 1 <= high and li[j + 1] > li[j]: # 如果右孩子存在并且右孩子更大
j += 1
if tmp < li[j]: # 如果原省长比孩子小
li[i] = li[j] # 把孩子向上移动一层
i = j
j = 2 * i + 1
else:
li[i] = tmp # 省长放到对应的位置上(干部)
break
else:
li[i] = tmp # 省长放到对应的位置上(村民/叶子节点)
def sift(li, low, high):
"""
:param li:
:param low: 堆根节点的位置
:param high: 堆最有一个节点的位置
:return:
"""
i = low # 父亲的位置
j = 2 * i + 1 # 孩子的位置
tmp = li[low] # 原省长
while j <= high:
if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在并且右孩子更大
j += 1
if tmp < li[j]: # 如果原省长比孩子小
li[i] = li[j] # 把孩子向上移动一层
i = j
j = 2 * i + 1
else:
break
li[i] = tmp
def heap_sort(li):
n = len(li)
# 1. 建堆
for i in range(n//2-1, -1, -1):
sift(li, i, n-1)
# 2. 挨个出数
for j in range(n-1, -1, -1): # j表示堆最后一个元素的位置
li[0], li[j] = li[j], li[0]
# 堆的大小少了一个元素 （j-1）
sift(li, 0, j-1)
li = list(range(10))
random.shuffle(li)
print(li)
heap_sort(li)
print(li)
# li=[2,9,7,8,5,0,1,6,4,3]
# sift(li, 0, len(li)-1)
# print(li)
希尔排序
思路：希尔排序是一种分组插入排序算法。
首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；
取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组
希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。
def insert_sort(li):#插入排序
for i in range(1, len(li)):
# i 表示无序区第一个数
tmp = li[i] # 摸到的牌
j = i - 1 # j 指向有序区最后位置
while li[j] > tmp and j >= 0:
#循环终止条件： 1. li[j] <= tmp; 2. j == -1
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
def shell_sort(li):#希尔排序 与插入排序区别就是把1变成d
d = len(li) // 2
while d > 0:
for i in range(d, len(li)):
tmp = li[i]
j = i - d
while li[j] > tmp and j >= 0:
li[j+d] = li[j]
j -= d
li[j+d] = tmp
d = d >> 1
li=[5,2,1,4,5,69,20,11]
shell_sort(li)
print(li)
图片发自简书App
