转载

Python全栈开发之5、几种常见的排序算法以及collections模块提供的数据结构

在面试中,经常会遇到一些考排序算法的题,在这里,我就简单了列举了几种最常见的排序算法供大家学习,说不定以后哪天面试正好用上,文章后半段则介绍一下collections模块,因为这个模块相对于python提供的基本数据结构(list,tuple,dict)不被人们所熟悉,但是如果你对他们了解的话,用起来也是非常方便高效的。

排序算法

一、冒泡排序(BubbleSort)

步骤:

  • 比较相邻的元素,如果第一个比第二个大,就交换他们两个。
  • 循环一遍后,最大的数就“浮”到了列表最后的位置。
  • 将剩下的数再次循环,直道所有的排序完成

代码如下:

def swap(a,b):            #一种巧妙交换两个数的位置而不用第三个变量的方法     a=b-a     b=b-a                 # b=b-(b-a) = a     a=b+a                 # a=a+(b-a) = b     return a,b  def BubbleSort(l):                      # 冒泡排序     for i in range(1,len(l)):         for j in range(0,len(l)-i):           # 每次循环减i是因为最后面的数已经排好序             if l[j]>l[j+1]:                 l[j],l[j+1]=l[j+1],l[j]        # 交换两个数,这里用的交换是python里面特有的交换方式     return l print(BubbleSort([555,2,3,2,3,1,19,3.5,27,24]))    # [1, 2, 2, 3, 3, 3.5, 19, 24, 27, 555]

二、选择排序 SelectionSort

步骤:

  • 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
  • 再从剩余未排序元素中继续寻找最小(大)元素,然后放到排序序列的起始。
  • 循环下去,直道所有的数排序完成

代码如下:

def SelectionSort(l):     for i in range(len(l)):         min = i                                     #存放最小元素的下标         for j in range(i+1,len(l)):             if l[j]<l[min]:                 min=j                              #记下最小元素的下标         l[i],l[min] = l[min],l[i]                  #将最小元素放到列表起始位置     return l print(SelectionSort([555,2,3,2,3,1,19,3.5,27,24]))   #[1, 2, 2, 3, 3, 3.5, 19, 24, 27, 555]

三、插入排序 InsertionSort

步骤:

  • 从第一个元素开始可以认为已经被排序,取出下一个元素,在已经排序的元素序列中从后向前扫描
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置,直到找到已排序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置后,如此反复循环,直道所有的排好序

代码如下:

def InsertionSort(l):     for i in range(1,len(l)):         if l[i]<l[i-1]:             temp=l[i]                               # 应该插入的数赋值给变量temp             for j in range(i-1,-1,-1):              # 从已排好的序列往前循环                 if l[j]>temp:                     l[j+1] = l[j]                     index=j                         # 记下应该插入的位置                 else:                     break             l[index]=temp     return l print(InsertionSort([555,2,3,2,3,1,19,3.5,27,24]))   # [1, 2, 2, 3, 3, 3.5, 19, 24, 27, 555]

四、快速排序 QuickSort

步骤:

  • 从数列中挑出一个元素作为基准数(这里我选择的是第一个数)
  • 将比基准数大的放到左边,小于或等于它的数都放到右边
  • 再对左右区间递归执行上一步,直至各区间只有一个数

代码如下:

#这里我用了递归和列表推到式(不明白列表推到式的可暂时跳过,后面讲到) def QuickSort(l):     if len(l)<=1:         return l     return QuickSort([lt for lt in l[1:] if lt<l[0]]) + l[0:1] + QuickSort([ge for ge in l[1:] if ge>=l[0]])  print(QuickSort([555,2,3,2,3,1,19,3.5,27,24]))   # [1, 2, 2, 3, 3, 3.5, 19, 24, 27, 555]

有关排序的算法暂时先写这么多,还有一些排序算法没有写,有的排序算法也可以用几种不同的方法实现,如果后续时间充足的话,再来完善,下面讲一下collctions模块

collections模块

一、deque

deque是一个双端队列,还记得以前的列表,一般情况下都是从尾部添加删除,而deque允许从任意一端增加或删除元素,deque的用法和list很像,下面的代码主要来看一下一些特有的用法,

#原生的list也可以从头部添加和取出元素,list对象的这两种用法的时间复杂度是 O(n) , #也就是说随着元素数量的增加耗时呈线性上升,而使用deque对象则是O(1)的复杂度 from collections import deque  d=deque('adf') print(type(d))                       # <class 'collections.deque'> d.appendleft([1,2,3])                # 从左端插入列别 print(d)                             # deque([[1, 2, 3], 'a', 'd', 'f']) d.extendleft('gssg')                 # 从左端扩展一个可迭代的对象 print(d)                             # deque(['g', 's', 's', 'g', [1, 2, 3], 'a', 'd', 'f']) print(d.popleft())                   # 左端删除元素 g print(d)                             # deque(['s', 's', 'g', [1, 2, 3], 'a', 'd', 'f']) d.rotate(1)                          # 1代表循环移动一步,相当于 d.appendleft(d.pop()) print(d)                             # deque(['f', 's', 's', 'g', [1, 2, 3], 'a', 'd']) print(d[4])                          #  支持索引,[1, 2, 3] for i in d:     print(i)                         # 支持for循环  # 除此之外,index(),append(),extend(),reverse(),remove(),pop(),insert()等方法和列表一样就不在说了

二、namedtuple

namedtuple()用来创建一个自定义的 tuple 对象,并且规定了 tuple 元素的个数,并可以用属性而不是索引来引用 tuple 的某个元素。

from collections import namedtuple # 如果我们想用元组表示一个点的话(x,y), # 这样写并不能很清楚的表达意思,这时候就可以用namedtuple, # 它具备tuple的不变性,又可以根据属性来引用  Point=namedtuple('Point',['x','y'])  # 用 namedtuple函数,创建一个自定义的tuple对象 Point p1=Point(11,y=2)                     # 创建一个实例 p1 p2=Point(2,3) print(p1.x)                          # 11  根据属性来获取值 print(p2[1])                         # 3   同样支持索引  p3=Point(*(55,22))                   # 传入元组的话用*转换 print(p3.x)                          # 55 p4=Point(**{'x':1,'y':1})            # 传入字典的话用**转换 print(p4.x)                          # 1

三、defaultdict

使用 dict 时,如果引用的Key不存在,就会抛出 KeyError,而且py3中没有has_key的方法,每次使用前需要使用in判断 。如果希望key不存在时,返回一个默认值,就可以用 defaultdict。

#传入一个默认的工厂方法,那么请求一个不存在的key时, #便会调用这个工厂方法使用其结果来作为这个key的默认值。  dd=defaultdict(lambda :'NA')         # 当key不存在调用lammbda函数 dd['x']=2 print(dd['y'])                       # 键不存在,返回NA print(dd['x'])                       # 存在,值为2 print(dd)                            # defaultdict(<function <lambda> at .., {'x': 2, 'y': 'NA'})  #defaultdict还有一种神奇的用法,用作统计,看下面的代码 s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)] d = defaultdict(list) for k, v in s:     d[k].append(v)  # key不存在的时候返回一个列表,然后用append添加相应的元素 print(d)            # defaultdict(<class 'list'>, {'yellow': [1, 3], 'red': [1], 'blue': [2, 4]})

四、OrderedDict

以前使用dict的时候,由于dict是无序的总是不能做循环迭代等,如果我们想保持Key的顺序可以使用OrderedDict,注意这里Key的顺序是指Key插入的顺序,而不是用Key本身排序。

from collections import OrderedDict od=OrderedDict() od['x']=1 od['y']=2 od['a']=3 print(od)             # OrderedDict([('x', 1), ('y', 2), ('a', 3)]) for i in od:     print(i)          # 打印顺序 x->y->a,读者可以下去多试几次看结果是否一样 print(od.popitem())   # 将('a', 3)弹出, LIFO(后进先出)

五、Counter

Counterdict 的一个子类,是一个简单的计数器,下面来看一下他的用法

from collections import Counter  c1=Counter('ddkhbb')           # 传入一个可迭代的对象 print(c1)                      # Counter({'d': 2, 'b': 2, 'h': 1, 'k': 1}) print(c1['d'])                 # 2  # 计数器的更新,增加 c1.update('kkk') print(c1)                      # Counter({'k': 4, 'd': 2, 'b': 2, 'h': 1})  # 计数器的更新,减少 c1.subtract('kkkkkkkk') print(c1)                      # Counter({'d': 2, 'b': 2, 'h': 1, 'k': -4})  # elements返回一个迭代器,元素被重复了多少次,在该迭代器中就包含多少个该元素。 # 个数小于1的元素不被包含。k数量小于1,就被排除了 print(list(c1.elements()))     # ['h', 'd', 'd', 'b', 'b']  print(c1.most_common(2))       #取出出现次数最多2个元素 [('b', 2), ('d', 2)]
原文  http://www.cnblogs.com/Wxtrkbc/p/5492298.html
正文到此结束
Loading...