数据结构与算法【Python实现】(一)查找和基础排序_数据结构python 查找排序

一、汉诺塔问题

def hanoi(n,a,b,c):  #从a经过b移动到c
    if n>0:
        hanoi(n-1,a,c,b) #从a经过b移动到c
        print("盘%d moving from %s to %s" %(n,a,c))
        hanoi(n-1,b,a,c)  #从b经过a移动到c
 
hanoi(2,'A','B','C')

递推式 h(x)=2h(x-1)+1 约等于2的n次方

二、查找

1、顺序查找

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

2、二分法查找

def binary_search(li,val):
    left = 0
    right = len(li) - 1
    while left <= right:  #候选区有值
        mid = (left + right) // 2  #整除2
        if li[mid] == val:
            return mid
        elif li[mid] > val:  #待查找的值在mid左侧
            right = mid - 1
        else:               #待查找的值在mid右侧
            left = mid + 1
    else:
        return None  #没有查找到

时间复杂度：O(logn)

三、排序

初级排序：

1、冒泡排序

原地排序，不需要占用新的内存空间。

列表每两个相邻的数，如果前面比后面大，则交换这两个数；

一趟排序完成后，则无序区减少一个数，有序区增加一个数。

def bubble_sort(li):  #升序排列
    for i in range(len(li)-1):  #第i趟 从0开始
         exchange = False
         for j in range(len(li)-i-1):  #指针，每一趟n-i-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(n^2)

2、选择排序

一趟排序记录最小的数，放到第一个位置

再一趟排序记录列表无序区最小的数，放到第二个位置

……直到排序结束

def select_sort(li):
    for i in range(len(li)-1):  #第i趟
        min_loc = i
        for j in range(i+1,len(li)):  #遍历范围
            if li[j] < li[min_loc]:  #如果是最小的，保存下标到min_loc
                min_loc = j
        li[i],li[min_loc] = li[min_loc],li[i]  #最小值和无序区第一个数交换位置
        print(li)

时间复杂度 O(n^2)

3、插入排序

初始时手里(有序区)只有一张牌

每次从无序区摸一张牌，插入到手里已有牌的正确位置

def insert_sort(li):
    for i in range(1,len(li)):  #表示摸到的牌的下标
        tmp = li[i]
        j = i - 1  #j指的是手里的牌的下标  从右往左遍历
        while li[j] > tmp and j >= 0:  #直到找到比摸到的牌小的牌
            li[j+1] = li[j]  #向右移动一位
            j -= 1
        li[j+1] = tmp
        print(li)

时间复杂度O(n^2)

进阶排序：

4、快速排序

取第一个元素p（第一个元素），使元素p归位

列表被p分程两部分，左边都比p小，右边都比p大

递归完成排序

def partition(li,left,right):#归位函数 一次快排
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:  #从右面开始找到比tmp小的数 放到left的空位
             right -= 1   #往左走一位
        li[left] = li[right]  #把右边的值放入左边空位
 
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]  #把左边的值放入右边空位
    li[left] = tmp  #把原来的值归位
    return left  #放回mid，也就是left或right的值
 
 
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)   #递归调用mid分成的左右两部分

时间复杂度：O(nlogn)   logn以2为底

最坏情况：O(n^2)  选取第一个/最后一个数为枢轴的情况下，当表已经有顺序(正序/倒序)，或列表所有元素相同时

避免方式：可以先把列表打乱，或不选取第一个数为枢轴 改为随机选取第一个要归位的数(枢轴)。但是如果输入的数组最大元素（或者最小元素）被选为枢轴，那最坏的情况就又来了。

虽然是原地排序，但递归需要用到系统栈的空间

空间复杂度： 平均情况 O(logn)  最坏情况 O(n)

5、堆排序

二叉树的存储方式：链式存储方式、顺序存储方式

顺序存储方式：

        父节点 i ，左孩子节点 2i+1， 右孩子节点 2i+2

        孩子节点 i ，父节点 (i-1) // 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 = j + 1   #把j指向右孩子
        if li[j] > tmp:
            li[i] = li[j]  #把大的数移到i的位置
            i = j   #i往下看一层
            j = 2 * i + 1
        else:   #tmp更大，把tmp放到i的位置
            li[i] = tmp  #把tmp放到某一层父节点的位置
            break
    else:
        li[i] = tmp  #j>high后，把tmp放到叶子节点
 
 
def heap_sort(li):
    n = len(li)
    #建立堆
    for i in range((n-2)//2,-1,-1):
        #i代表建立堆的时候调整的部分的根的下标，从n-1的根节点开始，倒序
        sift(li,i,n-1)  #low是调整部分的根节点,将high直接放到最后一个叶子节点
    #建堆完成了  开始出数
    for i in range(n-1,-1,-1):
        #i一直指向堆的最后一个数
        li[0],li[i] = li[i],li[0]  # 最后一个数与堆顶交换
        sift(li,0,i-1)  #对整个堆调整 low是0,当前最后一个数是i-1，i-1是新的high
    #排序完成
 
li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)

时间复杂度：sift过程复杂度折半，为O(logn)；整个堆排序O(nlogn)

实际表现：快速排序好于堆排序

Python堆排序内置模块：heapq

常用函数：

        heapify(x)：建堆(小根堆)

        heappush(heap,item)：为heap增加元素

        heappop(heap)：每次弹出一个最小的数

eg：

import heapq   #q->queue 优先队列（小的先出/大的先出）
import random
 
li = [i for i in 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)

        冒泡/插入/选择排序 O(kn)

使用堆排序：复杂度 O(nlogk)  更快

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

依次向后遍历原列表，对于列表中的元素，如果小于堆顶则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整

遍历列表所有元素后，倒序弹出堆顶

#topk 根据堆排序改动
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 = j + 1   #把j指向右孩子
        if li[j] < tmp:
            li[i] = li[j]  #把小的数移到i的位置
            i = j   #i往下看一层
            j = 2 * i + 1
        else:   #tmp更大，把tmp放到i的位置
            li[i] = tmp  #把tmp放到某一层父节点的位置
            break
    else:
        li[i] = tmp  #j>high后，把tmp放到叶子节点
 
 
def topk(li,k):
    heap = li[0:k]
    for i in range((k-2)//2,-1,-1):
        sift(li,i,k-1)
    #1、建堆
    for i in range(k,len(li)-1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap,0,k-1)
    #2、遍历所有元素
    for i in range(k-1,-1,-1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)
    #3、出数
    return heap
 
 
import random
li = list(range(100))
random.shuffle(li)
 
print(topk(li,10))

6、归并排序

一次归并：假设列表分为两段有序，将其合称为一个有序列表

归并排序——使用一次归并：

（1）分解：将列表越分越小，直至分成一个元素

（2）终止条件：只有一个元素的时候是一定有序的

（3）合并：将两个有序列表归并，列表越来越大

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执行完 两段中肯定有一部分没数了
    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(n)，分解+合并整体：O(nlogn)

空间复杂度：O(n)  开了临时列表存储；递归空间复杂度为O(logn)，可由开的O(n)的了表抵消

快速排序 / 堆排序 / 归并排序总结：

时间复杂度都是O(n)

一般情况下，就运行时间而言：

        快读排序 < 归并排序 < 堆排序

三种排序算法的缺点：

        快速排序：极端情况下效率低

        归并排序：需要额外的内存开销

        堆排序：在快的排序算法中相对较慢

 稳定性：当两个元素值相同时，保证他们的相对位置不变

               <在列表中挨个移动顺序的都是稳定的，不挨个换顺序的是不稳定的>

Python使用的稳定排序 基于归并排序