排序和搜索（1）排序、堆、最大（最小索引堆）

客官°小女子只卖身不卖艺 2022-02-22 04:50 298阅读 0赞

## 排序与搜索 ##

排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定顺序进行排列的一种算法。  
**排序算法的稳定性**  
稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。  
如：

> (4, 1) (3, 1) (3, 7)（5, 6）

在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：

> (3, 1) (3, 7) (4, 1) (5, 6) （维持次序）  
> (3, 7) (3, 1) (4, 1) (5, 6) （次序被改变）

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，（比如上面的比较中加入第二个标准：第二个键值的大小）就会被决定使用在原先数据次序中的条目，当作一个同分决赛。  
**一、六种排序方法**  
**1、冒泡排序**  
是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。  
冒泡排序算法的运作如下：

*  比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 *  针对所有的元素重复以上的步骤，除了最后一个。
 *  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。  
    冒泡排序的分析  
    交换过程图示(第一次)：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]  
    那么我们需要进行n-1次冒泡过程，每次对应的比较次数如下图所示：  
    ![在这里插入图片描述][20190408213412812.png]  
    算法实现：

#冒泡排序1：
    """设置两个游标，i和j，j从最后面固定不懂，然后i从游标的前一个向list的最开始元素移动，如果前面的数比后面的大则交换两个数，循环一遍后，j游标指向的数是0-j上最大的，这时游标j-1，
    （2）重复上面的过程，直到j=1
    （3）这时list中的最大数永远在后面
    """
    def Bubble(list):
        for j in range(len(list)-1,0,-1):
            for i in range(j-1,-1,-1):
                if list[i]>list[j]:
                    list[j],list[i]=list[i],list[j]
        return list
    list1= [54,26,93,17,77,31,44,55,20]
    Bubble(list1)
    法2：
    """
    方法2只是游标从最前面开始，把最小的数放在最前面跟方法1，类似
    """
    def Bubble2(list):
        for i in range(len(list)-1):
            for j in range(i+1,len(list)):
                if list[i]>list[j]:
                    list[j],list[i]=list[i],list[j]
        return list
    
    list1= [54,26,93,17,77,31,44,55,20]
    Bubble(list1)

![在这里插入图片描述][20190408221803726.png]  
时间复杂度：  
最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）  
最坏时间复杂度：O(n2)  
稳定性：稳定  
**2、选择排序**  
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的第2个位置。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。  
其排序过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]  
代码：  
错误代码：

alist = [54,226,93,17,77,31,44,55,20]
    def choose_sort(list):
        length=len(list)
        for i in range(length-1):
            for j in range(i+1,length):
                min_index=i
                if list[j]<list[i]:
                    min_index=j
                else:
                    pass
            print(list[min_index])
        return list
    choose_sort(alist)

第一次写时，排序一直不正确，仔细看会发现，我们希望通过min\_index这个变量保留住j，可是当我们第一次找出list\[j\]<list \[i\]的数时，这时最小的数已经变为list\[j\],但我们却仍然比较的是list\[i\]这个数，表明我们的第二个循环其实是为了找出，其中最后一个比list\[i\]小的数，所以应该把代码改为：

import copy
    alist = [54,226,93,17,77,31,44,55,20]
    def choose_sort(list):
        length=len(list)
        for i in range(length-1):
            #设最小数的索引为min_index并从第0个数开始找起
            min_index=i    
            for j in range(i+1,length):
                if list[j]<list[i]:
                    min_index=j
            print(min_index)
            if min_index != i:
                list[min_index],list[i]=list[i],list[min_index]
        return list
    choose_sort(alist)

时间复杂度  
最优时间复杂度：O(n2)  
最坏时间复杂度：O(n2)  
稳定性：不稳定（考虑升序每次选择最大的情况）  
如：  
list=\[26,16,17,15,26,11,10,9\]  
我们按照升序排列，最大的放最后面，这时第一个26排到了最后，但是第二个26却排到了倒数第二个位置，这时两个26原有的顺序就变了。  
**3、插入排序**  
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过将列表分成两个部分，有序序列和无序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]  
代码：

def insert_sort(alist):
        """插入排序"""
        for i in range(1,len(alist)):
            while i>0:
                if alist[i]<alist[i-1]:# 如果前面的数比alist[i]大，就交换两者的位置
                    alist[i],alist[i-1]=alist[i-1],alist[i]
                    i=i-1
                else: #如果前面的数比alist[i]大，证明不用循环，直接跳出
                    break
        return alist
    alist = [54,26,93,17,77,31,44,55,20]
    insert_sort(alist)

![在这里插入图片描述][20190409165932574.png]  
通过例子帮助大家更好理解这个排序的过程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]  
时间复杂度：

*  最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）  
    插入排序和冒泡和选择排序不同，这个和序列的本身的排序有关
 *  最坏时间复杂度：O(n2)
 *  稳定性：稳定

**4、希尔排序**

(1)定义  
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。  
(2) 希尔排序过程  
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。由于之前的步长将其中部分数组已经排好序了，所以每次进行插入排序时比较会变少。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 4]  
代码：

def shell_sort(list1):
        n=len(list1)
        gap=n//2
        group=n//gap+1
        while gap>0:
            for i in range(group):
                #对每组数据进行一个
                j=i+gap
                while j<n:
                    for z in range(j,0,-gap):
                        if list1[z-gap]>list1[z]:
                            list1[z],list1[j]=list1[j],list1[z]
                        else:
                            break
                    j+=gap
            gap=gap//2
            if gap!=0: #每次重新分组，但是要注意gap不能等于0，因为gap等于1时
            #会走一遍循环，此时1//2=0,此时分组会失效所以需要加上这一步
                group=n//gap+1
        return list1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 5]  
时间复杂度：  
会跟据步长的不同而变化，最坏的情况下为O(N\*\*2)  
**5、快速排序**  
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
步骤为：

*  从数列中挑出一个元素,称为基准，一般选取第一个元素
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
 *  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。  
    递归的最底部情形，是数列的大小是零或一
 *  这时再进行归并，归并完成后数组便排序好了  
    方法1：

def quick_sort(self,list1):
         if not list1: #如果为空集，直接返回
             return []
         if len(list1)==1:
             return list1
         pivot=list1[0]
         left=self.quick_sort([i for i in list1[1:] if i<pivot])
         right=self.quick_sort([i for i in list1[1:] if i>=pivot])
         return left+[pivot]+right

基本思路为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 6]  
方法2：我们可以将这个代码分为两部分一个是将数组快速排序的过程，采用指针交换的方法，第二个是递归的过程，代码可以写成：（这种方法和上面方法的不同之处在于利用指针法进行排序，当扫描的数等于中间的数时我们可以采取交换或者不交换，但是上面的数组归并的方式便不行，但是两者的原理都是一样的。）

a=[2,3,2,4,6,7,4,2,3,4]
     """分割函数，以数组的第1个元素为基准点，将小于基准点数都放在基准点左边，
     大于基准点的数放在基准点右边,返回基准点索引"""
    def partion(arr,l,r):
        if l<r:
            i=l+1
            j=r
            mid=a[l]
        while i<j:
            if a[i]>mid:
                #将这个较大的数换给j
                a[j],a[i]=a[i],a[j]
                j-=1
            else:
                i+=1
            if a[i]>mid:
                i-=1
            else:
                j+=1
            a[l],a[i]=a[i],a[l]
        return i
    #print(partion(a,0,len(a)-1))
    #对arr[l,r]这个区间进行快排
    #归并过程
    def quick_sort(arr,l,r):
        if l>=r:
            return #相当于程序运行结束
        p=partion(arr,l,r)
        print(p)
        quick_sort(arr,l,p-1)
        quick_sort(arr,p+1,r)
        return arr
        #print(arr)

一般来说，快速排序是生成了一棵树，当数组为完全顺序的时候就相当于，我们对数组整个进行了扫描，此时快排就相当于完全遍历数组。此时树的深度还是n，那么排序的的时间复杂度变为O(n\*\*2).  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 7]  
那么有没有方法可以改进呢，答案是有的，我们可以不用使得基准元素每次都是最左侧的元素，那么这时生成的树便不会是n。  
**改进2**：  
我们的基准比较值变为v=np.random.random\_integers(0,len(数组))，然后a\[v\]，随机抽取一个数作为基准值。然后将第一个数和选取的数进行互换，最后继续重复上面的操作即可。这样便能防止，生成的树过于单一。  
改进3：  
我们虽然考虑了数组是近乎顺序的情况，但是没有考虑过数组重复值较多的情况，如我们要排序的数组是\[0,10\]生成的100w个随机数，那么这个数组会存在很多的随机值，这代表我们在进行以基准值分裂操作时，可能生成的树及其不均衡，那么我们就要想办法解决这种不均衡问题。  
如：  
![在这里插入图片描述][2019041617393683.png]  
我们发现当有大量重复键值时，我们会将等于基准值的这个  
元素全部放入左边，或者全部放入右边，有没有什么办法这个元素均匀放在两边呢。  
**改进3**

import numpy as np
    def partion2(arr,l,r):#对l,r这个闭区间的元素进行划分排序
        v=int(np.random.random_integers(l,r,size=1))
        print(v)
        mid=arr[v]
        print(mid)
        #交换两者
        arr[v],arr[0]=arr[0],arr[v]
        print(arr)
        i=l+1
        j=r  #arr[l,..i]<mid;arr[j,...r]>=mid
        while True:
            #当i等于j时，i还是可能移动
            while i<=j  and arr[i]< mid:
                i+=1
            #同理当i等于j时，j还是可能移动，但i=j时不能同时移动，因为这时必然有一个数不满足条件
            while j>=i and arr[j]>mid:
                j-=1
            if i >= j:
                    break
            while arr[i]>=mid and arr[j]<=mid:
            #如果arr[i]和arr[j]相等，则不交换，否则进行交换
                if arr[i]==arr[j]:
                    i+=1
                    j-=1
                else:
                    arr[j],arr[i]=arr[i],arr[j]
                    i+=1
                    j-=1
        arr[j],arr[0]=arr[0],arr[j]
        return arr
    a=[2,2,3,4,1,2,3,2,2]
    print(partion2(a,0,len(a)-1))

**改进4**  
三路快速排序：  
![在这里插入图片描述][20190417091943997.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 8]  
可以通过画图来实现上面的排序算法，思路会清晰很多。

#三路排序
    def partion(arr,l,r):
        v = int(np.random.random_integers(l, r, size=1))
        mid = arr[v]
        print(mid)
        # 交换两者
        arr[v], arr[0] = arr[0], arr[v]
        lt = l  # arr[l+1....lt]<v,一开始为空值
        gt = r + 1  # arr[gt...r]>v
        i = l + 1  # arr[lt+1,i)==v #i用来遍历整个数组
        if len(arr)==1:
            return arr
        while i < gt:
            if arr[i] == mid:
                i += 1
            elif arr[i] < mid:
                arr[i], arr[lt + 1] = arr[lt + 1], arr[i]
                lt += 1
                i += 1
            else:
                arr[gt - 1], arr[i] = arr[i], arr[gt - 1]
                gt -= 1
        arr[lt], arr[l] = arr[l], arr[lt]
        return lt,gt
    a=[2,2,3,4,1,2,3,2,2]
    print(partion(a,0,len(a)-1))
    def quick_sort3(arr,l,r):
        #当l,r中只有一个数的时候，代表r-l等于1，而当l=r时，证明这时arr中已经没有数了，这时不能继续进行这种排序和递归
        #我们要学会考虑极端的情况 比如arr中只有1个或者两个数
        if l>=r:
            return
        lt,gt=partion(arr,l,r)
        quick_sort3(arr,l,lt)
        quick_sort3(arr,gt,r)
        return arr
    a=[2,2,3,4,1,2,3,2,2]
    print(quick_sort3(a,0,len(a)-1))

我们在进行程序测试时一定要注意特殊情况，如上面进行三路排序的partion时，忘记考虑了数组中只有一个元素的这种情况，所以我们下次做时要多考虑这种情形 <\\font>

**6、归并排序**  
如 我们要将lis1=\[8,6,5,7,1,3,6,2\]进行归并排序,那么我们首先要采取分的方式，即将整个数组分为不能分的小整体，这时我们再将整个小数组进行排序合并，由于分的数组最小为1，这时这个数组已经是有序的了。我们合并时只要采取比较合并即可。那么什么叫比较合并，即对左数组left=\[1,2,3,4\]为一个有序数组，右数组right=\[2,4,5,6\]为一个有序数组，我们将两个数组合并在一起还是一个有序数组，list=\[1,2,2,3,4,4,5,6\].  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 9]  
代码：

'''
    6、归并排序
    将数组每次都1分为2，左边的为左数组，右边的为右数组，分到无法再分时再进行合并,注意进行合并时
    左右数组都为有序数组，最终形成有序列表
    '''
    def merge(list1,list2):
        n1=len(list1)
        n2=len(list2)
        if n1==0 or n2==0:
            return list1+list2
        arr=[]
        i,j=0,0
        while True:
            #print(arr)
            if list1[i]<list2[j]:
                arr.append(list1[i])
                i+=1
            else:
                arr.append(list2[j])
                j+=1
            if i==n1:
                arr+=list2[j:]
                break
            if j==n2:
                arr+=list1[i:]
                break
        return arr
    merge([1,2,3,4,5],[2,3,4,5])
    merge([1],[2])
    def part_merge_sort(list1):
        if len(list1)<=1:
            return list1
            #二分分解
        mid=int(len(list1)/2)
        left=part_merge_sort(list1[:mid])
        print(left)
        right=part_merge_sort(list1[mid:])
        print(right)
        return merge(left, right)
    part_merge_sort(list1)

难点：  
这个题有两个难点，  
一是merge函数对于merge来说我们要考虑数组越界的问题，即l,r<=len(left)或者len(right)  
二是 递归的逻辑理解:我们在进行递归时，return没有结束，函数便会一直没有执行完，此时我们持续的执行下去，直到子函数执行完。这个题的逻辑图如下所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 10]  
这个树的生成也是按程序进行的如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 11]  
从上面也可以看出递归的程序没有完结，递归便不会结束  
而我们的merge()函数则必须要两边的递归都完成才会进行操作  
时间复杂度：n\*O(logn)

**补充所有排序总结**：

#六种排序算法
    alist=[1,2,4,23,2,32,3,4,3,34,3,43,2,5,8,6,4]
    def maopao(list1):
        n=len(list1)
        for i in range(n-1):
            for j in range(i,n):
                if list1[j]<list1[i]:
                    list1[j],list1[i]=list1[i],list1[j]
        return list1
    maopao(alist)
    #2、插入排序
    #假设前面第一个数为一个自增数列，后面第二个数开始向前面插入，
    #不断循环，从第三个数开始向前两个数进行插入
    def insert_sort(list1):
        n=len(list1)
        for i in range(1,n):
            while i>0:
                if list1[i]<list1[i-1]:
                    list1[i],list1[i-1]=list1[i-1],list1[i]
                    i-=1
                else:
                    break
        return list1
    alist=[1,2,4,23,2,32,3,4,3,34,3,43,2,5,8,6,4]
    insert_sort(alist)                
    
    alist=[1,2,4,23,2,32,3,4,3,34,3,43,2,5,8,6,4]
    insert_sort(alist)   
    #3、选择排序
    #先从n个数中选择一个放在第一个，再从剩余n-1个数中选择一个放入倒数第二个...
    #不断循环直到整个数列为递增数列为止
    def choose_sort(list1):
        n=len(list1)
        for i in range(n-1):
            for j in range(i,n):
                if list1[j]<list1[i]:
                    list1[j],list1[i]=list1[i],list1[j]
        return list1
    alist=[1,2,4,23,2,32,3,4,3,34,3,43,2,5,8,6,4]
    choose_sort(alist)   
    #4、归并排序
    class solution:
        def merge(self,left,right):
            n1=len(left)
            n2=len(right)
            result=[]
            i,j=0,0
            while True:
                if i==n1:
                    result.extend(right[j:])
                    break
                if j==n2:
                    result.extend(left[i:])
                    break
                if left[i]<right[j]:
                    result.append(left[i])
                    i+=1
                else:
                    result.append(right[j])
                    j+=1
            return result
        def merge_sort(self,list1):
            if len(list1)==1:
                return list1
            num=len(list1)//2
            left=self.merge_sort(list1[:num])
            right=self.merge_sort(list1[num:])
            return self.merge(left,right)
    alist=[1,2,4,23,2,32,3,4,3,34,3,43,2,5,8,6,4]
    solution().merge_sort(alist)
    #solution().merge([2,3,4,5],[1,3,5,7])
    #5 快速排序
    def quick_sort(list1):
        if len(list1)==0:
            return []
        if len(list1)==1:
            return list1
        p=list1[0]
        left=quick_sort([i for i in list1 if i<p])
        right=quick_sort([i for i in list1 if i>p])
        return left+[p]+right
    alist=[1,2,4,23,2,32,3,4,3,34,3,43,2,5,8,6,4]
    quick_sort(alist)

**7、堆排序**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 12]  
当我们使用普通数组或者顺序数组，最差的情况：O(n\*\*2)  
使用堆：O(nlogn)  
堆是种树形结构：  
7.2、二叉堆  
1、二叉堆的性质  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 13]  
特点1：对于二叉堆来说所有的子节点的值都小于等于其父系结点，注：但不一定左子树一定比右子树小  
图1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 14]  
特点2：堆是一个完全二叉树，所谓说是完全二叉树的意思是，二叉树的每个结点都有两个分支 ，最下层的二叉树结点都是从左侧开始完全生长。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 15]  
性质3：二叉堆中存储的左结点是父节点的二倍，而右结点是父节点的二倍+1.如果二叉堆的序列号是从0开始的，则左结点为父节点的二倍加1，右结点为父节点的二倍加2  
我们存储以后如果想找子节点和父节点可以采取下面的公式：  
![在这里插入图片描述][20190418110016815.png]  
注：这里的除为//地板除法。向下取整  
性质4：堆元素有入队和出队两种形式，入队是将元素添加到堆中，出队是挑选出优先级最高的元素出队，即最上层的元素,但是无论是入队还是出队都是删除最末尾的元素。  
2、二叉堆的实现  
（1）向二叉堆插入新元素并归位

class binheap:
        def __init__(self):
            self.heaplist=[0]
            self.size = 0
        #percUp为堆的定位函数，即当我们插入新的值时，我们将这个元素重新定位并赋予正确的位置索引
        def percUp(self, i):
            while i//2 > 0:
                if self.heaplist[i] > self.heaplist[i // 2]:
                    self.heaplist[i],self.heaplist[i//2]=self.heaplist[i//2],self.heaplist[i]
                else:
                    pass
                i=i//2
        #设置插入函数insert
        def insert(self,k):
            #向堆添加元素
            self.heaplist.append(k)
            self.size+=1
            self.percUp(self.size)#重置堆的位置和索引
    #######################
    heap=binheap()
    heap.insert(62)
    heap.insert(30)
    heap.insert(41)
    heap.insert(28)
    heap.insert(16)
    heap.insert(22)
    heap.insert(13)
    heap.insert(19)
    heap.insert(17)

结果:  
![在这里插入图片描述][20190418121827588.png]  
我们可以发现二叉树不一定是顺序的，这只是记录了树的结构。我们基本实现了二叉堆对于元素的添加  
**（2）二叉堆元素的删除**  
<1> 删除最大值  
对于二叉堆来说，最上面的值为这组树中的最大值，删除这个这个值很简单，可是怎么在删除以后依然保持堆的数据完整性就是一个问题了。这时我们可以将二叉堆尾部的元素移至二叉树的顶端，再逐级交换，变换至正确位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 16]  
代码：

#删除最大堆中的最大值
        def delmax(self):
            self.heaplist[-1],self.heaplist[1]=self.heaplist[1],self.heaplist[-1]
            del self.heaplist[-1]
            self.perdown(1)
        #maxchild，查找子节点的最大值,即我们每次都需要将左右结点的最大值与根节点交换，这样才能保证我们的#	 	 
        #根节点始终大于左右结点，如果该节点下面没有右结点了，交换左结点
        def maxchild(self,i):
            if i*2+1>self.size:#树的搜索已经大于树的最大深度了
                return 2*i
            else: #寻找子树的最大值，并返回是最大值时左边还是右边
                if self.heaplist[2*i]>=self.heaplist[2*i+1]:
                    return 2*i
                else:
                    return  2*i+1
        def perdown(self,i): #检验第i个元素是否向下交换
            while 2*i<=self.size:
                """
                确定这个结点的下面还有延生，这里不能使用2*i+1<=size.因为可能这个树下面还有衍生，但是只有
                左枝，size=2*i，但2*i+1肯定大于size，这时便跳出了循环，而实际情况却因该是执行这次循环，	 
                判断下这个左枝大小
                """
                mc=self.maxchild(i)
                if self.heaplist[i]<self.heaplist[mc]: #等于的时候元素保持原位置不动
                    self.heaplist[mc],self.heaplist[i]=self.heaplist[i],self.heaplist[mc]
                i=mc
    
    heap.delmax()
    print(heap.heaplist)

结果：  
![在这里插入图片描述][20190418173945434.png]  
（3）将列表转换成堆

def bulidheap(self,alist):
            i=len(alist)//2
            #结点的寻找是从二叉堆的非叶子结点索引开始的，如图1的非叶子结点索引就是5
            self.size=len(alist)
            self.heaplist=[0]+alist[:]
            while i>0:
                self.perdown(i)
                i-=1
    a=[2,3,6,7,5,9]
    heap.bulidheap(a)
    print(heap.heaplist)

![在这里插入图片描述][20190418181450987.png]  
注：同一数据的二叉堆可能不同，比如上面的2结点和3结点互换同样是一个最大二叉堆  
补充堆排序简化代码：

'''
    7、堆排序
    '''
    def adjust_heap(list1,i,n):
        '''
        调整堆,将堆中编号为i的父子节点变为最大堆
        如：
                       9(1)
                  7（2）    6(3)
               3(4) 4(5)  5(6) 3(7)
        i=2的意思就是
        将编号为2的二叉树变为最大堆
        '''
        left=2*i+1
        right=2*i+2
        if left<n and list1[left]>list1[i]:
            list1[i],list1[left]=list1[left],list1[i]
            '''
            由于你对树进行了交换，这时你交换后的子节点步再维持原先最大堆的状态，
            需要继续交换
            如
                    7        
                 12    8    
              11    10
             此时12这个堆为最大堆,我们7这个父节点进行最大堆交换，交换后如图
                    12        
                 7     8    
              11    10
            可以看出由于7交换下来以后，将原先12这个最大堆破坏了，所以必须对7继续
            进行最大堆的维护及下面的这个递归
            '''
            adjust_heap(list1,left,n)
        if right<n and list1[right]>list1[i]:
            list1[i],list1[right]=list1[right],list1[i]
            adjust_heap(list1,right,n)
    def rebuild_heap(list1):
        '''
        重建最大堆
        '''
        n=len(list1)
        i=(n-1)//2 
        '''
        对于list来说所有的父节点都在n-2//2之前，比如数组长度为9
        则所有的父节点的编号都在0-3
        '''
        for z in range(i)[::-1]:
            adjust_heap(list1,z,n)
    list1= [54,26,93,12,77,31,10,55,20]
    rebuild_heap(list1)
    def heap_sort(list1):
        '''
        1 将原数组生成最大堆，此时最大的元素在开头
        2 将最开始的元素与尾部交换，并对前n-1个元素进行二叉堆重建
        3 循环这个操作，
        与倒数第二个元素交换，对钱n-2个元素进行二叉堆重建
        ...
        当抽出第n-1个元素时此时已经形成有序数列,第一个元素肯定为最小的
        因为此时最大堆只剩一个元素了
        '''
        n=len(list1)
        rebuild_heap(list1)
        for i in range(n)[::-1]:
            list1[0],list1[i]=list1[i],list1[0]
            adjust_heap(list1,0,i)
        return list1
    heap_sort(list1)

注：堆中的元素是从索引1开始的

排序算法的时间复杂度与空间复杂度  
![在这里插入图片描述][20190919173309916.png]  
7.3 最大最小索引堆  
1、索引堆的基本概念  
我们上面学会了堆这个概念，但是当堆对应结点的元素比较复杂时，我们在删除、添加等工作时只希望更改堆元素所在的索引，而不想更改堆元素所在的索引，这时就引出了索引堆这个概念，即我们的堆只维护元素所在的索引，但是元素的位置是不变的  
2、索引堆的特点  
我们以\[15,17,19,13,22,16,28,30,41,62\]构造最小索引堆，其格式如下：  
![在这里插入图片描述][20190429203826317.png]  
![在这里插入图片描述][20190429152844439.png]  
上图所表示的便是一个最小索引堆。

*  在最小索引堆中共有两个数组，一个是index数组，一个是data数组，data\[i\]存储真实的数据元素，index\[i\]存储data的索引，并且index构成一个特殊的堆。 index\[0\]是堆顶的第一个元素，index\[0\] = 3,表示取data数组索引3的元素13。可以看到13确实是最小的一个元素，这是一个最小索引堆。  
    素，而这个元素对应index的第1个元素，我们再映射到data数组进行比较。  
    3、最小索引堆的实现  
    我们还是以上图为例来实现最小索引堆

class min_index_heap():
        def __init__(self):
            self.indexlist=[0]
            self.items={
         }
            self.size=0
        def insert(self,k,value):
            self.indexlist.append(k)
            self.items[k]=value
            self.size+=1
            self.perup(self.size)
        def perup(self,i):
            currentvalue=self.items[self.indexlist[i]]
            currentindex=self.indexlist[i]
            while i//2>0:
                if self.items[self.indexlist[i//2]]>currentvalue:               self.indexlist[i],self.indexlist[i//2]=self.indexlist[i//2],self.indexlist[i]
                    i=i//2
                else:
                    break
        def delmin(self): #即删除最小索引堆中的最小的元素（堆中的第一个元素）
            if self.size==1: #索引堆只有一个元素：
                self.size-=1
                return self.items.pop(self.indexlist.pop())
            else:
                self.indexlist[-1],self.indexlist[1] = self.indexlist[1], self.indexlist[-1]
                u=self.indexlist.pop()
                del_element=self.items.pop(u)
                self.size-=1
                self.perdown(1)
                return del_element
        def perdown(self,i):
            while 2*i<=self.size:
                mc=self.minchild(i)
                if self.items[self.indexlist[i]]>self.items[self.indexlist[mc]]:
                    self.indexlist[i],self.indexlist[mc]=self.indexlist[mc],self.indexlist[i]
                    i=mc
                else:
                    break
        def minchild(self,i):
            if 2*i+1>self.size: #只有左枝没有右枝
                return 2*i
            else:
                if self.items[self.indexlist[2*i]]>=self.items[self.indexlist[2*i+1]]:
                    return 2*i+1
                else:
                    return 2*i
        def buildheap(self,items):
            self.items=items
            self.indexlist=[0]+list(self.items.keys())
            self.size=len(items)
            i=self.size//2
            while i>0:
                self.perdown(i)
                i-=1
        def get_items(self,i):
            return self.items[i]
        def min_item(self):
            return self.items[self.indexlist[1]]
        def change(self,k,value):
            if k not in self.items:
                print("错误无法更改")
            else:
                self.items[k]=value
                i=self.indexlist.index(k) #选出索引编号为k的索引在索引堆中的位置
                self.perup(i)  #先将这个索引堆中编号k的索引向上调整位置，维护最小堆
                self.perdown(i) #再将索引堆中编号为k的索引向下调整位置，维护最小堆
                print("元素改变成功")
    #测试
    minindexheap=min_index_heap()
    minindexheap.buildheap({
        1:15,2:17,3:19,4:13,5:22,6:16,7:28,8:30,9:41,10:62})
    print(minindexheap.indexlist)
    print(minindexheap.items)
    minindexheap.change(2,50)
    print(minindexheap.indexlist)
    print(minindexheap.items)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 17]  
函数说明：  
insert：向最小索引堆插入元素，我们的元素是从1开始的，这个插入指的是新增元素，类中的items是个字典，我们不能向已存在的键值进行元素插入，否则就是对元素的更改。  
perup：由下往上找到该元素在堆中的正确位置  
delmin：删除堆中的最小值  
perdown:由上向下  
minchild:辅助函数，返回根节点下子节点中较小的结点索引  
buildheap:将传入的字典转化为最小堆  
get\_items:获取数据集items键值为i的数据  
min\_items：获取堆中最小的数据  
change:改变数据集items中索引为i的value值，并在最小索引堆中重新排序。  
7.4 堆排序  
首先我们先将数组转化为一个最大堆，找出最大堆的第一个元素和最大堆的最后一个元素进行交换，这时数组的最后一个元素已经排好序.  
![在这里插入图片描述][20190418182930632.png]  
但前面已经不是一个最大堆了  
![在这里插入图片描述][20190418183000221.png]  
我们将其变为最大堆，再重复之前的操作，直到w中只有一个元素为止  
这时便拍好了数组中所有元素的顺序。

class heapsort( ):
        def __init_(self):
            self.heaplist=[]
            self.size=len(self.heaplist)
        def buildheap(self,alist):
            self.heaplist=alist
            i=(len(alist)-1)//2
            self.size=len(alist)-1
            #将整个数组重新组合成最大堆
            while i>=0: #
                self.perdown(i)
                i-=1
            return self.heaplist
        def maxchild(self,i):
            if i*2+2>self.size:#我们进行树的搜索时只搜索到树的最后父节点
                return 2*i+1
            else: #寻找子树的最大值，并返回是最大值时左边还是右边
                if self.heaplist[2*i+1]>=self.heaplist[2*i+2]:
                    return 2*i+1
                else:
                    return  2*i+2
        def perdown(self,i): #检验第i个元素是否向下交换
            while 2*i+1<=self.size:
                """
                确定这个结点的下面还有延生，这里不能使用2*i+1<=size.因为可能这个树下面还有衍生，但是只有左枝，size=2*i
                但2*i+1肯定大于size，这时便跳出了循环，而实际情况却因该是执行这次循环，判断下这个左枝的大小
                """
                mc=self.maxchild(i)
                if self.heaplist[i]<self.heaplist[mc]: #等于的时候元素保持原位置不动
                    self.heaplist[mc],self.heaplist[i]=self.heaplist[i],self.heaplist[mc]
                i=mc
        def sort(self,alist):
            j=len(alist) #alist[j..]是已经排好序
            while j>1:
                alist_heap=self.buildheap(alist[0:j])
                alist=alist_heap+alist[j:]
                print(alist)
                j = j - 1
                alist[j],alist[0]=alist[0],alist[j]
                print(alist)
    
            return alist
    
    heap_sort=heapsort()
    a=[2,3,6,7,5,9,11,23,32,11,2,2,2]
    print(heap_sort.buildheap(a))
    sort_a=heap_sort.sort(a)
    print(sort_a)

![在这里插入图片描述][20190418225627628.png]  
**7.4 堆排序的时间复杂度分析**  
堆排序的时间复杂度为O(nlogn)  
其具体分析如下：  
具有n个元素的平衡二叉树，树高为㏒n，我们设这个变量为h。  
最下层非叶节点的元素，只需做一次线性运算便可以确定大根，而这一层具有  
2^(h-1)个元素，我们假定O(1)=1，那么这一层元素进行交换所需时间为 2 h − 1 × 1 2^\{h-1\}× 1 2h−1×1，与此同时，这一层元素的子节点还要进行一次比较（看哪个子节点大）时间复杂度为 2 h − 1 2^\{h-1\} 2h−1，所以这h-1层的时间复杂度为 2 h − 1 × 1 + 2 h − 1 = 2 h − 1 × 2 2^\{h-1\}× 1+2^\{h-1\}=2^\{h-1\}×2 2h−1×1\+2h−1=2h−1×2。同理倒数第h-2层的时间复杂度为 2 h − 2 × 3 2^\{h-2\}×3 2h−2×3,依次类推第k层的时间复杂度为 2 k × ( h − k + 1 ) 2^\{k\}×(h-k+1) 2k×(h−k\+1),最顶层为  
 2 2 × h 2^\{2\}×h 22×h  
则整个的时间复杂度  
 s = 2 h − 1 × 2 + 2 h − 2 × 3 + . . . . 2 3 × ( h − 1 ) + 2 2 × h s=2^\{h-1\}×2+2^\{h-2\}×3+....2^3×(h-1)+2^2×h s=2h−1×2\+2h−2×3\+....23×(h−1)\+22×h  
利用错位相减得 s = 3 ∗ 2 h − 4 h − 8 s=3\*2^h-4h-8 s=3∗2h−4h−8  
将 h = l o g 2 n h=log\_2n h=log2n带入上式  
 s = 3 n − 4 l o g 2 n − 8 s=3n-4log\_2n-8 s=3n−4log2n−8  
时间复杂度为O(log(n))  
**7.5 索引堆**  
我们在对数据进行堆排序时常常会完全改变索引的位置，这会使得我们再对原始数据进行查找时十分不方便。这时我们便可以对原始数组的索引进行堆算法，而不对原始数组进行变动。如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 18]  
                          堆排序前  
（二叉堆的结点标记的为索引号）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 19]  
                建堆后的索引  
这时我们可以通过元素直接找出索引数值以及在堆的位置，具体代码这里不做详解，其基本原理和上面是一样的。  
**总结**：  
排序算法共有7大排序算法  
其总结如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 20]  
注 ：对于不稳定的排序算法，我们可设置比较函数去除排序的不稳定问题，如：当两者相等时，我们设置索引在前的数在前

## 二、排序算法的衍生应用 ##

**一、分治法的应用**  
**1、求逆序对的数量**  
例1：求数组\[2,3,6,8,1,4,5,7\]这个数组的逆序对，  
逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a\[i\] > a\[j\]，则其为一个逆序对；否则不是  
方法1：暴力法  
设置两个指针，指针i和指针j，i在j的前面，先固定i不动，使j从i+1到n寻找逆序对的个数，找到计数器加1，然后不断移动i指针到n-1，直到所有数据遍历结束。

a=[2,3,6,8,1,4,5,7]
    def reverse_double(arr):
        count=0
        i=0
        for i in range(len(arr)-2):
            for j in range(i+1,len(arr)-1):
                if a[j]<a[i]:
                    count+=1
                else:
                    pass
        return count
    print(reverse_double(a))

答案为9  
方法2：采用上面的归并排序的方法先进行分解，再进行归并，归并时计算逆序对

#方法2：
    #首先设置count函数,对于两个已经排好序数列，我们可以直接求逆序对及合并后排序的序列
    def Count(left,right,count):
        result=[]
        l = 0 #左边数组的指针
        r = 0 #右边数组的指针
        bianli=True
        while True:
            #print(result)
            #print(l,r)
            if left[l]<=right[r]:
                result.append(left[l])
                l+=1
                #print("判断1")
                #print(l)
            else: #right[r]<left[l]
                result.append(right[r])
                r+=1
                count=count+len(left)-l
            if l>len(left)-1: #证明左边数组的数都比r当前指针的数小
                #print("判断3")
                result=result+right[r:]
                break
            if r>len(right)-1:
                #print("判断4")
                result=result+left[l:]
                break
        return count,result
    #print(Count(left,right,count=0))
    def reverse_number(arr):
        if len(arr)==1:
            return 0,arr
        else:
            n=len(arr)//2
            left=arr[:n]
            right=arr[n:]
            count1,lis1=reverse_number(left)
            count2,lis2=reverse_number(right)
            #对每一个分后的个体采用Count操作，计算合并的逆序对个数
            count3, lis = Count(lis1, lis2, 0)
            return count3+count1+count2,lis
    print(reverse_number(a))

当思路不明确的时候，画图会更好一点。  
例2：求数组中的最大最小值（或者求解数组中第n大的元素）  
同样采取quick\_sort快速排序，然后按照索引取出其中的元素。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: /images/20220222/cfc00abedd6c45cfbcdaf8336dce90c1.png
[20190408213412812.png]: /images/20220222/8fec529eabf747d4a9befc0ab8172c21.png
[20190408221803726.png]: /images/20220222/b159cd693d394f86b6e1ec77e017e0ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: /images/20220222/c4d24baad56643f1b1bbb495635fcc6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]: /images/20220222/7aa4637f4c7c4bcbbf4c0618bafd12f4.png
[20190409165932574.png]: /images/20220222/5d4fd4df1ba44095b5c281c14ad49046.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]: /images/20220222/2dfaf5f179fa4b28a41e7d271a312fdc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 4]: /images/20220222/60579f34d65e432cba625446bbe76677.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 5]: /images/20220222/53197f205cef49d48451fdb2263d934d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 6]: /images/20220222/27266515c7854ae3924df2ad3de7201b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 7]: /images/20220222/60d5d03867a24f5489b0eddf233885bb.png
[2019041617393683.png]: /images/20220222/113f41e2d90147f9a564cbe6c97b306b.png
[20190417091943997.png]: /images/20220222/632f7867b513454f96bcb911e40decdf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 8]: /images/20220222/878d989078544d2289dcbf8e2b9e17fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 9]: /images/20220222/73780a755f544215a94746f6c81af535.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 10]: /images/20220222/9ad8b20102034a648a498199142adf81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 11]: /images/20220222/72bda47ddaee493f8c8a270520108492.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 12]: /images/20220222/9826e965ffc143be90be16d63f8311e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 13]: /images/20220222/23026f5c590d4abfa55f4dd273818b52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 14]: /images/20220222/85512907d6eb4d5184cc9efc194eb6ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 15]: /images/20220222/25745a677c264ba89b4d24b902b4fc07.png
[20190418110016815.png]: /images/20220222/5eb34ceddbb245d79f34606de27e97f8.png
[20190418121827588.png]: /images/20220222/7d60f8322da54633b6c2cc0074fec964.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 16]: /images/20220222/ba514b98fde141149fe70e03b3743465.png
[20190418173945434.png]: /images/20220222/1253d1c0d84f4fc49581eb30cf2e4d19.png
[20190418181450987.png]: /images/20220222/a3ef40ab7c664f509874158077bb3fe0.png
[20190919173309916.png]: /images/20220222/125da1e59d7449b58b08da6ba80be16d.png
[20190429203826317.png]: /images/20220222/030232343b6449d48550b10b0f5fa062.png
[20190429152844439.png]: /images/20220222/984bad06f3a74f2598d2e941a431e850.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 17]: /images/20220222/5a52c65b49204812a9ca3b752b4da1c4.png
[20190418182930632.png]: /images/20220222/4831a62470ea4eaa98692bee30def91a.png
[20190418183000221.png]: /images/20220222/6f5991db2b3b441b9bee5a7264afc6d2.png
[20190418225627628.png]: /images/20220222/8cdfbe540b844a6eab155e1827cc2fba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 18]: /images/20220222/f41e53c0e53a478f9e5acabad60f1694.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 19]: /images/20220222/81a19cf4a8c1432ea55f50a3166b7a34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 20]: /images/20220222/a3f7f1f96a674cfd83c141866a70ca50.png