中国移动 二分类数据集 linux HashMap 物联网项目 Jetson Nano WorldCloud 人脸识别 软件开发 swift angularjs windows file drupal count swagger 河南省普通话考试官网 bootstrap时间轴 录音棚设备一套多少钱 cmd查看mysql版本 ubuntu更改文件夹权限 python生成多个随机数 python正则表达式例子 java集合 安装java环境 java8时间 java数组追加 java格式化字符串 linux镜像安装 js选项卡 丁丁下载 福昕阅读器绿色版 微信砍价软件 早早省 hedit 凯立德下载 ass转srt fabfilter rdpwrap this关键字
当前位置: 首页 > 学习教程  > 编程语言

python学习记录5(查找和排序)

2021/1/28 23:32:03 文章标签:

直接查找 l [1,2,3,4,5,6,7,8,9,10] x int(input("输入想查找的数:")) flag 1 for i in range(0,len(l)):if x l[i]:flag 0print(i)breakif flag 1:print("没有找到")二分查找 def binary_search(l, item):low 0high len(l)-1while l…

直接查找

l = [1,2,3,4,5,6,7,8,9,10]
x = int(input("输入想查找的数:"))
flag = 1
for i in range(0,len(l)):
    if x == l[i]:
        flag = 0
        print(i)
        break
        
if flag == 1:
    print("没有找到")

二分查找

def binary_search(l, item):
    low = 0
    high = len(l)-1
    
    while low<=high:
        mid = (low+high)//2
        if l[mid] == item:
            return mid
        elif l[mid]<item:
            high = mid-1
        else:
            low = mid+1
    return None # 没有找到

插入排序

在列表前端维护一个有序的子列表,并逐个将新元素插入这个子列表

def insertionSort(l):
    for i in range(1,len(l)):
        temp = l[i]
        pos = i
        while pos>0 and l[pos-1]>temp:
            l[pos] = l[pos-1]
            pos-=1
        l[pos] = temp

时间复杂度 O ( n 2 ) O(n^2) O(n2)

快速排序

首先选一个基准,默认选列表中的第一个元素,基准左边的元素小于基准值、右边的元素大于基准值,递归

def partition(l, first, last):
    # 选基准
    privot = l[first]
    left = first+1
    right = last
    flag = True
    while flag:
        # left等于左边第一个大于基准的元素
        while left<=right and l[left]<=privot:
            left = left+1
        # right等于右边第一个小于基准的元素
        while left<=right and l[right]>=privot:
            right = right-1
        #
        if right<left:
            flag = False
        else:
            # 将大于基准的元素换到右边,小于基准的元素换到左边
            temp = l[left]
            l[left] = l[right]
            l[right] = temp
    # 将基准和小于基准的元素交换
    temp = l[first]
    l[first] = l[right]
    l[right] = temp
    # 返回基准的位置
    return right
    
def quickSort(l, first, last):
    if first<last:
        p = partition(l, first, last)
        quickSort(l, first, p-1)
        quickSort(l, p+1, last)

时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

选择排序

每次遍历时寻找最大值,将其放在正确的位置上

def selectionSort(l):
    for i in range(len(l)-1,0,-1):
        m = 0
        for j in range(1,i+1):
            if l[j]>l[m]:
                m = j
        
        temp = l[i]
        l[i] = l[m]
        l[m] = temp

时间复杂度 O ( n 2 ) O(n^2) O(n2)

冒泡排序

比较相邻的元素,将不合适的交换

def bubbleSort(l):
    flag = 1 # 记录这趟遍历是否发生交换
    num = len(l)-1
    while num>0 and flag:
        flag = 0
        for i in range(num):
            if l[i]>l[i+1]:
                flag = 1
                temp = l[i]
                l[i] = l[i+1]
                l[i+1] = temp
        num-=1

时间复杂度 O ( n 2 ) O(n^2) O(n2)

归并排序

将列表一分为二,如果列表为空或只有一个元素认为它有序,否则继续将列表一分为二,递归,当两部分都有序后将列表合并

def mergeSort(l):
    if len(l)>1:
        mid = len(l)//2
        leftlist = l[:mid]
        rightlist = l[mid:]
        
        mergeSort(leftlist)
        mergeSort(rightlist)
        
        # 归并
        i,j,k = 0,0,0
        while i<len(leftlist) and j<len(rightlist):
            if leftlist[i]<rightlist[j]:
                l[k] = leftlist[i]
                i+=1
            else:
                l[k] = rightlist[j]
                j+=1
            k+=1
        while i<len(leftlist):
            l[k] = leftlist[i]
            i+=1
            k+=1
        while j<len(rightlist):
            l[k] = rightlist[j]
            j+=1
            k+=1

时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

堆排序

根节点的值总是大于/小于它的子节点

def heapify(l, n, i): 
    largest = i  
    left = 2*i + 1 
    right = 2*i + 2 
  	
  	# 得到较大元素的下标
    if left < n and l[i] < l[left]: 
        largest = left  
    if right < n and l[largest] < l[right]: 
        largest = right
  
    if largest != i: 
        l[i],l[largest] = l[largest],l[i]  # 交换  
        heapify(l, n, largest) 
  
def heapSort(l): 
    n = len(l) 
  
    # 构建大根堆
    for i in range(n, -1, -1): 
        heapify(l, n, i) 
  
    # 交换元素
    for i in range(n-1, 0, -1): 
        l[i], l[0] = l[0], l[i] # 和堆底元素交换
        heapify(l, i, 0)

时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

计数排序

统计每个数比列表其他数大的次数,次数越多说明这个数越大,反之说明这个数就越小。
将输入的数据值转化为键存储在额外开辟的数组空间中

def countSort(l):
    output = [0 for i in range(256)]  
    count = [0 for i in range(256)]  
    ans = ["" for _ in l]
  
    for i in l: 
        count[ord(i)] += 1
        
    # 对每一个元素,确定出小于它的元素个数 
    for i in range(256): 
        count[i] += count[i-1] 
               
    # 遍历计数列表,依次在新列表中添加对应数量的元素。添加后计数列表中减掉对应的数量。
    for i in range(len(l)): 
        output[count[ord(l[i])]-1] = l[i] 
        count[ord(l[i])] -= 1
  
    for i in range(len(l)): 
        ans[i] = output[i]
                    
    return ans

希尔排序

将列表分成数个子列表,对每一个子列表进行插入排序

def shellSort(l):
    step = len(l)//2  # 步长
    while step>0:
        for start in range(step):
            for i in range(start+step,len(l),step):
                temp = l[i]
                pos = i                
                while pos>=step and l[pos-step]>temp:
                    l[pos] = l[pos-step]
                    pos = pos-step
                l[pos] = temp
        
        step = step//2

拓扑排序

拓扑排序是对深度优先搜索的改进,将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前

# graph = {'u':'v'}
def topoSort(graph):     
    in_degrees = dict((u,0) for u in graph)   #初始化顶点入度为0     
    num = len(in_degrees)     
    for u in graph:         
        for v in graph[u]:             
            in_degrees[v] += 1    #计算每个顶点的入度     
    Q = [u for u in in_degrees if in_degrees[u] == 0]   # 筛选入度为0的顶点     
    seq = []     
    while Q:         
        u = Q.pop()   
        seq.append(u)         
        for v in graph[u]:             
            in_degrees[v] -= 1    #移除其所有出边
            if in_degrees[v] == 0:        
                Q.append(v)          #再次筛选入度为0的顶点
    if len(seq) == num:       #输出的顶点数是否与图中的顶点数相等
        return seq     
    else:         
        return None
    
graph = {'a':'bce', 'b':'f', 'c':'', 'd':'', 'e':'df','f':''}
print(topoSort(graph))

本文链接: http://www.dtmao.cc/news_show_650237.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?