保研考研机试攻略：python笔记（3）

🐨🐨🐨11sort 与 sorted 区别

sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作。

list 的 sort 方法返回的是对已经存在的列表进行操作， 无返回值，而内建函数 sorted 方法返回的是一个 新的 list ，而不是在原来的基础上进行的操作。

注意： python 的sort排序为稳定排序，当条件都一致时，按照index的顺序排序

>>>a = [5,7,6,3,4,1,2]

>>> b = sorted(a)       # 保留原列表

>>> a

[5, 7, 6, 3, 4, 1, 2]

>>> b

[1, 2, 3, 4, 5, 6, 7]

>>> L=[('b',2),('a',1),('c',3),('d',4)]

>>> sorted(L, ,cmp=lambda x,y:cmp(x[1],y[1]))   # 利用cmp函数 cmp为对比函数

[('a', 1), ('b', 2), ('c', 3), ('d', 4)]

>>> sorted(L, key=lambda x:x[1])               # 利用key

[('a', 1), ('b', 2), ('c', 3), ('d', 4)]

>>> students = [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

>>> sorted(students, key=lambda s: s[2])            # 按年龄排序

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

>>> sorted(students, key=lambda s: s[2], reverse=True)       # 按降序

[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

🐨🐨🐨12Sorted Key用法

🐼key理解

 传递给key参数的是一个函数，它指定可迭代对象中的每一个元素来按照该函数进行排序。

# 这里先看一个不带key参数的sort()函数，大家很容易知道结果
li = [[1, 7], [1, 5], [2, 4], [1, 1]]
li.sort() 
print(li)
# [[1, 1], [1, 5], [1, 7], [2, 4]] 默认按照0维排序 再按照1维排序def fun(li):return li[1]
# 这时将函数fun传递给参数key 得出结果 ,也可使用匿名函数 li.sort(key=lambda x:x[1])
li.sort(key=fun)
print(li) # [[1, 1], [2, 4], [1, 5], [1, 7]]

🐶多条件排序

多条件排列规定，当1条件相同时，按2条件排序。

#按start从小到大排列， 如果start相同，则按end从小到大排列。
a = {'a': {'start': 10, 'end': 20}, 'd': {'start': 10, 'end': 19}, 'c': {'start': 13, 'end': 20}
}
#若想从大到小排序可以在条件前加-（数字可直接加-, 字符串用reverse=True）
d = sorted(a.keys(), key=lambda x: (a[x]['start'], a[x]['end']))# d = ['d', 'a', 'c']

多条件排序，不限于两个条件，如：

#按int(x[-1])排序，如果int(x[-1])相同，按x[0]排序，如x[0]相同，按x[1]排序
res = sorted(data,key=lambda x:(int(x[-1]),x[0],x[1]))

🐼cmp理解

sorted的key选择按数据的哪个条件进行排序， cmp则决定排序的规则，使用时加上key = functools.cmp_to_key（ cmp）参数实现。

import functoolsdef cmp_new(x,y):if (x+y)>(y+x):return 1elif (x+y)<(y+x):return -1 else :return 0n=input()
s=input().split()
s.sort(key=cmp_to_key(cmp_new),reverse=True) 
print(''.join(s).lstrip("0"))
#或者如下
s_new = sorted(s,key = functools.cmp_to_key(cmp_new),reserve=True) print(''.join(s_new).lstrip("0"))

🐶例题

对N个长度最长可达到1000的数进行排序。

import functools
#注意要返回具体的1，-1，0值，不能返回逻辑值。
def cmp_new(x, y):if len(x) == len(y):#此次是按从小到大排序if x > y:return 1elif x < y:return -1else:return 0#return x<y 不直接写成这样，要返回具体值如 1，-1，0else:if len(x) > len(y): return 1elif len(x) < len(y): return -1while True: try:n = int(input()) data = []for i in range(n):data.append(input())res = sorted(data, key=functools.cmp_to_key(cmp_new)) for v in res:print(v)except:break

🐨🐨🐨13队列

🐼定义

先进先出。队列类似于一条管道，元素先进先出,进put(arg)，取get( )。需要注意的是：队列都是在内存中操作， 进程退出，队列清空，另外，队列也是一个阻塞的形态。

🐼方法

🐼队列分类

队列有很多种，但都依赖模块queue。

队列方式	特点
queue.Queue	先进先出队列
queue.LifoQueue	后进先出队列
queue.PriorityQueue	优先级队列
queue.deque	双线队列

🐶单项队列

import queue#q=queue.Queue(5)    #如果不设置长度 ,默认为无限长
#print(q.maxsize)    #注意没有括号
from queue import Queue
# FIFO
queue_obj = Queue()  # 创建一个队列对象
for i in range(4):queue_obj.put(i)
while not queue_obj.empty(): print(queue_obj.get())# 输出顺序
0
1
2
3

🐶后进先出队列

q = queue.LifoQueue()
q.put(12)
q.put(34)
print(q.get())#34

🐶优先级队列

需要注意的是，优先级队列put的可以是单个值，可以是一个元组 ，(优先级,数据)，优先级数越小，级别越高。

q = queue.PriorityQueue() 
q.put((3,'aaaaa'))
q.put((3,'bbbbb')) 
q.put((1,'ccccc')) 
q.put((3,'ddddd')) 
print(q.get())
print(q.get())#(1, 'ccccc') 
#(3, 'aaaaa')

当优先级一样，数据部分可以比较大小的时候，也可以排序：

priorityQueue_obj = queue.PriorityQueue() 
priorityQueue_obj.put((1,45))
priorityQueue_obj.put((1,42)) 
priorityQueue_obj.put((1,47))
while not PriorityQueue_obj.empty(): print(PriorityQueue_obj.get())#(1, 42) 
#(1, 45) 
#(1, 47)priorityQueue_obj = PriorityQueue() 
priorityQueue_obj.put((1,[1,4]))
priorityQueue_obj.put((1,[2,4])) 
priorityQueue_obj.put((1,[2,3]))
while not PriorityQueue_obj.empty(): print(PriorityQueue_obj.get())#(1, [1, 4]) 
#(1, [2, 3]) 
#(1, [2, 4])#当优先级一样的时候，会在比较数据部分的大小，同上字符串也可以比较大小，

优先级一样，数据部分不可以比较大小时，程序会报错：

priorityQueue_obj = queue.PriorityQueue() 
priorityQueue_obj.put((1,{"1":9}))
priorityQueue_obj.put((1,{"k":6}))
priorityQueue_obj.put((1,{"8":9}))
while not priorityQueue_obj.empty():print(priorityQueue_obj.get())   
# 没有字典不能直接比较大小# 报错内容
# TypeError: '<' not supported between instances of 'dict' and 'dict'

🐶双线队列

from collections import deque 
q = deque()
q.append(123) 
q.append(456)
q.appendleft(780) 
print(q)
print(q.pop())#移除右边的元素，对应的append也不变
print(q.popleft())#移除左边的元素，对应的append为appendleft#deque([780, 123, 456]) 
#456
#780

🐨🐨🐨14各类排序

🐼插入排序

效率(N^2)

1. 将第一个数据当成已排序序列，后面的数据当成未排序序列。取未排序的第一个数据与已排序的最 后一个数据进行比较，如果顺序错误则交换位置。  17(未排序的第一个数据)比10(已排序的最后一个 数据)大，不需要进行交换。

2. 当不需要交换时则此轮插入完成。已排序序列变成了两个数据，未排序序列数据减1。

3. 继续取未排序的第一个数据与已排序的最后一个数据进行比较。如果顺序错误则交换位置。  50比17 大，不需要交换。

4. 第二轮插入完成，已排序序列数量加1，未排序序列减1。

5. 重复上面的步骤，未排序的第一个数据与已排序的最后一个数据进行比较。

6. 如果位置错误则交换位置。  7比50小，交换位置。

7. 交换位置后，继续将插入的数据与相邻的前一个数据进行比较。

8. 如果位置错误则交换位置。  7比17小，交换位置。

9. 重复步骤7，继续将插入的数据与相邻的前一个数据进行比较。

10. 如果位置错误则交换位置。  7比10小，交换位置。此时插入的数据已经通过交换位置到达了数列的 最前端，不需要再次交换了，此轮插入完成。

11. 一直重复取未排序的第一个数据插入已排序序列中，直到所有数据都已经插入到已排序序列中，列 表排序完成。排序结果如下图。

代码：

# coding=utf-8
def insertion_sort(array):for i in range(len(array)):cur_index = iwhile array[cur_index-1] > array[cur_index] and cur_index-1 >= 0:array[cur_index], array[cur_index-1] = array[cur_index-1], array[cur_index]#对新来数字在前已排序的序列中循环排序cur_index -= 1 return arrayif _name_== '_main_':array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] print(insertion_sort(array))

🐼希尔排序

希尔排序的具体思路步骤： (n等于列表的长度) 效率(最差N^2，最好N)

1）首先取一个整数d1 = n // 2 ，将元素分为d1个组，每组相邻元素之间的距离为d1,在各组内进行插入 排序

2）取第二个整数d2 = d1 // 2 ，重复上述分组排序，则到di =1时，即所有元素在同一组内进行插入排序 即可完成排序

3）希尔排序每趟并不是使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据 有序

第一次分组插入排序后： [3, 1, 2, 6, 5, 7, 4, 9, 8]

第二次分组插入排序后： [ 2,1,3,6,4,7,5,9,8 ]

第三次分组 d3 = d2 // 2 =1 则对 [ 2,1,3,6,4,7,5,9,8 ]进行插入排序，排序后[1, 2, 3, 4, 5, 6, 7, 8, 9]

代码：

def insert_sort_gap(li, gap):  # gap 代表分成几组for i in range(gap, len(li)):tmp = li[i]  # 第一组中下一个值 k = i - gap  # 第一组中前一个值 # 插入排序while k >= 0 and li[k] > tmp:li[k + gap] ,li[k] = li[k],li[k+gap] k -= gap#li[k + gap] = tmpprint(li)def shell_sort(li):  d = len(li) // 2 while d >= 1:insert_sort_gap(li, d)d //= 2#li = [5, 7, 4, 6, 3, 1, 2, 9, 8] 
#shell_sort(li)
#print(li)

🐼直接选择排序

最简单的排序，原理：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从 剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均 排序完毕。 效率(N^2)

代码：

def simpleSelect(a):# 简单选择排序: 小->大for i in range(0, len(a) - 1): min_index = i#找到i~len（a）的最小值的坐标for j in range(i, len(a)):  if a[min_index] > a[j]:min_index = ja[i], a[min_index] = a[min_index], a[i] return aprint simpleSelect([11, 1, 6, 9, 8, 5])

🐼快速排序

采用 “分而治之” 的思想，把大的拆分为小的，小的拆分为更小的。其原理是，对于给定的记录，选择一 个基准数，通过一趟排序后，将原序列分为两部分，使得前面的比后面的小，然后再依次对前后进行拆  分进行快速排序，递归该过程，直到序列中所有记录均有序。

步骤

设当前待排序序列为R[low:high]，其中low ≤ high ，如果待排序的序列规模足够小，则直接进行排序， 否则分3步处理。

1、分解

在R[low:high]中选定一个元素R[pivot]，以此为标准将要排序的序列划分为两个序列R[low:pivot-1]与

R[pivot+1： high]，并使序列R[low:pivot-1]中所有元素的值小于等于R[pivot]，序列R[pivot+1： high]所 有的值大于R[pivot]，此时基准元素以位于正确位置，它无需参加后续排序。

2、递归

对于子序列R[low:pivot-1]与R[pivot+1： high] ，分别调用快速排序算法来进行排序。

3、合并

由于对序列R[low:pivot-1]与R[pivot+1： high]的排序是原地进行的，所以R[low:pivot-1]与R[pivot+1： high]都已经排好序后，不需要进行任何计算，就已经排好序。

注：基准元素， 一般来说选取有几种方法

  取第一个元素

  取最后一个元素

  取第中间位置元素

  取第一个、最后一个、中间位置3者的中位数元素

图解

假设当前排序为R[low:high]，其中low ≤ high。

1：首先取序列第一个元素为基准元素pivot=R[low]。 i=low,j=high。 2：从后向前扫描，找小于等于

pivot的数，如果找到， R[i]与R[j]交换， i++。 3：从前往后扫描，找大于pivot的数，如果找到， R[i]与 R[j]交换，j--。 4:重复2~3，直到i=j,返回该位置mid=i,该位置正好为pivot元素。 完成一趟排序后，以

mid为界，将序列分为两部分，左序列都比pivot小，有序列都比pivot大，然后再分别对这两个子序列进 行快速排序。

以序列（30 ，24 ，5 ，58 ， 18 ，36 ， 12 ，42 ，39）为例，进行演示

 1、初始化， i=low,j=high,pivot=R[low]=30 

2、从后往前找小于等于pivot的数，找到R[j]=12

R[i]与R[j]交换， i++

3、从前往后找大于pivot的数，找到R[i]=58

R[i]与R[j]交换，j--

4、从后往前找小于等于pivot的数，找到R[j]=18

R[i]与R[j]交换， i++

5、从前往后找大于pivot的数，这时i=j,第一轮排序结束，返回i的位置， mid=i

此时已mid为界，将原序列一分为二，左子序列为（12 ，24 ，5 ， 18）元素都比pivot小，右子序列为    （ 36 ，58 ，42 ，39）元素都比pivot大。然后在分别对两个子序列进行快速排序，最后即可得到排序后 的结果。

   平均时间复杂度为： O(nlogn)

   平均空间复杂度为： O(logn)

代码：

def quickSort(list, i, j): if i >= j:return list pivot = list[i]# 保持上下界low = i  high = j# 寻找midwhile i < j:# 右值while i < j and list[j] > pivot: j -= 1# 在右值找到小于pivot的值，交换基准位置list[j], list[i] = list[i], list[j]# 注意要判断i，j不越界才能加减if i < j: i += 1# 左值while i < j and list[i] < pivot: i += 1# 在左值找到大于pivot的值，交换基准位置list[j], list[i] = list[i], list[j]# 注意要判断i，j不越界才能加减if i < j: j -= 1 mid = iquickSort(list, low, mid - 1)  quickSort(list, mid + 1, high) return listif _name_=="_main_":lists=[30,24,5,58,18,36,12,42,39]print("排序前的序列为：") for i in lists:print(i,end =" ")print("\n排序后的序列为：")for i in quick_sort(lists,0,len(lists)-1): print(i,end=" ")>>>
排序前的序列为：
30 24 5 58 18 36 12 42 39
排序后的序列为：
5 12 18 24 30 36 39 42 58#简单快排
def quick(array): if array==[]:return [] else:afirst = array[0]#无low，high交互，直接找出大于与小于基准的集合aless = quick([l for l in array[1:] if l < afirst])  amore = quick([m for m in array[1:] if m >= afirst]) return aless + [afirst] + amore

🐼二路归并排序算法

稳定排序，时间复杂度O(NLog(N))，空间复杂度O(N)

归并含义是将两个或两个以上的有序表组合成一个新的有序表。无论是顺序存储结构还是链表存储结 构，都可在O(m+n)的时间量级上实现。

合并两个有序数组过程：

例如 a = [1, 2] ， b = [0, 3, 4] 两个有序数组和一个空数组 res = [ ]，设置两个指针， i 指向 a 数组第一个  元素，j 指向 b 数组第一个元素。首先比较这两个元素 1 < 0，将0添加到 res 数组[0]；然后让 j 指针递    增指向 3 元素, 此时比较 i 和 j 指向元素 对比1 < 3,将 1 添加到 res 数组[0, 1] ； 让 i 指针递增指向2 元素, 此时比较 i 和 j 指向元素 对比2 < 3，将2添加到res数组[0, 1, 2]。这个时候 i = len(a)已经把 a 数组元素    添加完，还剩 b 数组中3 和 4元素，直接把剩下b数组元素添加到 res [0, 1, 2 ,3 , 4]，这样就实现了合并  两个有序数组为一个有序数组。

如此递归的分割排序后，再合并

代码：

def MergeSort(lists):  if len(lists) <=1:return listsnum = len(lists)//2left = MergeSort(lists[:num])  right = MergeSort(lists[num:]) return Merge(left,right)def Merge(left,right): r,l=0,0reslut=[]while l<len(left) and r<len(right):if left[l] < right[r]:reslut.append(left[l])l+=1 else:reslut.append(right[r])r+=1reslut+= right[r:] reslut+= left[l:]  return reslutif _name_== '_main_':arr = [4,2,15,4,6,7,1] print(MergeSort(arr))

文章内容摘自我学习的N诺python笔记，感兴趣的宝子欢迎关注专栏——《保研考研机试攻略》