一、冒泡排序
1.1、冒泡的原理
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2.1、冒泡排序的代码实现
def bubble_sort(seq):
count=len(seq)
for i in range(0,count):
for j in range(i+1,count):
if seq[i]>seq[j]:
seq[i],seq[j]=seq[j],seq[i]
return seq
seq=[4,5,2,1,6,3]
print(bubble_sort(seq))
3.1、冒泡排序的时间复杂度
1、最好情况：若文件的初始状态是正序的，一趟扫描即可完成排序，这是冒泡排序的最优情况时间复杂度o(n)
2、最坏情况：若初始文件是反序的的，则冒泡排序需要两层循环，这是最坏情况时间复杂度o(n^2)
3、平均时间复杂度o(n^2)
二、快排
2.1 快排原理
快排是冒泡排序的改进，抽取第一个值作为比较值，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比比较值小，另一部分比比较值大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最后将分开的来两部分加比较值合并到一起，完成排序。
2.2 快排的代码实现
def quck_sort(seq):
if seq==[]:
return []
else:
pivot=seq[0]
low_list=quck_sort([x for x in seq if x<pivot]) #比比较值小的部分递归排序
upper_list=quck_sort([x for x in seq if x>pivot])#比比较值大的部分递归排序
return low_list+[pivot]+upper_list #将三者进行合并，注意将比较值转换成列表
print(quck_sort(seq))
2.3 快排的时间复杂度
1、最优情况：比较值刚好将列表分成等分了两部分，时间复杂度o(nlogn)
2、最坏情况：每次递归比较值都是最小值，导致列表分开不均衡，时间复杂度o(n^2)
3、平局时间复杂度o(nlogn)
三、堆排序
堆排序原则，1.先对数据进行建堆操作（可以建大根堆或小根堆） 大跟堆：任一节点都比其孩子节点大
2.再对建好的堆进行出树据操作，交换堆顶元素和末尾元素并重建堆两部分组
def shit(li,low,high): #建堆
#li表示树，low表示树跟，high 表示最后一个节点的位置
temp=li[low]
i=low #i指向调整为起始为0
j=2*i+1 #左孩子的位置
while j<=high:
if j+1<=high and li[j]<li[j+1]: #如果右孩子存在，且右孩子比左孩子大，j指向右孩子
j+=1
if li[j]>temp: #比较跟节点值和新指向j的大小
li[i]=li[j] #如果j的值大于temp，跟节点和孩子节点位置互换，i位置调整到j的位置
i=j
j=2*i+1 #得出调整后新的j的位置
else: #循环推出的条件，temp值比两个孩子均大，不做调整
break
li[i]=temp
def heap_sort(li):
n=len(li)
#1.构造堆
for low in range(n//2-1,-1,-1):
shit(li,low,n-1)
#2.挨个出数
for high in range(n-1,-1,-1):
li[0],li[high]=li[high],li[0] #树顶的数据跟尾部数据交换，
shit(li,0,high-1) #每次循环high的位置多一个大的数字，位置调整一次，剩余的部分再建堆 arr1=[1,4,3,6,5,8,2,7]
heap_sort(arr1)
print(arr1)
其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
python中heapq模块是堆排序模块，他建立的堆属于小根堆，用法如下：
import heapq
li=[1,3,2,6,4,7,5,9,8]
heapq.heapify(li) #建堆(小根堆)
heapq.heappush(li,0)#向队中加入一个数字，会自动做重新建堆操作
heapq.heappop()#从堆中取数据，由于其建的是小根堆，最后出的是0