python实现各种算法详解，以及时间复杂度

用心的医美匠人

python实现各种排序

1. 快速排序

1：首先取序列第一个元素为基准元素pivot=R[low]。i=low,j=high。
2：从后向前扫描，找小于等于pivot的数，如果找到，R与R[j]交换，i++。
3：从前往后扫描，找大于pivot的数，如果找到，R与R[j]交换，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[low]=30：
ij302455816261241392、从后往前找小于等于pivot的数，找到R[j]=12
ij30245581626124139

• R与R[j]交换，i++
  

ij122455816263041393、从前往后找大于pivot的数，找到R=58
ij12245581626304139

• R与R[j]交换，j--
  

ij122453016265841394、从后往前找小于等于pivot的数，找到R[j]=16
ij12245301626584139

• R与R[j]交换，i++
  

i,j12245163026584139

5、从前往后找大于pivot的数，这时i=j,第一轮排序结束，返回i的位置，mid=i

Lowmid-1midmid+1High1224516302658413此时已mid为界，将原序列一分为二，左子序列为（12，24，5，18）元素都比pivot小，右子序列为（36，58，42，39）元素都比pivot大。然后在分别对两个子序列进行快速排序，最后即可得到排序后的结果。

1. def quicksort(low,high,li):
2.     if low >= high:
3.         return li
4.     i = low
5.     j= high
6.     pivot = li[low]
7.     while i<j:
8.         while i<j and li[j]>pivot:
9.             j -= 1
10.         li[i] = li[j]
11.         while i<j and li[i]<pivot:
12.             i += 1
13.         li[j] = li[i]
15.     li[j] = pivot
16.     quicksort(low,i-1,li)
17.     quicksort(i+1,high,li)
18.     return li
22. lists=[30,24,5,58,18,36,12,42,39]
23. print("排序前的序列为：")
24. for i in lists:
25.     print(i,end =" ")
26. print("\n排序后的序列为：")
27. for i in quicksort(0,len(lists)-1,lists):
28.     print(i,end=" ")

复制代码

5. 归并排序

将原问题划分成 n 个规模较小而结构与原问题相似的子问题；递归地解决这些问题，然后再合并其结果，就得到原问题的解。从上图看分解后的数列很像一个二叉树。
归并排序采用分而治之的原理：

• 将一个序列从中间位置分成两个序列；
  
• 在将这两个子序列按照第一步继续二分下去；
  
• 直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。
  

[code]def merge(left,right):    r,l = 0,0    res = []    while r < len(right) and l < len(left):        if left[l] < right[r]:  # 排序，小于等于的放左边            res.append(left[l])            l += 1        else:            res.append(right[r])  # 排序，大的放右边            r += 1    res +=(left[l:])    res +=(right[r:])      return resdef mergesort(li):    if(len(li))