Python数据结构与算法 （二）

快速排序

伪代码：

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] ## 把右边的值写到左边的空位上
        #print(li，'right')
        while left < right and li[left] <= tmp: ## 只要左右碰上了，就退出
            left += 1
        li[right] = li[left] ## 把左边的值写到右边的空位上
        #print(li,'left')
    li[left] = tmp  # 把tmp归位
li = [5,7,4,6,3,1,2,9,8]
print(li)
partition(li,0,len(li)-1)
print(li)
## soooo cool!!! 学什么医啊，这个多带劲

完整的quick_sort

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] ## 把右边的值写到左边的空位上
        #print(li)
        while left < right and li[left] <= tmp: ## 只要左右碰上了，就退出
            left += 1
        li[right] = li[left] ## 把左边的值写到右边的空位上
        #print(li)
    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)
li = [5,7,4,6,3,1,2,9,8]
quick_sort(li,0,len(li)-1)
print(li)
## 数越大，效率越能体现出来

有一些关于装饰器的神奇操作并不是很懂
ps python中递归的深度有限制，默认不超过999，但可以修改

比如：
import sys
sys.setrecursionlimit(100000)

快速排序的最坏情况：第一个数就是最大数，

二叉树的存储方式（顺序存储方式）

堆：

撸省长的代码

def sift(li,low,high):  ## 只撸省长
    """
    :param li: 列表
    :param low: 堆顶的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    """
    i = low  ## i最开始指向根节点
    j = 2*i +1 ## 左孩子
    tmp = li[low] ## 把堆顶存起来
    while j <= high: ## 只要j位置有数，就一只循环
        if j+1 <=high and li[j+1] > li[j]: # 如果右孩子有，且比左孩子大
            j = j + 1  ## 把j指向j+1
        if li[j] > tmp:
            li[i] = li[j]
            i = j  ## 往下看一次，更新i和j
            j = 2*i +1
        else:       # tmp 更大，把tmp放到i的位置
            li[i] = tmp  ## 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp ## 把tmp放在最后一级叶子节点，当村民

完整实现

def sift(li,low,high):  ## 只撸省长
    """

    :param li: 列表
    :param low: 堆顶的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    """
    i = low  ## i最开始指向根节点
    j = 2*i +1 ## 左孩子
    tmp = li[low] ## 把堆顶存起来
    while j <= high: ## 只要j位置有数，就一只循环
        if j+1 <=high and li[j+1] > li[j]: # 如果右孩子有，且比左孩子大
            j = j + 1  ## 把j指向j+1
        if li[j] > tmp:
            li[i] = li[j]
            i = 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)  ## 因为high的下表不好求，所以一直用最后一个元素代替high，起到限制子堆的作用
    # print(li) 建堆完成
    for i in range(n-1,-1,-1): ## i 指向当前堆的最后一个元素
        li[0],li[i] = li[i],li[0]
        sift(li,0,i-1) ## i-1 是最后一个
##
li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)

时间复杂度
sift：O（nlogn）
python 里面有内置函数 heapq

topK 问题
现在有n个数，设计算法得到前k大的数。（k应用：例如热搜榜单
思路：
排序后切片O(nlogn)
排序lowB三人组 O(kn <- 冒泡、选择、插入)

def sift(li,low,high):
    i = low
    tmp = li[low]
    j = i*2 + 1
    while j <=high:
        if j+1 <=high and li[j] > li[j+1]:
            j = j +1
        if tmp > li[j]:
            li[i] = li[j] ## 不能反过来谢，否者顶点没变，省长没撸下来，只是提升了村长
            i = j
            j = 2*i +1
        else:
            li[i] = tmp
            break
    else:
        li[i] =tmp

def top_k(li,k):
    heap= li[0: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) ## 堆，堆的顶点和止点
    print(heap)
    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(1000))
print(li)

random.shuffle(li)
print(li)
print(top_k(li,10))

实现topK
归并排序

def merge(li,low,mid,high):
    ## 两个有序列表，合并成一个有序列表
    i = low
    j = mid +1
    tmp = []
    while i <= mid and j <= high:  ##两边都有数
        if li[i] < li[j]:
            tmp.append(li[i])
            i += 1
        else:
            tmp.append(li[j])
            j += 1
    ## while执行完
    while i <= mid:
        tmp.append(li[i])
        i += 1
    while j <= high:
        tmp.append(li[j])
        j += 1
    li[low:high+1] = tmp  ## 切片写回去

# li = [2,4,5,7,1,3,6,8]
# merge(li,0,3,7)
# print(li)
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)
li = list(range(1000))
import random
random.shuffle(li)
print(li)
merge_sort(li,0,len(li)-1)
print(li)

递归用的很妙啊

有序的挨个换的都是稳定的，飞着换的都是不稳定的