python实现各种算法详解，以及时间复杂度
python实现各种排序1. 快速排序
1：首先取序列第一个元素为基准元素pivot=R。i=low,j=high。
2：从后向前扫描，找小于等于pivot的数，如果找到，R与R交换，i++。
3：从前往后扫描，找大于pivot的数，如果找到，R与R交换，j--。
4：重复2~3，直到i=j,返回该位置mid=i,该位置正好为pivot元素。 完成一趟排序后，以mid为界，将序列分为两部分，左序列都比pivot小，有序列都比pivot大，然后再分别对这两个子序列进行快速排序。
以序列（30，24，5，58，16，36，12，42，39）为例，进行演示：
1、初始化，i=low,j=high,pivot=R=30：
ij302455816261241392、从后往前找小于等于pivot的数，找到R=12
ij30245581626124139
[*]R与R交换，i++
ij122455816263041393、从前往后找大于pivot的数，找到R=58
ij12245581626304139
[*]R与R交换，j--
ij122453016265841394、从后往前找小于等于pivot的数，找到R=16
ij12245301626584139
[*]R与R交换，i++
i,j122451630265841395、从前往后找大于pivot的数，这时i=j,第一轮排序结束，返回i的位置，mid=i
Lowmid-1midmid+1High1224516302658413此时已mid为界，将原序列一分为二，左子序列为（12，24，5，18）元素都比pivot小，右子序列为（36，58，42，39）元素都比pivot大。然后在分别对两个子序列进行快速排序，最后即可得到排序后的结果。
def quicksort(low,high,li):
if low >= high:
return li
i = low
j= high
pivot = li
while i<j:
while i<j and li>pivot:
j -= 1
li = li
while i<j and li<pivot:
i += 1
li = li
li = pivot
quicksort(low,i-1,li)
quicksort(i+1,high,li)
return li
lists=
print("排序前的序列为：")
for i in lists:
print(i,end =" ")
print("\n排序后的序列为：")
for i in quicksort(0,len(lists)-1,lists):
print(i,end=" ")5. 归并排序
将原问题划分成 n 个规模较小而结构与原问题相似的子问题；递归地解决这些问题，然后再合并其结果，就得到原问题的解。从上图看分解后的数列很像一个二叉树。
归并排序采用分而治之的原理：
[*]将一个序列从中间位置分成两个序列；
[*]在将这两个子序列按照第一步继续二分下去；
[*]直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。
def merge(left,right): r,l = 0,0 res = [] while r < len(right) and l < len(left): if left < right:# 排序，小于等于的放左边 res.append(left) l += 1 else: res.append(right)# 排序，大的放右边 r += 1 res +=(left) res +=(right) return resdef mergesort(li): if(len(li))
页:
[1]