转载请注明出处http://www.cnblogs.com/Wxtrkbc/p/5492298.html
在面试中,经常会遇到一些考排序算法的题,在这里,我就简单了列举了几种最常见的排序算法供大家学习,说不定以后哪天面试正好用上,文章后半段则介绍一下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函数,创 |