排序和查找

算法评定

评价一个算法的好坏, 通常是由空间复杂度和时间复杂度决定的。

而现实中很难做到时间复杂度time complexity和空间复杂度space complexity都很低, 一种被认可的的做法就是牺牲空间换取时间。

常见时间复杂度

表示方法 解释 算法
O(c) 常量级 哈希存储/bloom过滤器
O(log2n) 对数级 二分查找
O(n) 线性级 顺序查找
O(nlog2n) 线性对数级 归并排序/快速排序
O(n^2) 平方级 冒泡排序/选择排序
O(n^3) 立方级 Floyd算法
O(2^n) 指数级 汉诺塔问题
O(n!) 阶乘级 旅行经销商问题

查找

顺序查找

说明

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。

时间复杂度

O(n), 即线性时间复杂度

代码实现

1
2
3
4
5
6
def seq_search(items, elem):
"""顺序查找"""
for index, item in enumerate(items):
if item == elem:
return index
return -1

二分查找

说明

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

时间复杂度

O(log2n), 即对数时间复杂度

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
def bin_search(items, elem):
"""二分查找"""
start, end = 0, len(items) - 1
while start <= end:
mid = (start + end) // 2
if elem > items[mid]:
start = mid + 1
elif elem < items[mid]:
end = mid - 1
else:
return mid
return -1

排序

快速排序

说明

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

图解

QuickSort

时间复杂度

O(nlog2n), 即线性对数时间复杂度

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def sort_arr(arr):
"""快速排序"""
_less = []
_greater = []
if len(arr) <= 1:
return arr
_pivot = arr.pop()
for _item in arr:
if _item <= _pivot:
_less.append(_item)
else:
_greater.append(_item)
return sort_arr(_less) + [_pivot] + sort_arr(_greater)

归并排序

说明

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

图解

MergeSort

时间复杂度

O(nlog2n), 即线性对数时间复杂度

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge_sort(items, cmp=lambda x, y: x > y):
"""归并排序"""
if len(items) < 2:
return items[:]
mid = len(items) // 2
left = merge_sort(items[:mid], cmp)
right = merge_sort(items[mid:], cmp)
return merge(left, right, cmp)


def merge(items1, items2, cmp=lambda x, y: x > y):
"""将两个有序列表组成一个新的有序列表"""
items = []
index1, index2 = 0, 0
while index1 < len(items1) and index2 < len(items2):
if cmp(items1[index1], items2[index2]):
items.append(items2[index2])
index2 += 1
else:
items.append(items1[index1])
index1 += 1
items += items1[index1:]
items += items2[index2:]
return items

冒泡排序

说明

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。

图解

时间复杂度

O(n^2), 即平方时间复杂度

代码实现

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
def bubble_sort(origin_items):
"""判断特殊情况(差一个数就有序呢)"""
items = origin_items[:]
for i in range(1, len(items)):
swapped = False
for j in range(0, len(items) - i):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if not swapped:
break
return items

from operator import gt
def bubble_sort(origin_items, *, cmp=gt):
"""可以比较类对象 *之后是命名关键字参数,之前是位置参数"""
items = origin_items[:]
items_len = len(items)
for i in range(1, items_len):
swapped = False
for j in range(0, items_len - i):
if cmp(items[j], items[j + 1]):
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if not swapped:
break
return items

def bubble_sort(origin_items, *, cmp=lambda x, y: x > y):
"""加上搅拌排序, 正向再反向"""
items = origin_items[:]
for i in range(1, len(items)):
swapped = False
for j in range(i - 1, len(items) - i):
if cmp(items[j], items[j + 1]):
items[j + 1], items[j] = items[j], items[j + 1]
swapped = True
if swapped:
swapped = False
for j in range(len(items)- i - 1, i - 1, -1):
if cmp(items[j - 1], items[j]):
items[j], items[j - 1] = items[j - 1], items[j]
swapped = True
if not swapped:
break
return items
"""
注:
1. 初始冒泡程序
2. 对其进行开头检测, 若遇到已经排好序的情况break
3. 对其进行末尾检测, 若遇到已经排好序的情况break
4. 解耦合, 通过函数对数据进行比较, 默认用lambda x,y: x>y(对类的实例的进行比较可以使用__gt__)
5. *符号其分界作用, 它之后为命名关键字参数, 前面为位置参数
"""

选择排序

说明

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

图解

selectSort

时间复杂度

O(n^2), 即平方时间复杂度

代码实现

1
2
3
4
5
6
7
8
def select_sort(origin_items, cmp=lambda x, y: x > y):
"""选择排序"""
items = origin_items[:]
for i in range(len(items)):
for j in range(i, len(items)):
if items[i] > items[j]:
items[i], items[j] = items[j], items[i]
return items
-------------end-------------
0%