一.查找和排序算法的python实现

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952

"""
Linear Search
时间复杂度 O(n)
内置列表查找函数index()使用了顺序查找,因为其可能是无序的,所以无法使用二分查找
"""
import random


def linear_search(li, val):
    for index, v in enumerate(li):
        if v == val:
            return index
    return None


li = [random.randint(1,10) for i in range(20)]
print(li)
idx = linear_search(li,5)
print("index : ", idx)

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952

"""
Binary Search
时间复杂度: O(logn)
前提:序列是有序的
"""
import random
from cal_time import *


@cal_time
def binary_search(li, val):
    left, right = 0,len(li)-1
    while left <= right:
        mid = (left + right) >> 1
        if li[mid] < val:
            left = mid + 1
        elif li[mid] > val:
            right = mid - 1
        else:
            return mid
    else:
        return None


li1 = list(range(1,50))
print(li1)
print(binary_search(li1, 33))

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952

"""
LowB 三人组: 冒泡排序,选择排序,插入排序,都是O(n^2)的时间复杂度,效率低,都是原地排序
"""

"""
Bubble Sort
时间复杂度: O(n^2)
列表每两个相邻的数,如果前面比后面大(升序排列),则交换这两个数
一趟完成后,无序区减少一个数,有序区增加一个数
"""

"""
优化:
如果有一趟没有发生任何交换,则认为整个序列都已经排好序了
增加exchange做判断,提前返回
"""
import random


def bubble_sort(li):
    for i in range(len(li)-1):
        exchange = False
        for j in range(len(li)-i-1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1],li[j]
                exchange = True
        if not exchange:
            return


li = [random.randint(0,10000) for i in range(20)]
print(li)
bubble_sort(li)
print(li)

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952

"""
select sort(选择每次遍历的最小值放到前面)
时间复杂度:O(n^2)
每一趟记录无序区最小的数,放到第一个位置,于是有序区+1,无序区-1
然后继续从下一个位置开始遍历记录最小数,放到前面
"""
import random


def select_sort(li):
    for i in range(len(li)-1):
        min_loc = i
        for j in range(i+1,len(li)):
            if li[min_loc] > li[j]:
                min_loc = j
        li[min_loc], li[i] = li[i], li[min_loc]


li1 = [random.randint(1, 1000) for i in range(20)]
select_sort(li1)
print(li1)

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952

"""
Insertion Sort
时间复杂度:O(n^2)
初始时手里(有序)只有一张牌li[0]
每次(从无序区)摸一张牌,插入到自己手里已有牌的正确位置
"""

import random
from cal_time import cal_time


@cal_time
def insert_sort(li):
    for i in range(1,len(li)): # i表示无序区牌的下标
        tmp = li[i]
        j = i - 1 # j表示手里的牌
        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j] # li[j]向后移动一个位置
            j -= 1
        li[j+1] = tmp


li = [random.randint(1,1000) for i in range(20)]
insert_sort(li)
print(li)

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952
"""
NB三人组: 快速排序,堆排序,归并排序,这三个排序复杂度较低,效率高,比较常用
"""

"""
Quick Sort
时间复杂度:O(nlogn)
取一个元素p(一般用第一个元素), 使元素p归位
列表被p分为两部分,左边都比p小,右边都比p大
递归完成排序
"""

"""
1.递归有最大深度问题(python默认最大递归深度为1000),而且函数调用消耗部分资源
  解决方法:使用尾递归优化,或者修改最大递归深度
2.最坏情况:初始序列完全逆序时,时间复杂度退化成O(n^2)
  解决方法:partition时随机找一个位置的数,用来分割左右序列
"""

import random
from cal_time import cal_time
import sys

sys.setrecursionlimit(100000)  # 设置python最大递归深度


def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and tmp <= li[right]:  # 从右边找比tmp小的数
            right -= 1  # 往左走一步
        li[left] = li[right]  # 把右边小于tmp的值写到左边空位上
        while left < right and tmp >= li[left]:  # 从左边找比tmp小的数
            left += 1  # 往右走一步
        li[right] = li[left]  # 把左边大于tmp的值写到右边空位上
    li[left] = tmp  # 把tmp归位
    return left


def _quick_sort(li, left, right):
    if left < right:  # 至少两个元素
        mid = partition(li, left, right)
        _quick_sort(li, left, mid - 1)
        _quick_sort(li, mid + 1, right)


@cal_time
def quick_sort(li):
    _quick_sort(li, 0, len(li)-1)


li = list(range(10000))
random.shuffle(li)
# print(li)
quick_sort(li)
# print(li)

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952
"""
Heap Sort
时间复杂度:O(nlogn)  (shift函数复杂度logn,heap_sort函数复杂度n)
与快速排序时间复杂度一样,但实际表现快速排序更好
步骤:
1.实现调整堆的函数shift,具体见shift函数内注释
2.用给定列表建立大顶堆
3.1 把堆顶元素放到列表最后位置i,然后i位置上原有的元素放到堆顶
3.2 用函数shift调整以i-1位置为最后元素的堆为大顶堆
4. 重复步骤3,直到i=0,到此排序完成
"""

import random


def shift(li, low, high):
    """
    向下调整堆,前提是根节点下的两个子树已经是大顶堆了
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    """
    i = low  # i最开始指向根节点
    j = 2*i + 1  # j是i的左子节点
    tmp = li[low]  # 把堆顶元素存起来
    while j <= high:  # 只要j位置有数
        if j + 1 <= high and li[j+1] > li[j]:  # 如果有右节点并且比较大
            j = j + 1
        if li[j] > tmp:
            li[i] = li[j]  # 把j位置的元素提升到i位置上
            i = j  # i指向下一层
            j = 2*i + 1
        else:  # tmp更大,确定了tmp的位置,循环结束
            li[i] = tmp
            break
    else:
        li[i] = tmp  # 循环中的比较tmp都< li[j],把tmp放入最后一层


def heap_sort(li):
    """实现一个大顶堆排序"""
    # 1.建立堆,从最后一个非子节点开始调整每个子堆
    n = len(li)
    for i in range((n-2) >> 1, -1, -1):  # i表示建立堆时需要调整的子堆的根节点下标
        shift(li, i, n-1)  # high = n-1 没有问题,因为堆是完全二叉树,如果任意节点的子节点位置越界,都会大于整个堆的最后节点位置
    print(li)

    # 挨个出数,每一次把堆顶元素(最大)弹出,放到最后,把最后的元素放到堆顶,然后shift重新调整成元素个数为n-1个的大顶堆,
    for i in range(n-1,-1,-1):  # 从最后一个元素向前遍历
        li[0], li[i] = li[i], li[0]  # i指向堆最后一个元素
        shift(li, 0, i-1)  # i-1作为新的high


li1 = list(range(100))
random.shuffle(li1)
print(li1)
heap_sort(li1)
print("堆排序结果:",li1)

#####################################################################
"""
内置模块 heapq 的使用
"""
# import heapq
# li = list(range(100))
# random.shuffle(li)
# print(li)
#
# heapq.heapify(li)  # 建立一个小顶堆
# print(li)
#
# heapq.heappop(li)  # 向外弹出一个最小值
#
# n = len(li)
# for i in range(n):
#     print(heapq.heappop(li), end = ",")
#######################################################
"""
堆排序的应用--topk问题
现在有n个数,设计算法得到前k大的数(k < n)
解决思路:
    1.排序后切片 O(nlogn) 
    2.LowB三人组做部分排序,排k趟,前k个值就满足要求了 O(kn)
    上面两种方式哪个更快,取决于k和logn的大小
    3.堆排序 O(nlogk) 比上面两种效率高
        取列表前k个元素建立一个小顶堆,堆顶就是第k大的数
        依次向后遍历原列表,如果小于堆顶,则忽略;如果大于堆顶,则将堆顶更换为该元素,并且对堆做一次调整
        遍历所有元素后,依次弹出堆顶
"""


def shift_topk(li, low, high):
    """
    向下调整堆,前提是根节点下的两个子树已经是大顶堆了
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    """
    i = low  # i最开始指向根节点
    j = 2*i + 1  # j是i的左子节点
    tmp = li[low]  # 把堆顶元素存起来
    while j <= high:  # 只要j位置有数
        if j + 1 <= high and li[j+1] < li[j]:  # 如果有右节点并且比较小
            j = j + 1
        if li[j] < tmp:
            li[i] = li[j]  # 把j位置的元素提升到i位置上
            i = j  # i指向下一层
            j = 2*i + 1
        else:  # tmp更小,确定了tmp的位置,循环结束
            li[i] = tmp
            break
    else:
        li[i] = tmp  # 循环中的比较tmp都>li[j],把tmp放入最后一层

def topk(li, k):
    heap = li[0:k]
    # 建立堆
    for i in range((k-2)>>1, -1, -1):
        shift_topk(heap, i, k-1)
    for i in range(k, len(li)):
        if li[i] > heap[0]:
            heap[0] = li[i]
            shift_topk(heap, 0, k-1)
    # 挨个出数,给heap中元素排序
    for i in range(k-1,-1,-1):
        heap[0], heap[i] = heap[i], heap[0]
        shift_topk(heap, 0, i-1)
    return heap


li2 = list(range(1000))
random.shuffle(li2)
print("topk结果:", topk(li2,10))

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952
"""
Merge Sort
时间复杂度: O(nlogn) 递归拆分logn,merge时遍历n
两步:拆分和合并
即向下递归的把给定序列拆分成两部分,直到序列元素个数为1后,递归返回并合并序列
python的内置sort函数内部实现基于归并排序实现,之所以不用快排是考虑到快排的最坏情况
"""
"""
一般情况下,就运行效率而言:
    快速排序 > 归并排序 > 堆排序
NB三人组各自缺点:
    快速排序: 最坏情况下时间复杂度退化成O(n^2)
    归并排序:需要额外的内存(merge时需要临时列表)
    堆排序:三者中最慢
稳定性(相同大小的元素排序后保持原来的相对顺序):
    稳定: 冒泡排序,插入排序,归并排序
    不稳定: 选择排序,快速排序,堆排序
"""
import random


def merge(li, low, mid, high):
    """
    把给定的两段有序序列合并
    :param li: 列表
    :param low: 左边序列开头
    :param mid: 左边序列结尾
    :param high: 右边序列结尾
    :return:
    """
    i = low
    j = mid + 1
    ltmp = []
    # 左右两段都有数
    while i <= mid and j <= high:
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    # 处理剩余的元素
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    # 把有序列表ltmp写回li
    li[low:high+1] = ltmp


def merge_sort(li, low, high):
    if low < high:  # 至少有两个元素
        mid = (low + high)//2
        merge_sort(li, low, mid)
        merge_sort(li, mid+1, high)
        merge(li, low, mid, high)


li1 = list(range(1000))
random.shuffle(li1)
print(li1)
merge_sort(li1, 0, len(li1)-1)
print(li1)

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952
"""
Shell's Sort
时间复杂度:和选取的gap序列有关
希尔排序是一种分组插入排序算法
首先取一个整数d1=n/2,将元素分成d1个组,每组相应元素之间距离为d1,在各组内做插入排序
取第二个整数d2=d1/2,将元素分成d2个组,各组内做插入排序
重复上述分组排序过程,直到d=1,即所有元素在同一组内进行插入排序

希尔元素每趟并不使某些元素有序,而是使整体数据越来越接近有序(逆序的数越来越少);最后一趟使得所有数据有序
实际使用时,希尔排序比LOWB三人组快,比NB三人组慢
"""
import random

def insert_sort_gap(li, gap):
    for i in range(gap, len(li)):
        tmp = li[i]
        j = i - gap
        while j >= 0 and li[j] > tmp:
            li[j+gap] = li[j]
            j -= gap
        li[j+gap] = tmp


def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li,d)
        d //= 2

li1 = list(range(1000))
random.shuffle(li1)
shell_sort(li1)
print(li1)

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952
"""
Count Sort
时间复杂度:O(n)
空间复杂度:O(N) N是指元素的最大取值
使用限制多:必须知道列表内元素的取值范围,只能应用在整数上
实现简单,效率高(空间换时间),甚至高过python内置的sort方法
"""
import random


def count_sort(li, max_count=100):
    count = [0 for _ in range(max_count+1)]
    for val in li:
        count[val] += 1
    li.clear()
    for idx, val in enumerate(count):
        for i in range(val):
            li.append(idx)


li = [random.randint(0, 100) for _ in range(1000)]
print(li)
count_sort(li)
print(li)

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952
"""
Bucket Sort
时间复杂度:O(N+k) N是最大取值,k是(N/桶的个数)
效率的具体表现取决于数据的分布,最坏情况下O(kN^2),即数据都集中在一个桶内
空间复杂度:O(N*k)

在计数排序的基础上改造出来的算法
首先将元素分在不同的桶中,再对每个桶中的元素排序(或者插入桶时维护排序)
实际应用不多
"""
import random


def bucket_sort(li, n = 100, max_num = 10000):
    buckets = [[] for _ in range(n)]  # 创建桶(一个二维列表)
    size = max_num // n
    for var in li:
        i = min(var // size, n-1)  # i 表示var放到几号桶中
        buckets[i].append(var)  # 把var加入桶中
        for j in range(len(buckets[i])-1, 0, -1):  # 维护桶内的顺序
            if buckets[i][j] < buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
            else:
                break
    sorted_li = []
    for buc in buckets:
        sorted_li.extend(buc)
    return sorted_li


li = [random.randint(0,10000) for i in range(100000)]
li = bucket_sort(li)
print(li)

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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952
"""
Radix Sort
时间复杂度:O(kn) k最大位数,n列表长度
空间复杂度:O(k+n)
k比logn小的情况下,基数排序比快排快,但随着k的增大,效率不断降低
一般当k比logn大时,基数排序会比快速排序慢

步骤:
    先按照个位数排序
    再按照十位数排序
    ...
    直到最高位,最大数有几位就迭代几次

字符串排序也可以用基数排序
"""
import random


def radix_sort(li):
    max_num = max(li)
    it = 0
    while 10**it <= max_num:
        buckets = [[] for _ in range(10)]
        for val in li:  # 分桶,相当于对当前位上的数字排序
            digit = (val // 10**it) % 10
            buckets[digit].append(val)
        li.clear()
        for buc in buckets:  # 把数按照it+1位上的数字大小顺序写回li
            li.extend(buc)
        it += 1

li = list(range(1000))
random.shuffle(li)
radix_sort(li)
print(li)