05_Python-CSDN_排序算法

发布于 更新于 Python , 评论
注：点击此处或下方 以展开或折叠目录

一. 顺序查找

1
2
3
4
5
6
7
8
9
10
● 顺序查找
顺序查找：也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止。
时间复杂度：O(n)

def Linear_search(li, val):     # 注：li列表 ；val待查找的元素
    for ind, v in enumerate(li):       # 注：因为要返回个下标 所以用 enumerate index和值都需要
        if v == val:    # 注：如果v == 我们要找的那个值 那就返回 它的index
            return ind
    else:   # 如果for循环结束后还没有找到 返回None
        return None

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=7
菜鸟教程 Python线性查找
https://www.runoob.com/python3/python-linear-search.html

二. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
● 二分查找
二分查找：又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。

时间复杂度：O(logn)

def binary_search(li, val): # li 列表  val待查找的值
    left = 0
    right = len(li) - 1
    while left <= right:    # 注：循环条件 说明候选区有值
        mid = (left + right) // 2   # 注：中间值(下标) 是整除2
        if li[mid] == val:  # 注：== 找到的情况   每次对比都是对比的li[mid]
            return mid      # 注：返回下标 mid
        elif li[mid] > val:  # 注：代表 待查找的值val在 mid左边
            right = mid - 1  # 注：更新候选区了 这种情况就可以继续循环
        else:               # 注：第3种情况 li[mid] < val  待查找的值在mid右侧
            left = mid + 1   # 注：更新候选区  继续循环
    else:
        return None         # 注：如果找不到的情况 即不满足 left <= right 时

li = [1,2,3,4,5,6,7,8,9]
print(binary_search(li,3))       # 注：调用二分查找 查3

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=8
菜鸟教程 Python二分查找
https://www.runoob.com/python3/python-binary-search.html

三. 冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
冒泡排序：列表每两个相邻的数，如果前面比后面大，则交换这两个数。
时间复杂度：O(n**2)

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

改进：如果冒泡排序中的一趟排序没有发生交换，则说明列表已经有序，可以直接结束算法。
def bubble_sort_1(li):
    for i in range(len(li)-1):
        exchange = False        # 在第i趟那加标志位
        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 # 注：如果有交换 把它识成True  交换这里也是1个标志位
        if not exchange:    # 注：如果每1趟结束后 exchange没有发生交换 (这个在for里面)
            return          # 注：就直接结束掉这个函数

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=12
菜鸟教程 Python冒泡排序
https://www.runoob.com/python3/python-bubble-sort.html

四. 选择排序

1
2
3
4
5
6
7
8
9
10
11
选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
时间复杂度：O(n**2)

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

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=14
菜鸟教程 Python选择排序
https://www.runoob.com/python3/python-selection-sort.html

五. 插入排序

1
2
3
4
5
6
7
8
9
10
11
插入排序：它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度：O(n**2)

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

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=15
菜鸟教程 Python插入排序
https://www.runoob.com/python3/python-insertion-sort.html

六. 快速排序

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
快速排序：快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
时间复杂度：O(nlogn)

# 快速排序-partition函数
def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp: # 从右边找比tmp小的数
            right -= 1          # 往右走一步
        li[left] = li[right]    # 把右边的值写到左边空位上
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]    # 把左边的值写到右边空位上
    li[left] = tmp              # 把tmp归位
    return left     # mid 是 这个函数返回left值的目的

# 快速排序-框架
def quick_sort(li, left, right):
    if left < right:    # 至少2个元素
        mid = partition(li, left, right)    # 这个函数返回left值的目的
        quick_sort(li, left, mid - 1)   # 左边部分
        quick_sort(li, mid + 1, right)  # 右边部分

li = [5,7,4,6,3,1,2,9,8]
quick_sort(li, 0, len(li)-1)

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=16
菜鸟教程 Python快速排序
https://www.runoob.com/python3/python-quicksort.html

七. 堆排序

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
堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
时间复杂度：O(nlogn)

def sift(li, low, high):   # 向下调整函数
    # li：列表
    # low: 堆的根节点位置
    # high: 堆的最后一个元素的位置
    i = low # i最开始指向根节点
    j = 2 * i + 1   # j开始是左孩子
    tmp = li[low]   # 把堆顶存起来
    while j <= high:    # 只要j位置有数
        if j + 1 <= high and li[j+1] > li[j]: # 如果有孩子有并且比较大
            j = j + 1   # j指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j       # 往下看一层
            j = 2 * i + 1
        else:   # tmp更大，把tmp放到i的位置上
            li[i] = tmp # 该语句可省 # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp # 把tmp放到叶子节点上

def heap_sort(li):    # 建堆函数
    n = len(li)
    for i in range((n-2)//2, -1, -1):
        # i表示建堆的时候调整的部分的根的下标
        sift(li, i, n-1)    # 这里不是递归
    #建堆完成了
#---------------------这一步 挨个出数的步骤
    for i in range(n-1, -1, -1):
        # i指向当前堆的最后一个元素
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)  # i-1是新的high

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=22
菜鸟教程 Python堆排序
https://www.runoob.com/python3/python-heap-sort.html

八. 归并排序

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
归并排序：创建在归并操作上的一种有效的排序算法。
时间复杂度：O(nlogn)

def merge(li, low, mid, high):
    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执行完，肯定有一部分没数了
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp

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

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=30
菜鸟教程 Python归并排序
https://www.runoob.com/python3/python-merge-sort.html

九. 希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
希尔排序：希尔排序(Shell Sort)是一种分组插入排序算法。
时间复杂度讨论比较复杂，并且和选取的gap序列有关。

def insert_sort_gap(li, gap):
    for i in range(gap, len(li)):   # i 表示摸到的牌的下标
        tmp = li[i]
        j = i - gap # j指的是手里牌的下标
        while j >= 0 and li[j] > tmp:
            li[j+gap] = li[j]
            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

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=34
菜鸟教程 Python希尔排序
https://www.runoob.com/python3/python-shellsort.html

十. 计数排序

1
2
3
4
5
6
7
8
9
10
11
计数排序：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
时间复杂度：O(n)

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 ind, val in enumerate(count):
        for i in range(val):
            li.append(ind)

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=36
菜鸟教程 Python计数排序
https://www.runoob.com/python3/python-counting-sort.html

十一. 桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
桶排序：首先将元素分在不同的桶中，在对每个桶中的元素排序。
时间复杂度 取决于数据的分布

def bucket_sort(li, n=100, max_num=10000):
    buckets = [[] for _ in range(n)]    # 创建桶
    for var in li:
        i = min(var // (max_num // n), 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

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=37
菜鸟教程 桶排序
https://www.runoob.com/w3cnote/bucket-sort.html

十二. 基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
基数排序：基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
时间复杂度：O(kn)

def list_to_buckets(li, base, iteration):
    buckets = [[] for _ in range(base)]
    for number in li:
        digit = (number // (base ** iteration)) % base
        buckets[digit].append(number)
    return buckets

def buckets_to_list(buckets):
    return [x for bucket in buckets for x in bucket]

def radix_sort(li, base=10):
    maxval = max(li)
    it = 0
    while base ** it <= maxval:
        li = buckets_to_list(list_to_buckets(list_to_buckets(li, base, it)))
        it += 1
    return li

b站视频 路飞IT学城
https://www.bilibili.com/video/BV1mp4y1D7UP?p=39
菜鸟教程 基数排序
https://www.runoob.com/w3cnote/radix-sort.html

Mycpen记录学习历程与受益知识

Mycpen