Python中格式化的两种方法 在Python中，采用的格式化方式和C语言是一致的，用%实现，举例如下：>>> 'Hello, %s' % 'world' 'Hello, world' >>> 'Hi, %s, you have $%d.' % ('Michael', 1000000) 'Hi, Michael, you have $1000000.'你可能猜到了，%运算符就是用来格式化字符串的。在字符串内部，%s表示用字符串替换，%d表示用整数替换，有几个%?占位符，后面就跟几个变量或者值，顺序要对应好。如果只有一个%?，括号可以省略。相关推荐：《Python视频教程》常见的占位符有：其中，格式化整数和浮点数还可以指定是否补0和整数与小数的位数：print('%2d-%02d' % (3, 1)) print('%.2f' % 3.1415926)如果你不太确定应该用什么，%s永远起作用，它会把任何数据类型转换为字符串：>>> 'Age: %s. Gender: %s' % (25, True) 'Age: 25. Gender: True'有些时候，字符串里面的%是一个普通字符怎么办？这个时候就需要转义，用%%来表示一个%：>>> 'growth rate: %d %%' % 7 'growth rate: 7 %' format()另一种格式化字符串的方法是使用字符串的format()方法，它会用传入的参数依次替换字符串内的占位符{0}、{1}……，不过这种方式写起来比%要麻烦得多：>>> 'Hello, {0}, 成绩提升了 {1:.1f}%'.format('小明', 17.125) 'Hello, 小明, 成绩提升了 17.1%'

基于Python的七种经典排序算法是什么 一、排序的基本概念和分类所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序的稳定性：经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。内排序和外排序内排序：排序过程中，待排序的所有记录全部放在内存中外排序：排序过程中，使用到了外部存储。通常讨论的都是内排序。影响内排序算法性能的三个因素：时间复杂度：即时间性能，高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数空间复杂度：主要是执行算法所需要的辅助空间，越少越好。算法复杂性。主要是指代码的复杂性。根据排序过程中借助的主要操作，可把内排序分为：插入排序交换排序选择排序归并排序按照算法复杂度可分为两类：简单算法：包括冒泡排序、简单选择排序和直接插入排序改进算法：包括希尔排序、堆排序、归并排序和快速排序以下的七种排序算法只是所有排序算法中最经典的几种，不代表全部。二、 冒泡排序冒泡排序（Bubble sort）：时间复杂度O(n^2)交换排序的一种。其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。其实现细节可以不同，比如下面3种：最简单排序实现:bubble_sort_simple冒泡排序:bubble_sort改进的冒泡排序:bubble_sort_advance#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: Liu Jiang# Python 3.5# 冒泡排序算法class SQList:     def __init__(self, lis=None):         self.r = lis    def swap(self, i, j):         """定义一个交换元素的方法，方便后面调用。"""         temp = self.r[i]         self.r[i] = self.r[j]         self.r[j] = temp    def bubble_sort_simple(self):         """         最简单的交换排序，时间复杂度O(n^2)         """         lis = self.r         length = len(self.r)        for i in range(length):            for j in range(i+1, length):                if lis[i] > lis[j]:                     self.swap(i, j)    def bubble_sort(self):         """         冒泡排序，时间复杂度O(n^2)         """         lis = self.r         length = len(self.r)        for i in range(length):             j = length-2             while j >= i:                if lis[j] > lis[j+1]:                     self.swap(j, j+1)                 j -= 1    def bubble_sort_advance(self):         """         冒泡排序改进算法，时间复杂度O(n^2)         设置flag，当一轮比较中未发生交换动作，则说明后面的元素其实已经有序排列了。         对于比较规整的元素集合，可提高一定的排序效率。         """         lis = self.r         length = len(self.r)         flag = True         i = 0         while i < length and flag:             flag = False             j = length - 2             while j >= i:                if lis[j] > lis[j + 1]:                     self.swap(j, j + 1)                     flag = True                 j -= 1             i += 1    def __str__(self):         ret = ""         for i in self.r:             ret += " %s" % i        return retif __name__ == '__main__':     sqlist = SQList([4,1,7,3,8,5,9,2,6])    # sqlist.bubble_sort_simple()     # sqlist.bubble_sort()     sqlist.bubble_sort_advance()     print(sqlist)简单选择排序（simple selection sort）:时间复杂度O(n^2)通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n)个记录进行交换。通俗的说就是，对尚未完成排序的所有元素，从头到尾比一遍，记录下最小的那个元素的下标，也就是该元素的位置。再把该元素交换到当前遍历的最前面。其效率之处在于，每一轮中比较了很多次，但只交换一次。因此虽然它的时间复杂度也是O(n^2)，但比冒泡算法还是要好一点。#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: Liu Jiang# Python 3.5# 简单选择排序class SQList:     def __init__(self, lis=None):         self.r = lis    def swap(self, i, j):         """定义一个交换元素的方法，方便后面调用。"""         temp = self.r[i]         self.r[i] = self.r[j]         self.r[j] = temp    def select_sort(self):         """         简单选择排序，时间复杂度O(n^2)         """         lis = self.r         length = len(self.r)        for i in range(length):             minimum = i            for j in range(i+1, length):                if lis[minimum] > lis[j]:                     minimum = j            if i != minimum:                 self.swap(i, minimum)    def __str__(self):         ret = ""         for i in self.r:             ret += " %s" % i        return retif __name__ == '__main__':     sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])     sqlist.select_sort()     print(sqlist)四、直接插入排序直接插入排序（Straight Insertion Sort）:时间复杂度O(n^2)基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: Liu Jiang# Python 3.5# 直接插入排序class SQList:     def __init__(self, lis=None):         self.r = lis    def insert_sort(self):         lis = self.r         length = len(self.r)        # 下标从1开始         for i in range(1, length):            if lis[i] < lis[i-1]:                 temp = lis[i]                 j = i-1                 while lis[j] > temp and j >= 0:                     lis[j+1] = lis[j]                     j -= 1                 lis[j+1] = temp    def __str__(self):         ret = ""         for i in self.r:             ret += " %s" % i        return retif __name__ == '__main__':     sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])     sqlist.insert_sort()     print(sqlist)该算法需要一个记录的辅助空间。最好情况下，当原始数据就是有序的时候，只需要一轮对比，不需要移动记录，此时时间复杂度为O(n)。然而，这基本是幻想。五、希尔排序希尔排序（Shell Sort）是插入排序的改进版本，其核心思想是将原数据集合分割成若干个子序列，然后再对子序列分别进行直接插入排序，使子序列基本有序，最后再对全体记录进行一次直接插入排序。这里最关键的是跳跃和分割的策略，也就是我们要怎么分割数据，间隔多大的问题。通常将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。下面的例子中通过：increment = int(increment/3)+1来确定“增量”的值。相关推荐：《Python视频教程》希尔排序的时间复杂度为：O(n^(3/2))#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 希尔排序class SQList:     def __init__(self, lis=None):         self.r = lis    def shell_sort(self):         """希尔排序"""         lis = self.r         length = len(lis)         increment = len(lis)                 while increment > 1:             increment = int(increment/3)+1             for i in range(increment+1, length):                                 if lis[i] < lis[i - increment]:                     temp = lis[i]                     j = i - increment                                 while j >= 0 and temp < lis[j]:                         lis[j+increment] = lis[j]                         j -= increment                     lis[j+increment] = temp             def __str__(self):             ret = ""             for i in self.r:                 ret += " %s" % i                     return ret if __name__ == '__main__':     sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0,123,22])     sqlist.shell_sort()     print(sqlist)六、堆排序堆是具有下列性质的完全二叉树：每个分支节点的值都大于或等于其左右孩子的值，称为大顶堆；每个分支节点的值都小于或等于其做右孩子的值，称为小顶堆；因此，其根节点一定是所有节点中（最小）的值。如果按照层序遍历的方式（广度优先）给节点从1开始编号，则节点之间满足如下关系：堆排序（Heap Sort）就是利用大顶堆或小顶堆的性质进行排序的方法。堆排序的总体时间复杂度为O(nlogn)。（下面采用大顶堆的方式）其核心思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的值就是堆的根节点。将它与堆数组的末尾元素交换，然后将剩余的n-1个序列重新构造成一个大顶堆。反复执行前面的操作，最后获得一个有序序列。#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 堆排序class SQList:     def __init__(self, lis=None):         self.r = lis             def swap(self, i, j):         """定义一个交换元素的方法，方便后面调用。"""         temp = self.r[i]         self.r[i] = self.r[j]         self.r[j] = temp             def heap_sort(self):         length = len(self.r)         i = int(length/2)        # 将原始序列构造成一个大顶堆         # 遍历从中间开始，到0结束，其实这些是堆的分支节点。         while i >= 0:             self.heap_adjust(i, length-1)             i -= 1         # 逆序遍历整个序列，不断取出根节点的值，完成实际的排序。         j = length-1         while j > 0:            # 将当前根节点，也就是列表最开头，下标为0的值，交换到最后面j处             self.swap(0, j)            # 将发生变化的序列重新构造成大顶堆             self.heap_adjust(0, j-1)             j -= 1     def heap_adjust(self, s, m):         """核心的大顶堆构造方法，维持序列的堆结构。"""         lis = self.r         temp = lis[s]         i = 2*s                    while i <= m:                     if i < m and lis[i] < lis[i+1]:                 i += 1             if temp >= lis[i]:                                 break             lis[s] = lis[i]             s = i             i *= 2         lis[s] = temp    def __str__(self):         ret = ""         for i in self.r:             ret += " %s" % i                     return ret if __name__ == '__main__':     sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])     sqlist.heap_sort()     print(sqlist)堆排序的运行时间主要消耗在初始构建堆和重建堆的反复筛选上。其初始构建堆时间复杂度为O(n)。正式排序时，重建堆的时间复杂度为O(nlogn)。所以堆排序的总体时间复杂度为O(nlogn)。堆排序对原始记录的排序状态不敏感，因此它无论最好、最坏和平均时间复杂度都是O(nlogn)。在性能上要好于冒泡、简单选择和直接插入算法。空间复杂度上，只需要一个用于交换的暂存单元。但是由于记录的比较和交换是跳跃式的，因此，堆排序也是一种不稳定的排序方法。此外，由于初始构建堆的比较次数较多，堆排序不适合序列个数较少的排序工作。七、归并排序归并排序（Merging Sort）：建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 归并排序 class SQList:     def __init__(self, lis=None):         self.r = lis         def swap(self, i, j):         """定义一个交换元素的方法，方便后面调用。"""         temp = self.r[i]         self.r[i] = self.r[j]         self.r[j] = temp          def merge_sort(self):         self.msort(self.r, self.r, 0, len(self.r)-1)          def msort(self, list_sr, list_tr, s, t):          temp = [None for i in range(0, len(list_sr))]                 if s == t:             list_tr[s] = list_sr[s]                 else:             m = int((s+t)/2)             self.msort(list_sr, temp, s,  m)             self.msort(list_sr, temp, m+1, t)             self.merge(temp, list_tr, s, m, t)          def merge(self, list_sr, list_tr, i, m,  n):         j = m+1         k = i                 while i <= m and j <= n:                         if list_sr[i] < list_sr[j]:                list_tr[k] = list_sr[i]               i += 1            else:               list_tr[k] = list_sr[j]               j += 1            k += 1         if i <= m:                         for l in range(0, m-i+1):                list_tr[k+l] = list_sr[i+l]                 if j <= n:                        for l in range(0, n-j+1):               list_tr[k+l] = list_sr[j+l]         def __str__(self):         ret = ""        for i in self.r:            ret += " %s" % i                return ret if __name__ == '__main__':     sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 12, 77, 34, 23])     sqlist.merge_sort()     print(sqlist)另外一个版本：def merge(lfrom, lto, low, mid, high):     """     两段需要归并的序列从左往右遍历，逐一比较，小的就放到     lto里去，lfrom下标+1，lto下标+1，然后再取，再比，再放，     最后lfrom里的两段比完了，lto里留下的就是从小到大排好的一段。     :param lfrom: 原来的列表     :param lto: 缓存的列表     :param low: 左边一段的开头下标     :param mid: 左右两段的中间相隔的下标     :param high: 右边一段的最右下标     :return:     """     i, j, k = low, mid, low         while i < mid and j < high:                 if lfrom[i] <= lfrom[j]:             lto[k] = lfrom[i]             i += 1         else:             lto[k] = lfrom[j]             j += 1         k += 1     while i < mid:         lto[k] = lfrom[i]         i += 1         k += 1     while j < high:         lto[k] = lfrom[j]         j += 1         k += 1def merge_pass(lfrom, lto, llen, slen):     """     用来处理所有需要合并的段，这需要每段的长度，以及列表的总长。     最后的if语句处理表最后部分不规则的情况。     :param lfrom: 原来的列表     :param lto: 缓存的列表     :param llen: 列表总长     :param slen: 每段的长度     :return:     """     i = 0     while i+2*slen < llen:         merge(lfrom, lto, i, i+slen, i+2*slen)         i += 2*slen    if i+slen < llen:         merge(lfrom, lto, i, i+slen, llen)                 else:                 for j in range(i, llen):             lto[j] = lfrom[j]     def merge_sort(lst):     """     主函数。     先安排一个同样大小的列表，作为辅助空间。     然后在两个列表直接做往复的归并，每归并一次slen的长度增加一倍，     逐渐向llen靠拢，当slen==llen时说明归并结束了。     归并完成后最终结果可能恰好保存在templist里，因此代码里做两次归并，     保证最后的结果体现在原始的lst列表里。     :param lst: 要排序的原始列表     :return:     """     slen, llen = 1, len(lst)     templist = [None]*llen    while slen < llen:         merge_pass(lst, templist, llen, slen)         slen *= 2         merge_pass(templist, lst, llen, slen)         slen *= 2归并排序对原始序列元素分布情况不敏感，其时间复杂度为O(nlogn)。归并排序在计算过程中需要使用一定的辅助空间，用于递归和存放结果，因此其空间复杂度为O(n+logn)。归并排序中不存在跳跃，只有两两比较，因此是一种稳定排序。总之，归并排序是一种比较占用内存，但效率高，并且稳定的算法。八、快速排序快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n))。快速排序算法的核心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分继续进行排序，以达到整个记录集合的排序目的。#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: Liu Jiang# Python 3.5# 快速排序class SQList:     def __init__(self, lis=None):         self.r = lis    def swap(self, i, j):         """定义一个交换元素的方法，方便后面调用。"""         temp = self.r[i]         self.r[i] = self.r[j]         self.r[j] = temp    def quick_sort(self):         """调用入口"""         self.qsort(0, len(self.r)-1)    def qsort(self, low, high):         """递归调用"""         if low < high:             pivot = self.partition(low, high)             self.qsort(low, pivot-1)             self.qsort(pivot+1, high)    def partition(self, low, high):         """         快速排序的核心代码。         其实就是将选取的pivot_key不断交换，将比它小的换到左边，将比它大的换到右边。         它自己也在交换中不断变换自己的位置，直到完成所有的交换为止。         但在函数调用的过程中，pivot_key的值始终不变。         :param low:左边界下标         :param high:右边界下标         :return:分完左右区后pivot_key所在位置的下标         """         lis = self.r         pivot_key = lis[low]                 while low < high:                     while low < high and lis[high] >= pivot_key:                 high -= 1             self.swap(low, high)                         while low < high and lis[low] <= pivot_key:                 low += 1             self.swap(low, high)                     return low             def __str__(self):             ret = ""         for i in self.r:            ret += " %s" % i                 return ret if __name__ == '__main__':     sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])     sqlist.quick_sort()     print(sqlist)另外一个版本：def quick_sort(nums):     # 封装一层的目的是方便用户调用     def qsort(lst, begin, end):         if begin >= end:                     return         i = begin         key = lst[begin]                 for j in range(begin+1, end+1):                     if lst[j] < key:                 i += 1                 lst[i], lst[j] = lst[j], lst[i]         lst[begin], lst[i] = lst[i], lst[begin]         qsort(lst, begin, i-1)         qsort(lst,i+1,end)     qsort(nums, 0, len(nums)-1)快速排序的时间性能取决于递归的深度。当pivot_key恰好处于记录关键码的中间值时，大小两区的划分比较均衡，接近一个平衡二叉树，此时的时间复杂度为O(nlog(n))。当原记录集合是一个正序或逆序的情况下，分区的结果就是一棵斜树，其深度为n-1，每一次执行大小分区，都要使用n-i次比较，其最终时间复杂度为O(n^2)。在一般情况下，通过数学归纳法可证明，快速排序的时间复杂度为O(nlog(n))。但是由于关键字的比较和交换是跳跃式的，因此，快速排序是一种不稳定排序。同时由于采用的递归技术，该算法需要一定的辅助空间，其空间复杂度为O(logn)。下面是一个实例测试数据： 从数据中可见：数据过万，冒泡算法基本不可用。测试时间忠实的反映了n平方的时间复杂度，数据扩大10倍，耗时增加100倍对于Python的列表，反序遍历比正序遍历还是要消耗一定的时间的快速排序在数据较大时，其威力显现，但不够稳定，总体还是维护了nlog(n)的复杂度。基本的快速排序还有可以优化的地方：1. 优化选取的pivot_key前面我们每次选取pivot_key的都是子序列的第一个元素，也就是lis[low]，这就比较看运气。运气好时，该值处于整个序列的靠近中间值，则构造的树比较平衡，运气比较差，处于或最小位置附近则构造的树接近斜树。为了保证pivot_key选取的尽可能适中，采取选取序列左中右三个特殊位置的值中，处于中间值的那个数为pivot_key，通常会比直接用lis[low]要好一点。在代码中，在原来的pivot_key = lis[low]这一行前面增加下面的代码：m = low + int((high-low)/2)if lis[low] > lis[high]:     self.swap(low, high)if lis[m] > lis[high]:     self.swap(high, m)if lis[m] > lis[low]:     self.swap(m, low)如果觉得这样还不够好，还可以将整个序列先划分为3部分，每一部分求出个pivot_key，再对3个pivot_key再做一次上面的比较得出最终的pivot_key。这时的pivot_key应该很大概率是一个比较靠谱的值。2. 减少不必要的交换原来的代码中pivot_key这个记录总是再不断的交换中，其实这是没必要的，完全可以将它暂存在某个临时变量中，如下所示：def partition(self, low, high):                  lis = self.r         m = low + int((high-low)/2)                 if lis[low] > lis[high]:             self.swap(low, high)                     if lis[m] > lis[high]:             self.swap(high, m)                     if lis[m] > lis[low]:             self.swap(m, low)         pivot_key = lis[low]        # temp暂存pivot_key的值         temp = pivot_key                 while low < high:                     while low < high and lis[high] >= pivot_key:                 high -= 1             # 直接替换，而不交换了             lis[low] = lis[high]                         while low < high and lis[low] <= pivot_key:                 low += 1             lis[high] = lis[low]             lis[low] = temp        return low3. 优化小数组时的排序快速排序算法的递归操作在进行大量数据排序时，其开销能被接受，速度较快。但进行小数组排序时则不如直接插入排序来得快，也就是杀鸡用牛刀，未必就比菜刀来得快。因此，一种很朴素的做法就是根据数据的多少，做个使用哪种算法的选择而已，如下改写qsort方法：def qsort(self, low, high):     """根据序列长短，选择使用快速排序还是简单插入排序"""     # 7是一个经验值，可根据实际情况自行决定该数值。     MAX_LENGTH = 7     if high-low < MAX_LENGTH:                 if low < high:             pivot = self.partition(low, high)             self.qsort(low, pivot - 1)             self.qsort(pivot + 1, high)                     else:        # insert_sort方法是我们前面写过的简单插入排序算法         self.insert_sort()4. 优化递归操作可以采用尾递归的方式对整个算法的递归操作进行优化，改写qsort方法如下：def qsort(self, low, high):     """根据序列长短，选择使用快速排序还是简单插入排序"""     # 7是一个经验值，可根据实际情况自行决定该数值。     MAX_LENGTH = 7     if high-low < MAX_LENGTH:        # 改用while循环         while low < high:             pivot = self.partition(low, high)             self.qsort(low, pivot - 1)            # 采用了尾递归的方式             low = pivot + 1     else:        # insert_sort方法是我们前面写过的简单插入排序算法         self.insert_sort()九、排序算法总结排序算法的分类：没有十全十美的算法，有有点就会有缺点，即使是快速排序算法，也只是整体性能上的优越，也存在排序不稳定，需要大量辅助空间，不适于少量数据排序等缺点。七种排序算法性能对比如果待排序列基本有序，请直接使用简单的算法，不要使用复杂的改进算法。归并排序和快速排序虽然性能高，但是需要更多的辅助空间。其实就是用空间换时间。待排序列的元素个数越少，就越适合用简单的排序方法；元素个数越多就越适合用改进的排序算法。简单选择排序虽然在时间性能上不好，但它在空间利用上性能很高。特别适合，那些数据量不大，每条数据的信息量又比较多的一类元素的排序。

Python中常用的查找数据结构及算法汇总 一、基本概念查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。查找表（Search Table）：由同一类型的数据元素（或记录）构成的集合关键字（Key）：数据元素中某个数据项的值，又称为键值。主键（Primary Key）：可唯一地标识某个数据元素或记录的关键字。查找表按照操作方式可分为：静态查找表（Static Search Table）：只做查找操作的查找表。它的主要操作是：查询某个“特定的”数据元素是否在表中检索某个“特定的”数据元素和各种属性动态查找表（Dynamic Search Table）：在查找中同时进行插入或删除等操作：查找时插入数据查找时删除数据二、无序表查找也就是数据不排序的线性查找，遍历数据元素。算法分析：最好情况是在第一个位置就找到了，此为O(1)；最坏情况在最后一个位置才找到，此为O(n)；所以平均查找次数为(n+1)/2。最终时间复杂度为O(n)# 最基础的遍历无序列表的查找算法# 时间复杂度O(n) def sequential_search(lis, key):     length = len(lis)         for i in range(length):                 if lis[i] == key:                         return i         else:                 return False if __name__ == '__main__':     LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]     result = sequential_search(LIST, 123)     print(result)三、有序表查找查找表中的数据必须按某个主键进行某种排序！1. 二分查找(Binary Search)算法核心：在查找表中不断取中间元素与查找值进行比较，以二分之一的倍率进行表范围的缩小。# 针对有序查找表的二分查找算法# 时间复杂度O(log(n)) def binary_search(lis, key):     low = 0     high = len(lis) - 1     time = 0     while low < high:         time += 1         mid = int((low + high) / 2)        if key < lis[mid]:             high = mid - 1         elif key > lis[mid]:             low = mid + 1         else:            # 打印折半的次数             print("times: %s" % time)            return mid     print("times: %s" % time)    return Falseif __name__ == '__main__':     LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]     result = binary_search(LIST, 99)     print(result)2. 插值查找二分查找法虽然已经很不错了，但还有可以优化的地方。有的时候，对半过滤还不够狠，要是每次都排除十分之九的数据岂不是更好？选择这个值就是关键问题，插值的意义就是：以更快的速度进行缩减。相关推荐：《Python视频教程》插值的核心就是使用公式：value = (key - list[low])/(list[high] - list[low])用这个value来代替二分查找中的1/2。上面的代码可以直接使用，只需要改一句。# 插值查找算法# 时间复杂度O(log(n)) def binary_search(lis, key):     low = 0     high = len(lis) - 1     time = 0     while low < high:         time += 1         # 计算mid值是插值算法的核心代码         mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))         print("mid=%s, low=%s, high=%s" % (mid, low, high))        if key < lis[mid]:             high = mid - 1         elif key > lis[mid]:             low = mid + 1         else:            # 打印查找的次数             print("times: %s" % time)            return mid     print("times: %s" % time)    return Falseif __name__ == '__main__':     LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]     result = binary_search(LIST, 444)     print(result)插值算法的总体时间复杂度仍然属于O(log(n))级别的。其优点是，对于表内数据量较大，且关键字分布比较均匀的查找表，使用插值算法的平均性能比二分查找要好得多。反之，对于分布极端不均匀的数据，则不适合使用插值算法。3. 斐波那契查找由插值算法带来的启发，发明了斐波那契算法。其核心也是如何优化那个缩减速率，使得查找次数尽量降低。使用这种算法，前提是已经有一个包含斐波那契数据的列表F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...]# 斐波那契查找算法# 时间复杂度O(log(n))def fibonacci_search(lis, key):     # 需要一个现成的斐波那契列表。其元素的值必须超过查找表中元素个数的数值。     F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,         233, 377, 610, 987, 1597, 2584, 4181, 6765,         10946, 17711, 28657, 46368]     low = 0     high = len(lis) - 1          # 为了使得查找表满足斐波那契特性，在表的最后添加几个同样的值     # 这个值是原查找表的最后那个元素的值     # 添加的个数由F[k]-1-high决定     k = 0     while high > F[k]-1:         k += 1     print(k)     i = high    while F[k]-1 > i:         lis.append(lis[high])         i += 1     print(lis)         # 算法主逻辑。time用于展示循环的次数。     time = 0     while low <= high:         time += 1         # 为了防止F列表下标溢出，设置if和else         if k < 2:             mid = low        else:             mid = low + F[k-1]-1                  print("low=%s, mid=%s, high=%s" % (low, mid, high))        if key < lis[mid]:             high = mid - 1             k -= 1         elif key > lis[mid]:             low = mid + 1             k -= 2         else:            if mid <= high:                # 打印查找的次数                 print("times: %s" % time)                return mid            else:                 print("times: %s" % time)                return high     print("times: %s" % time)    return Falseif __name__ == '__main__':     LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]     result = fibonacci_search(LIST, 444)     print(result)算法分析：斐波那契查找的整体时间复杂度也为O(log(n))。但就平均性能，要优于二分查找。但是在最坏情况下，比如这里如果key为1，则始终处于左侧半区查找，此时其效率要低于二分查找。总结：二分查找的mid运算是加法与除法，插值查找则是复杂的四则运算，而斐波那契查找只是最简单的加减运算。在海量数据的查找中，这种细微的差别可能会影响最终的查找效率。因此，三种有序表的查找方法本质上是分割点的选择不同，各有优劣，应根据实际情况进行选择。四、线性索引查找对于海量的无序数据，为了提高查找速度，一般会为其构造索引表。索引就是把一个关键字与它相对应的记录进行关联的过程。一个索引由若干个索引项构成，每个索引项至少包含关键字和其对应的记录在存储器中的位置等信息。索引按照结构可以分为：线性索引、树形索引和多级索引。线性索引：将索引项的集合通过线性结构来组织，也叫索引表。线性索引可分为：稠密索引、分块索引和倒排索引稠密索引稠密索引指的是在线性索引中，为数据集合中的每个记录都建立一个索引项。这其实就相当于给无序的集合，建立了一张有序的线性表。其索引项一定是按照关键码进行有序的排列。这也相当于把查找过程中需要的排序工作给提前做了。分块索引给大量的无序数据集合进行分块处理，使得块内无序，块与块之间有序。这其实是有序查找和无序查找的一种中间状态或者说妥协状态。因为数据量过大，建立完整的稠密索引耗时耗力，占用资源过多；但如果不做任何排序或者索引，那么遍历的查找也无法接受，只能折中，做一定程度的排序或索引。分块索引的效率比遍历查找的O(n)要高一些，但与二分查找的O(logn)还是要差不少。倒排索引不是由记录来确定属性值，而是由属性值来确定记录的位置，这种被称为倒排索引。其中记录号表存储具有相同次关键字的所有记录的地址或引用（可以是指向记录的指针或该记录的主关键字）。倒排索引是最基础的搜索引擎索引技术。

Python中的二叉排序树和平衡二叉树是什么 二叉排序树二叉排序树又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：若它的左子树不为空，则左子树上所有节点的值均小于它的根结构的值；若它的右子树不为空，则右子树上所有节点的值均大于它的根结构的值；它的左、右子树也分别为二叉排序树。构造一颗二叉排序树的目的，往往不是为了排序，而是为了提高查找和插入删除关键字的速度。二叉排序树的操作：查找：对比节点的值和关键字，相等则表明找到了；小了则往节点的左子树去找，大了则往右子树去找，这么递归下去，最后返回布尔值或找到的节点。插入：从根节点开始逐个与关键字进行对比，小了去左边，大了去右边，碰到子树为空的情况就将新的节点链接。删除：如果要删除的节点是叶子，直接删；如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可；如果同时有左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。      """     定义一个二叉树节点类。     以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。     """     def __init__(self, data, left=None, right=None):         """         初始化         :param data: 节点储存的数据         :param left: 节点左子树         :param right: 节点右子树         """         self.data = data         self.left = left         self.right = rightclass BinarySortTree:     """     基于BSTNode类的二叉排序树。维护一个根节点的指针。     """     def __init__(self):         self._root = None     def is_empty(self):         return self._root is None     def search(self, key):         """         关键码检索         :param key: 关键码         :return: 查询节点或None         """         bt = self._root        while bt:             entry = bt.data            if key < entry:                 bt = bt.left            elif key > entry:                 bt = bt.right            else:                return entry        return None     def insert(self, key):         """         插入操作         :param key:关键码          :return: 布尔值         """         bt = self._root        if not bt:             self._root = BSTNode(key)            return         while True:             entry = bt.data            if key < entry:                if bt.left is None:                     bt.left = BSTNode(key)                    return                 bt = bt.left            elif key > entry:                if bt.right is None:                     bt.right = BSTNode(key)                    return                 bt = bt.right            else:                 bt.data = key                return     def delete(self, key):         """         二叉排序树最复杂的方法         :param key: 关键码         :return: 布尔值         """         p, q = None, self._root     # 维持p为q的父节点，用于后面的链接操作         if not q:             print("空树！")            return         while q and q.data != key:             p = q            if key < q.data:                 q = q.left            else:                 q = q.right            if not q:               # 当树中没有关键码key时，结束退出。                 return         # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。         if not q.left:            if p is None:                 self._root = q.right            elif q is p.left:                 p.left = q.right            else:                 p.right = q.right            return         # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树         # 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。         r = q.left        while r.right:             r = r.right         r.right = q.right        if p is None:             self._root = q.left        elif p.left is q:             p.left = q.left        else:             p.right = q.left    def __iter__(self):         """         实现二叉树的中序遍历算法,         展示我们创建的二叉排序树.         直接使用python内置的列表作为一个栈。         :return: data         """         stack = []         node = self._root        while node or stack:            while node:                 stack.append(node)                 node = node.left             node = stack.pop()            yield node.data             node = node.rightif __name__ == '__main__':     lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]     bs_tree = BinarySortTree()    for i in range(len(lis)):         bs_tree.insert(lis[i])    # bs_tree.insert(100)     bs_tree.delete(58)    for i in bs_tree:         print(i, end=" ")    # print("\n", bs_tree.search(4))相关推荐：《Python视频教程》二叉排序树总结：二叉排序树以链式进行存储，保持了链接结构在插入和删除操作上的优点。在极端情况下，查询次数为1，但操作次数不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状，也就引申出了后面的平衡二叉树。给定一个元素集合，可以构造不同的二叉排序树，当它同时是一个完全二叉树的时候，查找的时间复杂度为O(log(n))，近似于二分查找。当出现最极端的斜树时，其时间复杂度为O(n)，等同于顺序查找，效果最差。平衡二叉树平衡二叉树（AVL树，发明者的姓名缩写）：一种高度平衡的排序二叉树，其每一个节点的左子树和右子树的高度差最多等于1。平衡二叉树首先必须是一棵二叉排序树！平衡因子（Balance Factor）：将二叉树上节点的左子树深度减去右子树深度的值。对于平衡二叉树所有包括分支节点和叶节点的平衡因子只可能是-1,0和1，只要有一个节点的因子不在这三个值之内，该二叉树就是不平衡的。最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的节点为根的子树。平衡二叉树的构建思想：每当插入一个新结点时，先检查是否破坏了树的平衡性，若有，找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，进行相应的旋转，成为新的平衡子树。下面是由[1,2,3,4,5,6,7,10,9]构建平衡二叉树

python新手常见问题一：乱用表达式 在函数参数中乱用表达式作为默认值Python允许给一个函数的某个参数设置默认值以使该参数成为一个可选参数。尽管这是这门语言很棒的一个功能，但是这当这个默认值是可变对象（mutable）时，那就有些麻烦了。例如，看下面这个Python函数定义：>>> def foo(bar=[]):         # bar是可选参数，如果没有指明的话，默认值是[] ...    bar.append("baz")     # 但是这行可是有问题的，走着瞧… ...    return bar人们常犯的一个错误是认为每次调用这个函数时不给这个可选参数赋值的话，它总是会被赋予这个默认表达式的值。例如，在上面的代码中，程序员可能会认为重复调用函数foo() （不传参数bar给这个函数），这个函数会总是返回‘baz’，因为我们假定认为每次调用foo()的时候（不传bar），参数bar会被置为[]（即，一个空的列表）。相关推荐：《Python视频教程》那么我们来看看这么做的时候究竟会发生什么：>>> foo() ["baz"] >>> foo() ["baz", "baz"] >>> foo() ["baz", "baz", "baz"]嗯？为什么每次调用foo()的时候，这个函数总是在一个已经存在的列表后面添加我们的默认值“baz”，而不是每次都创建一个新的列表？答案是一个函数参数的默认值，仅仅在该函数定义的时候，被赋值一次。如此，只有当函数foo()第一次被定义的时候，才讲参数bar的默认值初始化到它的默认值（即一个空的列表）。当调用foo()的时候（不给参数bar），会继续使用bar最早初始化时的那个列表。由此，可以有如下的解决办法：>>> def foo(bar=None): ...    if bar is None:       # 或者用 if not bar: ...        bar = [] ...    bar.append("baz") ...    return bar ... >>> foo() ["baz"] >>> foo() ["baz"] >>> foo() ["baz"]