Python 19 算法

一、基本概念

时间复杂度：是用来估计算法运行时间的单位，一般来说时间复杂度高的算法运行速度慢。常见的时间复杂度排序： 1<logn<n<nlogn<n**2<n**2logn<n**3

空间复杂度：用来评估算法所占内存大小

递归的两个特点：调用自身、结束条件

二、二分查找

方式一：非递归

 1 #方式一：非递归
 2 def half_search1(li, val):
 3     start = 0
 4     end = len(li) - 1
 5     while start <= end:
 6         half = (start + end) // 2
 7         if li[half] > val:
 8             end = half - 1
 9         elif li[half] < val:
10             start = half + 1
11         else:
12             return half
13     return

方式二：递归

#方式二：递归
def half_search2(li, val, start, end):
    if start <= end:
        half = (start + end) // 2
        if li[half] > val:
            end = half - 1
            return half_search2(li, val, start, end)
        elif li[half] < val:
            start = half + 1
            return half_search2(li, val, start, end)
        else:
            return half

一般可以不用递归实现的就不使用递归

三、排序

（1）基本排序

1、冒泡排序

冒泡排序是从第一个数开始，依次与下一个数进行比较，如果前一个数大于后一个数，则交换位置，这样每一趟都把无序区最大的数调换到有序区开头。

1 def bubble_sort(li):
2     for i in range(len(li)-1):
3         for j in range(len(li)-1-i):
4             if li[j] > li[j+1]:
5                 li[j], li[j+1] = li[j+1], li[j]
6     return li

2、选择排序

选择排序是每次遍历无序区，找到无序区中的最小值，放到有序区的最后。

1 def choose_sort(li):
2     for i in range(len(li)-1):
3         min_index = i
4         for j in range(i,len(li)):
5             if li[j] < li[min_index]:
6                 min_index = j
7         li[i], li[min_index] = li[min_index], li[i]
8     return li

3、插入排序

插入排序是依次取出一个无序区的数，放在有序区第一个比他小的数右边。

1 def insert_sort(li):
2     for i in range(len(li)):
3         j = i - 1
4         val = li[i]
5         while j >= 0 and li[j] > val:
6             li[j+1] = li[j]
7             j -= 1
8         li[j+1] = val
9     return li

（2）升级排序

1、快速排序

 1 def quick_sort(li, start, end):
 2     if start < end:
 3         md = partition(li, start, end)
 4         quick_sort(li, start, md-1)
 5         quick_sort(li, md+1, end)
 6     return li
 7 
 8 def partition(li, start, end):
 9     val = li[start]
10     while start < end:
11         while start < end and li[end] >= val:
12             end -= 1
13         li[start] = li[end]
14         while start < end and li[start] <= val:
15             start += 1
16         li[end] = li[start]
17     li[start] = val
18     return start

2、堆排序

3、归并排序