python-常用算法

发表于 | in | | 访客

记录一下常用的算法实现

斐波拉契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 递归方式输出n个斐波那契數列
def fib1(x):
  if x < 2: return x
  return fib1(x - 2) + fib1(x - 1)
# 调用，返回10个斐波拉契数列
for i in range(10):
  print fib1(i)
输出：
0
1
1
2
3
5
8
13
21
34
# yield(生成器)方式输出n以内的斐波那契數列
def fib2(n):
    prev, curr = 0, 1
    while prev < n:
        yield prev
        prev, curr = curr, curr + prev
# 调用，返回10以内的斐波拉契数列 
for i in fib2(10):
  print i
输出：
0
1
1
2
3
5
8
# 遍历方式输出n以内的斐波拉契数列
def fab3(n):
    prev, cur = 0, 1
    while prev < n:
        print prev
        prev, cur = cur, prev + cur
fab3(10)
0
1
1
2
3
5
8

质数

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数

1
2
3
4
5
6
7
8
9
def test(max_):
  n = []
  for i in range(2, max_):
    for j in range(2, i):
      if i%j == 0:
        break
    else: n.append(i)  # 注意该行的缩进与内循环for对齐
  return n
print test(50)

排序

冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

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

拆入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

1
2
3
4
5
6
7
8
9
10
11
12
def insert_sort(lists):
    # 插入排序
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

快速排序

快排的思想：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

时间复杂度：O(nlgn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 普通写法
def quick(infos):
    if len(infos) <= 1:
        return infos
    mins = []
    maxs = []
    for v in infos[1:]:
        if v > infos[0]:
            maxs.append(v)
        elif v < infos[0]:
            mins.append(v)
    return quick(mins) + [infos[0]] + quick(maxs)  
 
lists = [72, 15, 4, 41, 16, 7, 2, 23]
res = quick(lists)
# list 推导式写法 
def quick_tds(infos):
    if len(infos) <= 1:
        return infos
    return quick_tds([v for v in infos[1:] if v < infos[0]] + [infos[0]]) + quick_tds([v for v in infos[1:] if v > infos[0]])
 
lists = [72, 15, 4, 41, 16, 7, 2, 23]
res = quick_tds(lists)
print(res)

直接选择排序

基本思想：第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

1
2
3
4
5
6
7
8
9
10
def select_sort(lists):
    # 选择排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if i < size / 2:
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)
 
def build_heap(lists, size):
    for i in range(0, (size/2))[::-1]:
        adjust_heap(lists, i, size)
 
def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)

二分查找

二分查找又称折半查找，binary search，是一种效率较高的查找方法。该算法将数组的中间元素与查找元素进行比较，如果相等，则查找结束； 如果查找元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半数组中查找，而且也是从中间元素开始比较，重复以上过程，直到找到满足条件的结果。 如果在某一步骤中数组为空，则表示找不到。该查找算法每一次比较都使搜索范围缩小一半。

利用二分查找来做，事先需要对列表进行排序，二分查找只对有序表有效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 输入指定列表和一个待查找的元素，输出元素是否在列表中，若存在则返回下标
def binary_search(sorted_list, target):
    mid = len(sorted_list) // 2
    if len(sorted_list) > 0:
        if target < sorted_list[mid]:
            sorted_list = sorted_list[:mid]
            return binary_search(sorted_list, target)
        elif target > sorted_list[mid]:
            sorted_list = sorted_list[mid + 1:]
            return binary_search(sorted_list, target)
        else:
            print "find it"
    else:
        print 'Not find'
num_list = sorted([34,6,78,9,23,56,177,33,2,6,30,99,83,21,17])
res = binary_search(num_list, 3)