Python数据结构与算法6

目录

topk问题

思路

代码实现

 时间复杂度

归并排序

思路

有序列表合并代码实现

 无序列表合并代码实现

 时间复杂度

希尔排序

思路

代码实现

时间复杂度

---

topk问题

思路：

1.取前k个元素建立一个小根堆，堆顶就是目前第k的的数

2.依次向后遍历源列表，根据大小替换元素，并调整堆

3.倒序弹出堆顶

代码实现：

def sift(li,low,high): #low根节点  high最后一个节点
    i=low     #i开始指向根节点
    j=2*i+1  #j是左孩子
    tmp=li[low] #堆顶的值
    while j<=high:
        if j+1<=high and li[j+1]>li[j]:
            j=j+1
        if li[j]>tmp:
            li[i]=li[j]
            i=j
            j=2*i+1
        else:
            li[i]=tmp
            break;
    else :
        li[i]=tmp
 
def topk(li,k):
    heap=li[0:k]   #取前k个元素建立一个小根堆，堆顶就是目前第k的的数
    for i in range((k-2)//2,-1,-1):
        sift(heap,i,k-1)
    for i in range(k,len(li)-1):  #依次向后遍历源列表，根据大小替换元素，并调整堆
        if li[i]>heap[0]:
            heap[0]=li[i]
            sift(heap,0,k-1)
    for i in range(k-1,-1,-1):  #倒序弹出堆顶
        heap[0],heap[i]=heap[i],heap[0]
        sift(heap,0,i-1)
    return heap
import random
li=list(range(100))
random.shuffle(li)
print(topk(li,10))
 
 
 

 时间复杂度：

o(nlogn)

归并排序

思路：

1.首先一次合并，前提是两边的列表都有序，将左右两边的数字挨个比较，顺序加入一个列表

2.两边的列表无序时，使用递归排好序，再使用1中的方法

有序列表合并代码实现：

def merge(li,low,mid,high):
    i=low
    j=mid+1
    ltmp=[]
    while i<=mid and j<=high:  #左右两边都有数
        if li[i]
            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
    li[low:high+1]=ltmp
    return li
li=[2,4,5,7,1,3,8,9]
print(merge(li,0,3,7))

 无序列表合并代码实现：

def merge_sort(li,low,high):
    if low
        #至少有两个元素
        mid=(low+high)//2
        merge_sort(li,low,mid)
        merge_sort(li,mid+1,high)
        merge(li,low,mid,high)
li=list(range(10))
import random
random.shuffle(li)
print(li)
merge_sort(li,0,len(li)-1)
print(li)

 时间复杂度：

o(nlogn)

希尔排序

思路：

1.实质是一种分组插入排序

2.通过设置gap将列表分组，延用插入排序的代码，但gap代替了两个数之间的距离

3.当gap<1时排序结束

代码实现：

#实质是一种分组插入排序
def insert_sort_gap(li,gap):
    for i in range(gap,len(li)):
        tmp=li[i]
        j=i-gap
        while li[j]>tmp and j>=0:
            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
 
li=list(range(10))
import random
random.shuffle(li)
print(li)
shell_sort(li)
print(li)
 

 时间复杂度：

较为复杂，与gap的选取有关