Python实现常见算法

曾用python实现的小算法,防止以后找不到了,今后再用python实现的算法,也放在这里



排序相关


直接选择排序


1
2
3
4
5
6
7
8
9
10
11
12
13
# 直接选择排序
def select_sort(array):
if not array:
return []
for i in range(len(array) - 1, 0, -1):
large = array[0]
pos = 0
for j in range(1, i + 1):
if array[j] > large:
pos = j
large = array[j]
array[pos], array[i] = array[i], array[pos]
return array

冒泡排序


1
2
3
4
5
6
7
8
9
# 冒泡排序
def bubble_sort(array):
if not array:
return []
for i in range(len(array) - 1, 0, -1):
for j in range(i):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array

快速排序


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 快速排序
def quick_sort(array):
if not array:
return []
quick_sort_temp(array, 0, len(array) - 1)
return array


def quick_sort_temp(array, low, high):
if low >= high:
return
flag = array[low]
l, h = low + 1, high
while l < h:
while h > l and array[h] >= flag:
h -= 1
while l < h and array[l] < flag:
l += 1
if l != h:
array[l], array[h] = array[h], array[l]
array[low], array[l] = array[l], array[low]
quick_sort_temp(array, low, l - 1)
quick_sort_temp(array, l + 1, high)

堆排序


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
# 堆排序
def heep_sort(array):
if not array:
return []
for i in range(len(array) - 1, 0, -1):
heep_sort_up(array, i)
for i in range(len(array) - 1, 0, -1):
array[0], array[i] = array[i], array[0]
heep_sort_down(array, i - 1, 0)
return array


def heep_sort_up(array, pos):
while pos > 0:
father = (pos - 1) / 2
if array[father] <= array[pos]:
array[father], array[pos] = array[pos], array[father]
pos = father


def heep_sort_down(array, max_pos, root):
if root > max_pos:
return
large = root
left, right = root * 2 + 1, root * 2 + 2
if left <= max_pos and array[large] < array[left]:
large = left
if right <= max_pos and array[large] < array[right]:
large = right
if large != root:
array[large], array[root] = array[root], array[large]
heep_sort_down(array, max_pos, large)



斐波那契数列


斐波那契数列-1


1
2
# 斐波那契数列 o(n^2)
fab = lambda n: fab(n - 1) + fab(n - 2) if n > 1 else n

斐波那契数列-2


1
2
3
# 斐波那契数列 o(n^2)
def fabN(n):
return fabN(n - 1) + fabN(n - 2) if n > 1 else n

斐波那契数列-3


1
2
3
4
5
6
7
8
9
# 斐波那契数列 o(n)
def fabN1(n):
if n > 1:
temp = [0, 1]
while len(temp) <= n:
temp.append(temp[len(temp) - 1] + temp[len(temp) - 2])
return temp[len(temp) - 1]
else:
return n



二分查找


1
2
3
4
5
6
7
8
9
10
11
12
13
# 二分查找
def bin_search(array, start, end, value):
if not array or start < 0 or end >= len(array):
return -1
if start >= end:
return -1
mid = (start + end) >> 1
if array[mid] == value:
return mid
elif array[mid] > value:
return bin_search(array, start, mid, value)
else:
return bin_search(array, mid, end, value)



字符串


回文字符串


1
2
3
4
5
6
7
8
9
# 回文字符串
def is_huiwen(data):
if not data:
return False
size = len(data)
for i in range(size / 2):
if data[i] != data[size - 1 - i]:
return False
return True






文章目录
  1. 1. 排序相关
    1. 1.1. 直接选择排序
    2. 1.2. 冒泡排序
    3. 1.3. 快速排序
    4. 1.4. 堆排序
  2. 2. 斐波那契数列
    1. 2.1. 斐波那契数列-1
    2. 2.2. 斐波那契数列-2
    3. 2.3. 斐波那契数列-3
  3. 3. 二分查找
  4. 4. 字符串
    1. 4.1. 回文字符串