网站建设需要包含什么,wordpress边栏尺寸,部署自己做的网站吗,中小学生在线做试卷的网站#x1f428;#x1f428;#x1f428;11sort 与 sorted 区别
sort 是应用在 list 上的方法#xff0c;sorted 可以对所有可迭代的对象进行排序操作。
list 的 sort 方法返回的是对已经存在的列表进行操作#xff0c; 无返回值#xff0c;而内建函数 sorted 方法返回的…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, ,cmplambda x,y:cmp(x[1],y[1])) # 利用cmp函数 cmp为对比函数 [(a, 1), (b, 2), (c, 3), (d, 4)] sorted(L, keylambda x:x[1]) # 利用key [(a, 1), (b, 2), (c, 3), (d, 4)] students [(john, A, 15), (jane, B, 12), (dave, B, 10)] sorted(students, keylambda s: s[2]) # 按年龄排序 [(dave, B, 10), (jane, B, 12), (john, A, 15)] sorted(students, keylambda s: s[2], reverseTrue) # 按降序 [(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(keylambda x:x[1])
li.sort(keyfun)
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}
}
#若想从大到小排序可以在条件前加-数字可直接加-, 字符串用reverseTrue
d sorted(a.keys(), keylambda 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,keylambda 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 (xy)(yx):return 1elif (xy)(yx):return -1 else :return 0ninput()
sinput().split()
s.sort(keycmp_to_key(cmp_new),reverseTrue)
print(.join(s).lstrip(0))
#或者如下
s_new sorted(s,key functools.cmp_to_key(cmp_new),reserveTrue) print(.join(s_new).lstrip(0))
例题
对N个长度最长可达到1000的数进行排序。 import functools
#注意要返回具体的1-10值不能返回逻辑值。
def cmp_new(x, y):if len(x) len(y):#此次是按从小到大排序if x y:return 1elif x y:return -1else:return 0#return xy 不直接写成这样要返回具体值如 1-10else: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, keyfunctools.cmp_to_key(cmp_new)) for v in res:print(v)except:break13队列
定义
先进先出。队列类似于一条管道元素先进先出,进put(arg)取get( )。需要注意的是队列都是在内存中操作 进程退出队列清空另外队列也是一个阻塞的形态。
方法 队列分类
队列有很多种但都依赖模块queue。 队列方式 特点 queue.Queue 先进先出队列 queue.LifoQueue 后进先出队列 queue.PriorityQueue 优先级队列 queue.deque 双线队列
单项队列
import queue#qqueue.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. 一直重复取未排序的第一个数据插入已排序序列中直到所有数据都已经插入到已排序序列中列 表排序完成。排序结果如下图。 代码
# codingutf-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[kgap] 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~lena的最小值的坐标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[pivot1 high]并使序列R[low:pivot-1]中所有元素的值小于等于R[pivot]序列R[pivot1 high]所 有的值大于R[pivot]此时基准元素以位于正确位置它无需参加后续排序。
2、递归
对于子序列R[low:pivot-1]与R[pivot1 high] 分别调用快速排序算法来进行排序。
3、合并
由于对序列R[low:pivot-1]与R[pivot1 high]的排序是原地进行的所以R[low:pivot-1]与R[pivot1 high]都已经排好序后不需要进行任何计算就已经排好序。
注基准元素 一般来说选取有几种方法 取第一个元素 取最后一个元素 取第中间位置元素 取第一个、最后一个、中间位置3者的中位数元素
图解
假设当前排序为R[low:high]其中low ≤ high。
1首先取序列第一个元素为基准元素pivotR[low]。 ilow,jhigh。 2从后向前扫描找小于等于
pivot的数如果找到 R[i]与R[j]交换 i。 3从前往后扫描找大于pivot的数如果找到 R[i]与 R[j]交换j--。 4:重复2~3直到ij,返回该位置midi,该位置正好为pivot元素。 完成一趟排序后以
mid为界将序列分为两部分左序列都比pivot小有序列都比pivot大然后再分别对这两个子序列进 行快速排序。
以序列30 24 5 58 18 36 12 42 39为例进行演示 1、初始化 ilow,jhigh,pivotR[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的数这时ij,第一轮排序结束返回i的位置 midi 此时已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]# 注意要判断ij不越界才能加减if i j: i 1# 左值while i j and list[i] pivot: i 1# 在左值找到大于pivot的值交换基准位置list[j], list[i] list[i], list[j]# 注意要判断ij不越界才能加减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]#无lowhigh交互直接找出大于与小于基准的集合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(mn)的时间量级上实现。 合并两个有序数组过程 例如 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,l0,0reslut[]while llen(left) and rlen(right):if left[l] right[r]:reslut.append(left[l])l1 else:reslut.append(right[r])r1reslut right[r:] reslut left[l:] return reslutif _name_ _main_:arr [4,2,15,4,6,7,1] print(MergeSort(arr)) 文章内容摘自我学习的N诺python笔记感兴趣的宝子欢迎关注专栏——《保研考研机试攻略》
