Python之计算机算法基础总结（借鉴、整理）、排序算法、查找算法

本文主要是介绍Python之计算机算法基础总结（借鉴、整理）、排序算法、查找算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

排序算法

算法	最优复杂度	最差复杂度	平均复杂度	稳定性
选择排序	O(n²)	O(n²)	O(n²)	不稳定
冒泡排序	O(n)	O(n²)	O(n²)	稳定
插入排序	O(n)	O(n²)	O(n²)	稳定
希尔排序	O(n)	O(n²)	O(n1.3)	不稳定
归并排序	O(nlog n)	O(nlog n)	O(nlog n)	稳定
快速排序	O(nlog n)	O(n²)	O(nlog n)	不稳定
堆排序	O(nlog n)	O(nlog n)	O(nlog n)	不稳定
基数排序	O(d(r+n))	O(d(n+rd))	O(d(r+n))	稳定

ps : 基数排序的复杂度中, r代表关键字的基数, d代表位数, n代表关键字的个数. 也就是说, 基数排序不受待排序列规模的影响.

算法复杂度 : 这里表中指的是算法的时间复杂度, 一般由O(1), O(n), O(logn), O(nlogn), O(n²), ..., O(n!). 从左到右复杂度依次增大, 时间复杂度是指在多少时间内能够执行完这个算法, 常数时间内呢, 还是平方时间还是指数时间等等.
还有个概念叫空间复杂度, 这就指的是执行这个算法需要多少额外的空间. (源数组/链表所占的空间不算)

稳定性 : 算法的稳定性体现在执行算法之前, 若a = b, a在b的前面, 若算法执行完之后a依然在b的前面, 则这个算法是稳定的, 否则这个算法不稳定.

作者：Jerry4me
链接：https://www.jianshu.com/p/f6e35db6bc51
来源：简书

01.选择排序

原理：每次从无序区中找出最小的元素, 跟无序区的第一个元素交换

def selectSort (a):
    for i in range(len(a)-1):
        min = i # 第一次从第一个数开始,第二次从第二个数开始
        for j in range(i+1, len(a)): # 用记录的max数与其他数挨着作比较
            if a[j] < a[min]:
                min = j

        a[i], a[min] = a[min], a[i]
    return a

s = [54, 38, 96, 23, 15, 72, 60, 45, 83]
d = ['Q', 'H', 'C', 'Y', 'P', 'A', 'M', 'S', 'R', 'D', 'F', 'X']
s1=selectSort(s)
print(s1)
d1=selectSort(d)
print(d1)

02.冒泡排序

原理：每次对比相邻两项的元素的大小，不符合顺序则交换

本文链接：https://blog.csdn.net/weixin_43790276/article/details/104033622

def buddingSort(a):
    for i in range(1, len(a)):
        for j in range(0, len(a)-i):
            if a[j]> a[j+1]:
               a[j], a[j+1] = a[j+1], a[j]

    return a


s = [54, 38, 96, 23, 15, 72, 60, 45, 83]
d = ['Q', 'H', 'C', 'Y', 'P', 'A', 'M', 'S', 'R', 'D', 'F', 'X']
s1 = buddingSort(s)
print(s1)
d1 = buddingSort(d)
print(d1)

03.插入排序

原理：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

本文链接：https://blog.csdn.net/weixin_43790276/article/details/104033635

def insertSort(a):
    for i in range(len(a)):
        cur_index = i
        while a[cur_index-1] > a[cur_index] and cur_index-1 >= 0:
            a[cur_index], a[cur_index - 1] = a[cur_index - 1], a[cur_index]
            cur_index -= 1
    return a


s = [54, 38, 96, 23, 15, 72, 60, 45, 83]
d = ['Q', 'H', 'C', 'Y', 'P', 'A', 'M', 'S', 'R', 'D', 'F', 'X']
s1 = insertSort(s)
print(s1)
d1 = insertSort(d)
print(d1)

04.希尔排序

其实就是分组插入排序, 也称为缩小增量排序. 比普通的插入排序拥有更高的性能.

算法思想 : 根据增量dk/gap将整个序列分割成若干个子序列. 如dk = 3, 序列1, 7, 12, 5, 13, 22 就被分割成1, 5, 7, 13和12, 22, 在这几个子序列中分别进行直接插入排序, 然后依次缩减增量dk再进行排序, 直到序列中的元素基本有序时, 再对全体元素进行一次直接插入排序. (直接插入排序在元素基本有序的情况下效率很高)

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
本文链接：https://blog.csdn.net/weixin_41678663/article/details/81811950

def shellSort(a):
    n = len(a)
    gap = n//2
    while gap >= 1:
        # j是需要比较的次数
        for j in range(gap, n):
             # i 是需要控制的索引
            i = j
             # 比较的逻辑和控制i的变换的逻辑
            while (i - gap) >= 0:
                if a[i] < a[i-gap]:
                    #交换
                    a[i], a[i-gap] = a[i-gap], a[i]
                    #修改i
                    i -= gap
                else:
                    break
        #控制间隙的变化
        gap //= 2
    return  a


s = [54, 38, 96, 23, 15, 72, 60, 45, 83]
d = ['Q', 'H', 'C', 'Y', 'P', 'A', 'M', 'S', 'R', 'D', 'F', 'X']
s1 = shellSort(s)
print(s1)
d1 = shellSort(d)
print(d1)

05.归并排序

原理 : 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列并成一个有序的长序列，不断合并直到原序列全部排好序。

本文链接：https://blog.csdn.net/weixin_38358654/article/details/80376200

import sys

class Solution:
    def __init__(self):
        pass
    def getdata(self):
        read_line = sys.stdin.readline().split()
        read_line = list(map(lambda x: int(x), read_line))
        return read_line

    def gbpx(self, data):
        assert hasattr(data, '__len__')
        assert len(data) > 0
        len_data = len(data)
        if len_data == 1:
            return data
        for cur_data_index in range(1, len_data, 1):
            if data[cur_data_index] < data[cur_data_index-1]:
                middle = len_data // 2
                left = data[:middle] #9 5
                right = data[middle:len_data] #2 7
                left_ordeted = self.gbpx(left)
                right_ordeted = self.gbpx(right)
                print((left_ordeted, right_ordeted))
                index_left = 0
                index_right = 0
                while index_left < len(left_ordeted):
                    right_ordeted.append(right_ordeted[0])
                    while index_right < len(right_ordeted)-1:
                        if right_ordeted[index_right] < left_ordeted[index_left]:
                            index_right += 1
                        else:
                            for mov_index in range(index_right, len(right_ordeted), 1):
                                right_ordeted[mov_index], right_ordeted[-1] = right_ordeted[-1],\
                                                                              right_ordeted[mov_index]
                            right_ordeted[index_right] = left_ordeted[index_left]
                            break
                        right_ordeted[index_right] = left_ordeted[index_left]
                    index_left += 1
                    print('tmp:', right_ordeted)
                return right_ordeted
        return data

if __name__ == '__main__':
    so = Solution()
    print(so.gbpx(so.getdata()))

06.堆排序

二叉堆的定义
- 二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：
- 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
- 每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

大顶堆：父结点的键值总是大于或等于任何一个子节点的键值
小顶堆：父结点的键值总是小于或等于任何一个子节点的键值

算法思想：堆排序 = 构造堆 + 交换堆末尾元素与根结点 + 删除末尾结点 + 构造堆 + 交换....依次循环, 由于根结点必定是堆中最大(最小)的元素, 所以删除出来的元素序列也必定是升序(降序)的.

本文链接：https://blog.csdn.net/june_young_fan/article/details/82014081

def max_heapify(heap,heapSize,root):  # 调整列表中的元素并保证以root为根的堆是一个大根堆
    '''
    给定某个节点的下标root，这个节点的父节点、左子节点、右子节点的下标都可以被计算出来。
    父节点：(root-1)//2
    左子节点：2*root + 1
    右子节点：2*root + 2  即：左子节点 + 1
    '''
    left = 2*root + 1
    right = left + 1
    larger = root
    # 小根堆只需要把下面and后面的条件改成：heap[larger] < heap[left] 和 heap[larger] < heap[right]
    # 当然，为了能见名知义，可以把larger换成smaller
    if left < heapSize and heap[larger] < heap[left]:
        larger = left
    if right < heapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:  # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作，交换此时的最大值到root节点
        heap[larger], heap[root] = heap[root], heap[larger]
        # 递归的对子树做调整
        max_heapify(heap, heapSize, larger)


def build_max_heap(heap):  # 构造一个堆，将堆中所有数据重新排序
    heapSize = len(heap)
    for i in range((heapSize -2)//2,-1,-1):  # 自底向上建堆
        max_heapify(heap, heapSize, i)

import random

def heap_sort(heap):  # 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。
    build_max_heap(heap)
    # 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆
    for i in range(len(heap)-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        max_heapify(heap, i, 0)

# 测试
if __name__ == '__main__':
    a = [30, 50, 57, 77, 62, 78, 94, 80, 84]
    print(a)
    heap_sort(a)
    print(a)
    b = [random.randint(1,666) for i in range(666)]
    print(b)
    heap_sort(b)
    print(b)

这里用网上的一张比较直观的图来展示一下堆排序的过程：
111

07.快速排序

算法思想 : 先从数列中取出一个数作为基准数 -> 将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边 -> 再对左右区间重复第二步，直到各区间只有一个数

本文链接：https://blog.csdn.net/weixin_43250623/article/details/88931925

def quick_sort(alist, start, end):
    """快速排序"""
    if start >= end:  # 递归的退出条件
        return
    mid = alist[start]  # 设定起始的基准元素
    low = start  # low为序列左边在开始位置的由左向右移动的游标
    high = end  # high为序列右边末尾位置的由右向左移动的游标
    while low < high:
        # 如果low与high未重合，high(右边)指向的元素大于等于基准元素，则high向左移动
        while low < high and alist[high] >= mid:
            high -= 1
        alist[low] = alist[high]  # 走到此位置时high指向一个比基准元素小的元素,将high指向的元素放到low的位置上,此时high指向的位置空着,接下来移动low找到符合条件的元素放在此处
        # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        alist[high] = alist[low]  # 此时low指向一个比基准元素大的元素,将low指向的元素放到high空着的位置上,此时low指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处

    # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
    alist[low] = mid  # 将基准元素放到该位置,
    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low - 1)  # start :0  low -1 原基准元素靠左边一位
    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low + 1, end)  # low+1 : 原基准元素靠右一位  end: 最后



if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    quick_sort(alist, 0, len(alist) - 1)
    print(alist)

08.基数排序

基数排序的算法复杂度不会因为待排序列的规模而改变. 基数排序又称为桶排序. 基数排序有3个重要概念 :

r : 关键字的基数, 指的是关键字k的取值范围, 十进制数的话, k=10
d : 位数
n : 关键字的个数

基数排序可以分为最高位优先法和最低位优先法，两种方法的结果相同。

最高位优先(Most Significant Digit first)法，简称MSD法。先按最高位进行分桶，合并，一直到最低位，依次进行分桶和合并，便得到一个有序序列。

最低位优先(Least Significant Digit first)法，简称LSD法。先按最低位进行分桶，合并，一直到最高位，依次进行分桶和合并，便得到一个有序序列。

本文链接：https://blog.csdn.net/weixin_43790276/article/details/107398348

# coding=utf-8
def radix_sort(array):
    max_num = max(array)
    place = 1
    while max_num >= 10**place:
        place += 1
    for i in range(place):
        buckets = [[] for _ in range(10)]
        for num in array:
            radix = int(num/(10**i) % 10)
            buckets[radix].append(num)
        j = 0
        for k in range(10):
            for num in buckets[k]:
                array[j] = num
                j += 1
    return array
 
 
if __name__ == '__main__':
    array = [25, 17, 33, 17, 22, 13, 32, 15, 9, 25, 27, 18]
    print(radix_sort(array))

查找算法

算法	最优复杂度	最差复杂度	平均复杂度
顺序查找	O(1)	O(n)	O(n)
折半查找	O(1)	O(log n)	O(log n)
哈希查找	O(1)	O(1)	O(1)

01.顺序查找

算法思想 : 顾名思义就是从数组的0坐标开始逐个查找对比。

本文链接：https://blog.csdn.net/qq_38534627/article/details/80213361

根据python中列表查找某一个数：

aList=[1,2,3,4,5,6,3,8,9]
sign=False                           #初始值为没找到
x=int(input("请输入要查找的整数："))
for i in range(len(aList)):
   if aList[i]==x:
      print("整数%d在列表中，在第%d个数"%(x,i+1))
      sign=True
if sign==False:
   print("整数%d不在列表中"%x)

由列表的遍历不同方式可以写出另一种

aList=[1,2,3,4,5,6,3,8,9]
sign=False
x=int(input("请输入要查找的整数："))
for i in aList:
   if i==x:
      print("整数%d在列表中，在第%d个数"%(x,i))
      sign=True
if sign==False:
   print("整数%d不在列表中"%x)

其实在python中有内置的函数用来查找，如下：有以下几种函数，in ， index（），count（）

aList=[1,2,3,4,5,6,3,8,9]
5 in aList             #查找5是否在列表中
print(aList.index(5))         #返回第一个数据5的下标
print(aList.index(5,4,10))    #返回从下标4到10(不包含) 查找数据5
print(aList.count(5))         #返回数据5的个数

02.二分查找(折半查找）

算法思想 : 在一个有序数组里, 先对比数组中间的数middle与要查找的数num的大小关系

- middle == num : 直接返回
- middle < num : 递归查找数组右半部分
- middle > num : 递归查找数组左半部分

https://blog.csdn.net/fengdu78/article/details/103907560

def halffind(a,c,low,high): 
    mid=(low+high)//2
    if c == a[mid]:
        return mid+1
    elif low>high:
        return False
    
    elif c>a[mid]:
        return halffind(a,c,low+1,high)
    else:
        return halffind(a,c,low,high-1)



if __name__ == "__main__":
    a=[56,52,-96,-53,23,-789,520]   #测试案例
    c=int(input('Please enter the number you want to find:'))
    if c not in a:
        print('当前输入元素不在列表中！')
    else:
        print('The position of the requried number in the list is:')
        answer=halffind(a,c,0,len(a)-1)  
        print(answer)

def binary(list,item):
    list=sorted(list)
    print('排好顺序后是：',list)
    low=0
    high=len(list)-1
    while low<=high:
        mid=(high+low)//2
        find=list[mid]
        if find==item:
            print('\n查找范围[%d-%d]在中间' %(list[low],list[high]))
            return mid
        if find<item:
            print('\n查找左半边...')
            print('查找范围[%d-%d]' %(list[low],list[high]))
            low=mid+1
        else:
            print('\n查找右半边...')
            print('查找范围[%d-%d]' %(list[low],list[high]))
            high=mid-1
    return None

list1=[234,346,56547,8,678,797,978,0,2,21,31,453,534,23423,25435,534,66,35,75756,123,3457,9909,1231,31,344,66677,777]
binary(list1,344)

03.哈希查找

哈希查找需要一张哈希表, 哈希表又称为散列法, 是高效实现字典的方法. 查找速度在O(1), 这说明无论你需要查找的数据量有多大, 他都能在常数时间内找到, 快得有点违背常理吧? 嘿嘿.

哈希表几个重要的概念：

负载因子：α = n / m (n为键的个数, m为单元格个数), 负载因子越大, 发生冲突的概率则越大
哈希函数：
- 哈希函数是指你把一样东西存进去之前, 先对它的key进行一次函数转换, 然后在通过转换出来的值作为key, 把你要存的东西存在表上.

碰撞解决机制：

再哈希法 : 使用其他的哈希函数对key再次计算, 直到没有发生冲突为止(计算量增加, 不推荐)
线性勘测法：通过一个公式, 算出下一个地址, (存储连续的)
二次探测法：生成的地址不是连续的, 而是跳跃的.

如果两样东西通过哈希函数算出来的key相同怎么办? 东西怎么存? 这个时候就是碰撞检测机制派上用场的时候
方法一：开散列法, 也称分离链法 : 即相当于在数组中每个格子是一个链表, 只要发生冲突就把后来的value拼接在先来的value后面, 形成一条链.

方法二：闭散列法, 也称开式寻址法 :

可以这么说, 哈希函数设计得越好, 冲突越少, 哈希表的效率就越高.

哈希法：使用哈希函数来计算一个键值所对应的地址，进而建立哈希表格然后依靠哈希函数来查找各个键值存放在表格中的地址，查找速度与数据多少无关，在没有碰撞和溢出的情况之下，一次读取即可完成，哈希函数还具有保密的特性不知道哈希函数便无法查找到数据。

除留余数法：最简单的哈希函数是将数据除以一个常数之后，取余数作为索引，函数为：h(key)=key mod b ,b为一个适当的常数，最好是质数。例如对65,67,70,33,99,48,12取13作为b,建立哈希表。h(65)=0,h(67)=2,h(70)=5,h(33)=7,h(99)=8,h(48)=9,h(12)=12

平方去中法：先计算数据的平方，再取中间的某段数字作为索引。例如：将12，65，70，99，33,67，51作为数据，再取百位数和十位数作为键值，分别为：f(12)=14，f(65)=22，f(70)=90，f(99)=80，f(33)=08，f(67)=48，f(51)=60。

折叠法：在将数据换成一串数字之后，先将这串数字换成几个部分，再把它们加起来，就可以计算出这个键值的桶地址，例如若有一个数据转化成数字之后为2365479125443,若以每4个数字为一个部分则可以拆分为2365,4791,2544,3将这4组数字加起来就是9703，即为桶地址。

在哈希法中，当标识符要放入某个桶（bucket,哈希表中储存数据的位置）时，若该桶已经满了，就会发生溢出（overflow），另一方面哈希法的理想情况是经过哈希函数运算之后所有数据都有不同的值，但是现实情况是即使所有的关键字段都不同，经过哈希运算之后还是有可能得到相同的地址，于是就发生了碰撞问题。处理碰撞可以采用探测法选出空地址或者不断地更换哈希函数。

04.插入查找

按照数据位置的分布利用公式预测数据所在的位置，再度以二分法的方式逐渐地逼近，使用插值法是假设数据平均分布在数组中，而每一项数据的差距相当接近或者一定的距离比例

https://blog.csdn.net/qq_15537309/article/details/96426127

def binary(list,item):
    list=sorted(list)
    print('排好顺序后是：',list)
    low=0
    high=len(list)-1
    while low<=high:
        mid=low+(item-list[low])//(list[high]-list[low])*(high-low)
        find=list[mid]
        if find==item:
            print('\n查找范围[%d-%d],在中间' %(list[low],list[high]))
            return mid
        if find<item:
            print('\n查找左半边...')
            print('查找范围[%d-%d]' %(list[low],list[high]))
            low=mid+1
        else:
            print('\n查找右半边...')
            print('查找范围[%d-%d]' %(list[low],list[high]))
            high=mid-1
    return None

list1=[234,346,56547,8,678,797,978,0,2,21,31,453,534,23423,25435,534,66,35,75756,123,3457,9909,1231,31,344,66677,777]
binary(list1,3457)

需要了解的名词

旅行商问题
- 哈密顿回路 : 经过图中所有顶点一次仅一次的通路

凸包问题

凸集合 : 平面上一个点集合, 任意两点为端点的线段都属于该集合
凸包 : 平面上n个点, 求包含这些点的最小凸多边形
极点 : 不是线段的中点

曼哈顿距离
- dM (p1, p2) = |x1 - x2| + |y1-y2|
深度优先查找(DFS) : 用栈实现
广度优先查找(BFS) : 用队列实现
拓扑排序( 无环有向图 )
- 深度优先查找 -> 记住顶点(出栈)的顺序, 反过来就是一个解
- 找源, 它是一个没有输入边的顶点, 然后删除它和它出发的所有边, 重复操作直到没有源为止.

2-3树

2节点 : 只包含1个键和2个子女
3节点 : 包含2个键和3个子女
高度平衡<所有叶子节点必须位于同一层>
可以包含两种类型的节点

BST树 :

也称为B树
二叉查找树, 随着插入和删除的操作有可能不是平衡的.

AVL树 :

平衡二叉查找树
左右子树深度只差不超过1
左右子树仍为平衡二叉树

RBT红黑树 :

一种平衡二叉树
跟AVL树类似, 通过插入和删除操作时通过特定操作保持二叉查找树的平衡, 从而有较高的查找性能.
相当于弱平衡的AVL数(牺牲了一定次数的旋转操作), 若查找 > 插入/删除, 则选择AVL树; 若差不多则选择红黑树

哈夫曼树

自由前缀变长编码
叶子之间的加权路径长度达到最小
哈夫曼编码

几种图论的算法

Warshall算法

选取一个顶点作为桥梁, 考察所有顶点是否可以通过该桥梁到达其他的顶点
求有向图的传递闭包
算法思想

Floyed算法

选取一个顶点作为桥梁, 考察所有顶点是否可以通过该桥梁到达其他的顶点, 如果能, (如a到c, b为桥梁)再比较Dab + Dbc < Dac ? 如果成立, 则更新最短距离
求每个顶点到各个顶点的最短路径
算法思想

Prim算法

首先找出S = {你选取的一个顶点}, 然后添加另一顶点(该顶点∈(V-S)且它们两顶点之间的边的权重最小, 直到S = V.
求无向带权连通图的最小生成树(每次按节点递增)
算法思想

Kruskal算法

第一次选出权重最小的边加入, 之后每次选择权重最小的边加入并不构成环.
求无向带权连通图的最小生成树(每次按边递增)
算法思想

Dijkstra算法

找一个源(起点), 之后求出离起点最近的点的距离; 然后第二近, 以此类推(允许通过其他点为中间点), 设置顶点集合S, 只要源到该顶点的距离已知就把该顶点加入到S中. 直到S包含了V中所有顶点.
求有向带权图中一个"源"到所有其他各顶点的最短路径

这篇关于Python之计算机算法基础总结（借鉴、整理）、排序算法、查找算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Python教程

Python之计算机算法基础总结（借鉴、整理）、排序算法、查找算法

排序算法

01.选择排序

02.冒泡排序

03.插入排序

04.希尔排序

05.归并排序

06.堆排序

07.快速排序

08.基数排序

查找算法

01.顺序查找

02.二分查找(折半查找）

03.哈希查找

04.插入查找

需要了解的名词

几种图论的算法

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯