Python算法

一、排序

1.冒泡排序

1
2
3
4
5
6
7
8
9
def buble_sort(num):
    for i in range(1,len(num)):
        for j in range(0,len(num)-i):
            if(num[j]>num[j+1]):
                num[j], num[j+1] = num[j+1], num[j]
    return num
num = [1,5,3,26,8,6]
buble_sort(num)

2.选择排序

1
2
3
4
5
6
7
8
9
10
11
def select_sort(num):
    for i in range(len(num)-1):
        minindex = i
        for j in range(i+1,len(num)):
            if(num[j] < num[minindex]):
                minindex = j;
        if minindex != i:
            num[minindex],num[i] = num[i],num[minindex]
    return num
num = [5,3,6,54,564,3]
select_sort(num)

3.插入排序

1
2
3
4
5
6
7
8
9
10
11
def insert_sort(num):
    for i in range(len(num)):
        preindex = i-1
        current = num[i]
        while(preindex >=0 and num[preindex]>current):
            num[preindex+1] = num[preindex]
            preindex-=1
        num[preindex+1] = current
    return num
num = [5,3,6,4,2,9,7]
insert_sort(num)

4.快速排序

1
2
3
4
5
6
7
8
9
10
11
def quick_sort(num):
    if len(num) <= 1:
        return num
    pivot = num[0]
    left = [x for x in num[1:] if x < pivot]
    right = [x for x in num[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

num = [6,5,3,2,4,5]
quick_sort(num)

5.归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge_sort(num):
    if len(num) <= 1:
        return num
    mid = len(num) // 2
    left = merge_sort(num[:mid])
    right = merge_sort(num[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
num = [5,6,48,3,51,4]
merge_sort(num)

6.python排序

1
2
3
4
5
6
num = [5,2,3,6,8,9]
# num.sort()
a = sorted(num)
print(num)
print(a)
num.sort()

二、查找算法

1.顺序查找

1
2
3
4
5
6
def linear_search(nums, x):
    for i in range(len(nums)):
        if nums[i] == x:
            return i
    return -1

2.二分查找

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

3.哈希查找

1
2
3
4
5
6
7
8
9
10
11
def hash_search(arr, target):
    hash_table = {}
    for i in range(len(arr)):
        hash_table[arr[i]] = i
    if target in hash_table:
        return hash_table[target]
    else:
        return -1

nums = [1,36,25,6]
hash_search(nums,1)

三、字符串匹配

1.kmp算法

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
def kmp_match(s, p):
    m = len(s)
    n = len(p)
    if n > m:
        return -1
    if n == 0:
        return 0
    next = make_next(p)
    j = 0
    for i in range(m):
        while j > 0 and p[j] != s[i]:
            j = next[j-1]
        if p[j] == s[i]:
            j += 1
        if j == n:
            return i - n + 1
    return -1

def make_next(p):
    n = len(p)
    next = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and p[j] != p[i]:
            j = next[j-1]
        if p[j] == p[i]:
            j += 1
        next[i] = j
    return next