不那么乐的世界

算法1——排序

 Tech  2328  5 分钟

算法入门

课程第一部分 排序

程序等于数据结构+算法

复杂度

时间复杂度

时间复杂度排序

O(1) < O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

快速判定算法复杂度(绝大多数情况):

  • 确定问题规模n
  • 循环减半过程 -> logn
  • k层关于n的循环->nk

复杂情况:根据算法执行过程判端

空间复杂度

空间复杂度: 用来评估算法内存占用大小的式子

递归

递归的两个特点

  • 调用自身
  • 结束条件

汉诺塔问题

n个盘子时:

  1. 把个盘子从A经过C移动到B
  2. 把第n个盘子从A移动到C
  3. 把n-1盘子从B经过A移动到C

def hanoi(n,a,b,c):
    if n > 0:
        hanoi(n-1,a,c,b)
        print("moving form %s to %s"%(a,c))
        hanoi(n-1,b,a,c)


hanoi(2,"A","B","C")

查找问题

顺序查找

def linear_search(li,val):
    for ind,v in enumerate(li):
        if v== val:
            return ind
        else:
            return None

二分查找

def binary_search(li,val):
    left = 0
    right = len(li) - 1
    while left <= right :
        mid = (left + right) // 2
        if li(mid) == val:
            return mid
        elif li(mid) > val:
            right = mid - 1
        elif li(mid) < val:
            left = mid + 1
    return None

列表排序

冒泡排序

  1. 列表每两个相邻的数,如果前面比后面大,则交换这两个数
  2. 一趟排序完成后,则无序区减少一个数,有序区增加一个数

关键点: 趟 无序区数量

def bubble_sort(li):
    for i in range(len(li)- 1):
        exchange = False
        for j in range(len(li) - 1):
            if li[j] > li[j+1]:
                li[j],li[j+1]=li[j+1],li[j]
                exchange = True
        print(li)
        if not exchange:
            return

复杂度 O(n2)

选择排序

  1. 一趟排序记录最小的数,放在第一个位置
  2. 再一趟排序记录列表无序区最小的数,放到第二个位置

关键点:有序区与无序区最小值的位置

def select_sort_simple(li):
    li_new = []
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)

    return li_new

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
        li[i],li[min_loc] = li[min_loc],li[i]
    return li

复杂度 O(n2)

插入排序

  1. 初始时手里(有序区)只有一张牌
  2. 每次(从无序区)摸一张牌,插入到手里已有牌的正确位置
def insert_sort(li):
    for i in range(1,len(li)):
        tmp = li[i]
        j= i -1
        while li[j] > tmp and j >= 0:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp

复杂度 O(n2)

快速排序

  1. 取一个元素p,使元素p归位
  2. 列表被p分成两部分,左边都比p小,右边都比p大
  3. 递归完成排序
def partition(li,left,right):
    tmp = li[left]
    while left<right:
        while left < right and li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]

    li[left] = 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)

复杂度O(nlogn)

堆排序

树与二叉树

树是一种可以递归定义的数据结构 树是由n个节点组成的集合:

  • 如果n=0 ,那么这是一棵空树
  • 如果n>0 ,那存在1个节点作为树的根节点,其他节点可以分为m个集合,每个集合本身又是一棵树 树的一些概念:
  • 根节点,叶子节点
  • 树的深度(高度)
  • 树的度
  • 孩子节点/父节点
  • 子树

二叉树:度不超过2的树

满二叉树:层节点达到最大值 完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树.

二叉树的存储方式

  • 链式存储方式
  • 顺序存储方式

二叉树的顺序存储方式:

  • 父节点和左孩子节点变化下表的关系

    i -> 2i+1

  • 父节点和右孩子节点的编号下标的关系

    i -> 2i+2

堆:一种特殊的完全二叉树结构

大根堆:一棵完全二叉树,满足任一节点都比其他孩子节点大 小根堆:一棵完全二叉树,满足任一节点都比其他孩子节点小

堆的向下调整

当根节点的左右子树都是堆时,可以通过一次向下的调整来将其变换成一个堆. 堆的向下调整性质:

  • 假设根节点的左右子树都是堆,但根节点不满足堆的性质
  • 可以通过一次向下的调整来将其变成一个堆

堆排序过程:

  1. 建立堆
  2. 得到堆顶元素,为最大元素
  3. 去掉堆顶,将堆最后一个元素放在堆顶,此时可通过一次调整重新使堆有序
  4. 堆顶元素为第二大元素
  5. 重复步骤三,直到堆变空
#堆排序

def sift(li,low,high):
    """
    :param li:列表
    :param low:堆的根节点位置
    :param high:堆的最后一个元素的位置
    :return:
    """
    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)
    # 建堆完成
    print(li)

时间复杂度 O(nlogn)

堆的python内部模块的使用

import heapq #q-queue 优先队列

import random

li = list(range(100))

random.shuffle(li)

print(li)

heapq.heapify(li) # 建堆
#print(li)

for i in range(len(li)):
    print(heapq.heappop(li),end=" ,")

topk问题(堆排序)

有n个数,设计算法得到前k大的数(k<N)

思路: 排序后切片 O(nlogn) 排序LowB三人组 O(mn)

堆排序方法

  1. 取列表前k个元素建立一个小根堆.堆顶是目前第k大的数
  2. 依次向后遍历原列表,对于列表中的元素,如果小于堆顶,则忽略该元素;如果大于堆顶,则将堆顶更换为该元素,并且对堆进行一次调整.

复杂度 O(mlogn)

归并排序

假设现在的列表分两段有序,如何将其合成为一个有序列表

这种操作称为一次归并

归并使用:

  • 分解:将列表越分越小,直至分成一个元素
  • 终止条件:一个元素是有序的
  • 合并:将两个有序列表归并,列表越来越大
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 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:
        mid = (low + high)//2
        merge_sort(li,low,mid)
        merge_sort(li,mid+1,high)
        merge(li,low,mid,high)

复杂度 O(nlogn)

python内的sort方法 是基于归并排序的

NB三人组 排序总结

  • 三种排序算法的时间复杂度都是O(nlogn)
  • 运行时间: 快速排序<归并排序<堆排序

三种排序算法的缺点:

  • 快速排序:极端情况下排序效率低
  • 归并排序:需要额外的内存开销
  • 堆排序:在快的排序算法中相对较慢

截屏2021-01-03 下午12.04.03.png

希尔排序

计数排序

对列表进行排序,已知列表中的数范围都在0到100之间.设计时间复杂度为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)

复杂度 O(n)

桶排序

在计数排序中,如果元素的范围比较大(比如在1到1亿之间),如何改造算法

桶排序(Bucket Sort):首先将元素分在不同的桶中,再对每个桶中的元素排序

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)
        #保持桶内的顺序
        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

桶排序的表现取决于数据的分布.也就是需要对不同数据排序时采取不同的分桶策略.

平均情况时间复杂度 O(n+k) 最坏情况时间复杂度 O(n2k) 空间复杂度 O(nk)

基数排序

多关键字排序:加入现在有一个员工表,要求按照薪资排序,年龄相同的员工按照年龄排序

先按照年龄进行排序,再按照薪资进行稳定的排序

def radix_sort(li):
    max_num = max(li) # 最大值
    it= 0
    while 10 ** it<= max_num:
        buckets= [[] for _ in range（10）]
        for var in li:
            digit = (var // 10**it )%10
            buckets[digit].append(var)
        li.clear()
        for buc in buckets:
            li.extend(buc)

        it += 1

github address:

https://github.com/chenbokaix250/ForSomeForMySelf

updatedupdated2021-01-122021-01-12

相关文章：