🐨🐨🐨11sort 與 sorted 區(qū)別

sort 是應(yīng)用在 list 上的方法，sorted 可以對(duì)所有可迭代的對(duì)象進(jìn)行排序操作。

list 的 sort 方法返回的是對(duì)已經(jīng)存在的列表進(jìn)行操作， 無(wú)返回值，而內(nèi)建函數(shù) sorted 方法返回的是一個(gè) 新的 list ，而不是在原來(lái)的基礎(chǔ)上進(jìn)行的操作。

注意： python 的sort排序?yàn)?/span>穩(wěn)定排序，當(dāng)條件都一致時(shí)，按照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函數(shù) cmp為對(duì)比函數(shù)

[('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參數(shù)的是一個(gè)函數(shù)，它指定可迭代對(duì)象中的每一個(gè)元素來(lái)按照該函數(shù)進(jìn)行排序。

# 這里先看一個(gè)不帶key參數(shù)的sort()函數(shù)，大家很容易知道結(jié)果
li = [[1, 7], [1, 5], [2, 4], [1, 1]]
li.sort() 
print(li)
# [[1, 1], [1, 5], [1, 7], [2, 4]] 默認(rèn)按照0維排序 再按照1維排序def fun(li):return li[1]
# 這時(shí)將函數(shù)fun傳遞給參數(shù)key 得出結(jié)果 ,也可使用匿名函數(shù) li.sort(key=lambda x:x[1])
li.sort(key=fun)
print(li) # [[1, 1], [2, 4], [1, 5], [1, 7]]

🐶多條件排序

多條件排列規(guī)定，當(dāng)1條件相同時(shí)，按2條件排序。

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

多條件排序，不限于兩個(gè)條件，如：

#按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選擇按數(shù)據(jù)的哪個(gè)條件進(jìn)行排序， cmp則決定排序的規(guī)則，使用時(shí)加上key = functools.cmp_to_key（ cmp）參數(shù)實(shí)現(xiàn)。

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"))

🐶例題

對(duì)N個(gè)長(zhǎng)度最長(zhǎng)可達(dá)到1000的數(shù)進(jìn)行排序。

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隊(duì)列

🐼定義

先進(jìn)先出。隊(duì)列類似于一條管道，元素先進(jìn)先出,進(jìn)put(arg)，取get( )。需要注意的是：隊(duì)列都是在內(nèi)存中操作， 進(jìn)程退出，隊(duì)列清空，另外，隊(duì)列也是一個(gè)阻塞的形態(tài)。

🐼方法

🐼隊(duì)列分類

隊(duì)列有很多種，但都依賴模塊queue。

隊(duì)列方式	特點(diǎn)
queue.Queue	先進(jìn)先出隊(duì)列
queue.LifoQueue	后進(jìn)先出隊(duì)列
queue.PriorityQueue	優(yōu)先級(jí)隊(duì)列
queue.deque	雙線隊(duì)列

🐶單項(xiàng)隊(duì)列

import queue#q=queue.Queue(5)    #如果不設(shè)置長(zhǎng)度 ,默認(rèn)為無(wú)限長(zhǎng)
#print(q.maxsize)    #注意沒有括號(hào)
from queue import Queue
# FIFO
queue_obj = Queue()  # 創(chuàng)建一個(gè)隊(duì)列對(duì)象
for i in range(4):queue_obj.put(i)
while not queue_obj.empty(): print(queue_obj.get())# 輸出順序
0
1
2
3

🐶后進(jìn)先出隊(duì)列

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

🐶優(yōu)先級(jí)隊(duì)列

需要注意的是，優(yōu)先級(jí)隊(duì)列put的可以是單個(gè)值，可以是一個(gè)元組 ，(優(yōu)先級(jí),數(shù)據(jù))，優(yōu)先級(jí)數(shù)越小，級(jí)別越高。

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')

當(dāng)優(yōu)先級(jí)一樣，數(shù)據(jù)部分可以比較大小的時(shí)候，也可以排序：

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])#當(dāng)優(yōu)先級(jí)一樣的時(shí)候，會(huì)在比較數(shù)據(jù)部分的大小，同上字符串也可以比較大小，

優(yōu)先級(jí)一樣，數(shù)據(jù)部分不可以比較大小時(shí)，程序會(huì)報(bào)錯(cuò)：

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())   
# 沒有字典不能直接比較大小# 報(bào)錯(cuò)內(nèi)容
# TypeError: '<' not supported between instances of 'dict' and 'dict'

🐶雙線隊(duì)列

from collections import deque 
q = deque()
q.append(123) 
q.append(456)
q.appendleft(780) 
print(q)
print(q.pop())#移除右邊的元素，對(duì)應(yīng)的append也不變
print(q.popleft())#移除左邊的元素，對(duì)應(yīng)的append為appendleft#deque([780, 123, 456]) 
#456
#780

🐨🐨🐨14各類排序

🐼插入排序

效率(N^2)

1. 將第一個(gè)數(shù)據(jù)當(dāng)成已排序序列，后面的數(shù)據(jù)當(dāng)成未排序序列。取未排序的第一個(gè)數(shù)據(jù)與已排序的最 后一個(gè)數(shù)據(jù)進(jìn)行比較，如果順序錯(cuò)誤則交換位置。? 17(未排序的第一個(gè)數(shù)據(jù))比10(已排序的最后一個(gè) 數(shù)據(jù))大，不需要進(jìn)行交換。

2. 當(dāng)不需要交換時(shí)則此輪插入完成。已排序序列變成了兩個(gè)數(shù)據(jù)，未排序序列數(shù)據(jù)減1。

3. 繼續(xù)取未排序的第一個(gè)數(shù)據(jù)與已排序的最后一個(gè)數(shù)據(jù)進(jìn)行比較。如果順序錯(cuò)誤則交換位置。? 50比17 大，不需要交換。

4. 第二輪插入完成，已排序序列數(shù)量加1，未排序序列減1。

5. 重復(fù)上面的步驟，未排序的第一個(gè)數(shù)據(jù)與已排序的最后一個(gè)數(shù)據(jù)進(jìn)行比較。

6. 如果位置錯(cuò)誤則交換位置。? 7比50小，交換位置。

7. 交換位置后，繼續(xù)將插入的數(shù)據(jù)與相鄰的前一個(gè)數(shù)據(jù)進(jìn)行比較。

8. 如果位置錯(cuò)誤則交換位置。? 7比17小，交換位置。

9. 重復(fù)步驟7，繼續(xù)將插入的數(shù)據(jù)與相鄰的前一個(gè)數(shù)據(jù)進(jìn)行比較。

10. 如果位置錯(cuò)誤則交換位置。? 7比10小，交換位置。此時(shí)插入的數(shù)據(jù)已經(jīng)通過(guò)交換位置到達(dá)了數(shù)列的 最前端，不需要再次交換了，此輪插入完成。

11. 一直重復(fù)取未排序的第一個(gè)數(shù)據(jù)插入已排序序列中，直到所有數(shù)據(jù)都已經(jīng)插入到已排序序列中，列 表排序完成。排序結(jié)果如下圖。

代碼：

# 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]#對(duì)新來(lái)數(shù)字在前已排序的序列中循環(huán)排序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等于列表的長(zhǎng)度) 效率(最差N^2，最好N)

1）首先取一個(gè)整數(shù)d1 = n // 2 ，將元素分為d1個(gè)組，每組相鄰元素之間的距離為d1,在各組內(nèi)進(jìn)行插入 排序

2）取第二個(gè)整數(shù)d2 = d1 // 2 ，重復(fù)上述分組排序，則到di =1時(shí)，即所有元素在同一組內(nèi)進(jìn)行插入排序 即可完成排序

3）希爾排序每趟并不是使某些元素有序，而是使整體數(shù)據(jù)越來(lái)越接近有序；最后一趟排序使得所有數(shù)據(jù) 有序

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

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

第三次分組 d3 = d2 // 2 =1 則對(duì) [ 2,1,3,6,4,7,5,9,8 ]進(jìn)行插入排序，排序后[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]  # 第一組中下一個(gè)值 k = i - gap  # 第一組中前一個(gè)值 # 插入排序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)

🐼直接選擇排序

最簡(jiǎn)單的排序，原理：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)?/span> 剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均 排序完畢。 效率(N^2)

代碼：

def simpleSelect(a):# 簡(jiǎn)單選擇排序: 小->大for i in range(0, len(a) - 1): min_index = i#找到i~len（a）的最小值的坐標(biāo)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])

🐼快速排序

采用 “分而治之” 的思想，把大的拆分為小的，小的拆分為更小的。其原理是，對(duì)于給定的記錄，選擇一 個(gè)基準(zhǔn)數(shù)，通過(guò)一趟排序后，將原序列分為兩部分，使得前面的比后面的小，然后再依次對(duì)前后進(jìn)行拆? 分進(jìn)行快速排序，遞歸該過(guò)程，直到序列中所有記錄均有序。

步驟

設(shè)當(dāng)前待排序序列為R[low:high]，其中low ≤ high ，如果待排序的序列規(guī)模足夠小，則直接進(jìn)行排序， 否則分3步處理。

1、分解

在R[low:high]中選定一個(gè)元素R[pivot]，以此為標(biāo)準(zhǔn)將要排序的序列劃分為兩個(gè)序列R[low:pivot-1]與

R[pivot+1： high]，并使序列R[low:pivot-1]中所有元素的值小于等于R[pivot]，序列R[pivot+1： high]所 有的值大于R[pivot]，此時(shí)基準(zhǔn)元素以位于正確位置，它無(wú)需參加后續(xù)排序。

2、遞歸

對(duì)于子序列R[low:pivot-1]與R[pivot+1： high] ，分別調(diào)用快速排序算法來(lái)進(jìn)行排序。

3、合并

由于對(duì)序列R[low:pivot-1]與R[pivot+1： high]的排序是原地進(jìn)行的，所以R[low:pivot-1]與R[pivot+1： high]都已經(jīng)排好序后，不需要進(jìn)行任何計(jì)算，就已經(jīng)排好序。

注：基準(zhǔn)元素， 一般來(lái)說(shuō)選取有幾種方法

? 取第一個(gè)元素

? 取最后一個(gè)元素

? 取第中間位置元素

? 取第一個(gè)、最后一個(gè)、中間位置3者的中位數(shù)元素

圖解

假設(shè)當(dāng)前排序?yàn)?/span>R[low:high]，其中low ≤ high。

1：首先取序列第一個(gè)元素為基準(zhǔn)元素pivot=R[low]。 i=low,j=high。 2：從后向前掃描，找小于等于

pivot的數(shù)，如果找到， R[i]與R[j]交換， i++。 3：從前往后掃描，找大于pivot的數(shù)，如果找到， R[i]與 R[j]交換，j--。 4:重復(fù)2~3，直到i=j,返回該位置mid=i,該位置正好為pivot元素。 完成一趟排序后，以

mid為界，將序列分為兩部分，左序列都比pivot小，有序列都比pivot大，然后再分別對(duì)這兩個(gè)子序列進(jìn) 行快速排序。

以序列（30 ，24 ，5 ，58 ， 18 ，36 ， 12 ，42 ，39）為例，進(jìn)行演示

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

2、從后往前找小于等于pivot的數(shù)，找到R[j]=12

R[i]與R[j]交換， i++

3、從前往后找大于pivot的數(shù)，找到R[i]=58

R[i]與R[j]交換，j--

4、從后往前找小于等于pivot的數(shù)，找到R[j]=18

R[i]與R[j]交換， i++

5、從前往后找大于pivot的數(shù)，這時(shí)i=j,第一輪排序結(jié)束，返回i的位置， mid=i

此時(shí)已mid為界，將原序列一分為二，左子序列為（12 ，24 ，5 ， 18）元素都比pivot小，右子序列為??? （ 36 ，58 ，42 ，39）元素都比pivot大。然后在分別對(duì)兩個(gè)子序列進(jìn)行快速排序，最后即可得到排序后 的結(jié)果。

?? 平均時(shí)間復(fù)雜度為： O(nlogn)

?? 平均空間復(fù)雜度為： 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的值，交換基準(zhǔn)位置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的值，交換基準(zhǔn)位置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#簡(jiǎn)單快排
def quick(array): if array==[]:return [] else:afirst = array[0]#無(wú)low，high交互，直接找出大于與小于基準(zhǔn)的集合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

🐼二路歸并排序算法

例如 a = [1, 2] ， b = [0, 3, 4] 兩個(gè)有序數(shù)組和一個(gè)空數(shù)組 res = [ ]，設(shè)置兩個(gè)指針， i 指向 a 數(shù)組第一個(gè)? 元素，j 指向 b 數(shù)組第一個(gè)元素。首先比較這兩個(gè)元素 1 < 0，將0添加到 res 數(shù)組[0]；然后讓 j 指針遞??? 增指向 3 元素, 此時(shí)比較 i 和 j 指向元素 對(duì)比1 < 3,將 1 添加到 res 數(shù)組[0, 1] ； 讓 i 指針遞增指向2 元素, 此時(shí)比較 i 和 j 指向元素 對(duì)比2 < 3，將2添加到res數(shù)組[0, 1, 2]。這個(gè)時(shí)候 i = len(a)已經(jīng)把 a 數(shù)組元素??? 添加完，還剩 b 數(shù)組中3 和 4元素，直接把剩下b數(shù)組元素添加到 res [0, 1, 2 ,3 , 4]，這樣就實(shí)現(xiàn)了合并? 兩個(gè)有序數(shù)組為一個(gè)有序數(shù)組。

如此遞歸的分割排序后，再合并

代碼：

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èi)容摘自我學(xué)習(xí)的N諾python筆記，感興趣的寶子歡迎關(guān)注專欄——《保研考研機(jī)試攻略》