明白查找和排序基本原理，但是一直手写不出来。手打一遍，帮助记忆。
  • 二分查找：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# author: nemo_chen
# 二分查找Python实现

def binary_search(arr, key):
    start = arr[0]
    end = arr[-1]
    while start <= end:
        mid = start + (end - start) / 2
        if arr[mid] > key:
            start = mid -1
        elif arr[mid] < key:
            start = mid + 1
        else:
            return mid
  • 常用排序
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# author: nemo_chen
# 几种常用排序Python实现
# http://blog.csdn.net/mrlevo520/article/details/77829204

# 冒泡
def bubbleSort(arr):
    l = len(arr)
    for i in range(l):
        for j in range(l-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 选择
# method one:
def selectSort(arr):
    l = len(arr)
    for i in range(l):
        min_index = i
        for j in range(i+1, l):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[j]
    return arr
    
# method two:
def selectSort(arr):
    l = len(arr)
    for i in range(l):
        for j in range(l - i):
            if arr[i] > arr[j+i]:
                arr[i], arr[i+j] = arr[i+j], arr[i]
    return arr

# 快速
def quickSort(arr):
    if len(arr) < 2:
        return arr
    else:
        basic = arr[0]
        less = [i for i in arr[1:] if i < basic]
        more = [i for i in arr[1:] if i > basic]
        return quickSort(less) + [basic] + quickSort(more)

# 插入
def insertSort(arr):
    l = len(arr)
    for i in range(1, l):
        for j in range(i):
            if arr[i] < arr[j]:
                arr.insert(j, arr[i])
                arr.pop(i+1)
                break
    return arr

# 希尔
def shellSort(arr):
    l = len(arr)
    basic = l / 2
    while basic > 0:
        for i in range(basic, l):
            temp = arr[i]
            j = i
            while j >= basic and arr[j - basic] > temp:
                arr[j] = arr[j - basic]
                j -= basic
            arr[j] = temp
        basic = basic / 2
    return arr

# 合并
def merge(left, right):
    result = []
    while left and right:
        result.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid_index = len(arr) / 2
    left = mergeSort(arr[:mid_index])
    right = mergeSort(arr[min_index:])
    return merge(left, right)

参考：