自定义比较排序/运算符
Python3和Python2相比有挺多变化。
在Python2中可以直接写一个cmp函数作为参数传入sort来自定义排序,但是Python3取消了。
在这里总结一下Python3的自定义排序的两种写法,欢迎补充。
我们以二维空间中的点来作为待排序的数据结构,我们希望能先比较x后再比较y。
1
2
3
4
5
6
7
8
9
|
class Pos: def __init__( self , x = 0 , y = 0 ): self .x = x self .y = y def __str__( self ): return ( '(%s, %s)' % ( self .x, self .y)) __repr__ = __str__ |
1.cmp函数
第一种方法我们还是以重写cmp或lambda表达式的形式,和Python2很类似
注意,此方法用sorted是不能成功排序的
只是要借助functools
1
2
3
4
5
6
7
8
9
10
11
|
import functools def cmp (a, b): return a.x - b.x if a.x ! = b.x else a.y - b.y # x y均按照从小到大的顺序 if __name__ = = '__main__' : test_list = [Pos( 5 , 1 ), Pos( 2 , 5 ), Pos( 2 , 4 )] # test_list.sort(key=functools.cmp_to_key(lambda a,b: a.x-b.x if a.x != b.x else a.y-b.y)) test_list.sort(key = functools.cmp_to_key( cmp )) # sorted(test_list, key=functools.cmp_to_key(cmp)) # 亲测此方法不能成功排序 print (test_list) # 输出结果 [(2, 4), (2, 5), (5, 1)] |
2.重写类方法
Python2中可以直接重写__cmp__方法来实现比较,但是Python3中已经取消了.
Python3中需要细分每一个比较运算符.
1
2
3
4
5
|
__lt__: < __gt__: > __ge__: > = __eq__: = = __le__: < = |
实现如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Pos: def __init__( self , x = 0 , y = 0 ): self .x = x self .y = y def __str__( self ): return ( '(%s, %s)' % ( self .x, self .y)) def __lt__( self , other): print ( 'lt: ' + str ( self )) return self .x < other.x if self .x ! = other.x else self .y < other.y def __gt__( self , other): print ( 'gt: ' + str ( self )) return self .x > other.x if self .x ! = other.x else self .y > other.y def __ge__( self , other): print ( 'ge: ' + str ( self )) return self .x > = other.x if self .x ! = other.x else self .y > = other.y def __eq__( self , other): print ( 'eq: ' + str ( self )) return self .x = = other.x and self .y = = other.y def __le__( self , other): print ( 'le: ' + str ( self )) return self .x < = other.x if self .x ! = other.x else self .y < = other.y __repr__ = __str__ |
我们实践一下
1
2
3
4
5
6
7
8
9
10
11
12
13
|
if __name__ = = '__main__' : if Pos( 5 , 1 ) < = Pos( 2 , 4 ): print ( 'True!' ) if Pos( 5 , 1 ) = = Pos( 2 , 4 ): print ( 'True!' ) if Pos( 5 , 1 ) > Pos( 2 , 4 ): print ( 'True!' ) # 输出 # le: (5, 1) # eq: (5, 1) # gt: (5, 1) # True! |
最后我们回到排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
if __name__ = = '__main__' : test_list = [Pos( 5 , 1 ), Pos( 2 , 5 ), Pos( 2 , 4 )] test_list.sort() print (test_list) test_list.sort(reverse = True ) print (test_list) # 输出 # lt: (2, 5) # lt: (2, 4) # [(2, 4), (2, 5), (5, 1)] # lt: (2, 5) # lt: (2, 4) # [(5, 1), (2, 5), (2, 4)] |
Python3实现各种排序方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
# coding=gbk import random from array import array def swap(lyst,i,j): temp = lyst[i] lyst[i] = lyst[j] lyst[j] = temp #选择排序,复杂度O(n^2) def selectionSort(lyst): i = 0 while i < len (lyst) - 1 : minIndex = i j = i + 1 while j < len (lyst): if lyst[j] < lyst[minIndex]: minIndex = j j + = 1 if minIndex ! = i: swap(lyst,minIndex,i) i + = 1 #冒泡排序,复杂的O(n^2) def bubbleSort(lyst): n = len (lyst) while n > 1 : i = 1 while i < n: if lyst[i] < lyst[i - 1 ]: swap(lyst,i,i - 1 ) i + = 1 n - = 1 #冒泡排序优化改进最好情况 def bubbleSortWithTweak(lyst): n = len (lyst) while n > 1 : swapped = False i = 1 while i < n: if lyst[i] < lyst[i - 1 ]: swap(lyst,i,i - 1 ) swapped = True i + = 1 if not swapped: return n - = 1 #插入排序,复杂的O(n^2) def insertionSort(lyst): i = 1 while i < len (lyst): itemToInsert = lyst[i] j = i - 1 while j > = 0 : if itemToInsert < lyst[j]: lyst[j + 1 ] = lyst[j] j - = 1 else : break lyst[j + 1 ] = itemToInsert i + = 1 #快速排序,最好情况,复杂的O(n*(log2 n)),最坏情况,复杂的O(n^2) def quicksort(lyst): quicksortHelper(lyst, 0 , len (lyst) - 1 ) def quicksortHelper(lyst,left,right): if left < right: pivotLocation = partition(lyst,left,right) quicksortHelper(lyst,left,pivotLocation - 1 ) quicksortHelper(lyst,pivotLocation + 1 ,right) def partition(lyst,left,right): middle = (left + right) / / 2 pivot = lyst[middle] lyst[middle] = lyst[right] lyst[right] = pivot boundary = left for index in range (left,right): if lyst[index] < pivot: swap(lyst,index,boundary) boundary + = 1 swap(lyst,right,boundary) return boundary #合并排序 def mergeSort(lyst): copyBuffer = [ 0 ] * ( len (lyst)) mergeSortHelper(lyst,copyBuffer, 0 , len (lyst) - 1 ) def mergeSortHelper(lyst,copyBuffer,low,high): if low < high: middle = (low + high) / / 2 mergeSortHelper(lyst,copyBuffer,low,middle) mergeSortHelper(lyst,copyBuffer,middle + 1 ,high) merge(lyst,copyBuffer,low,middle,high) def merge(lyst,copyBuffer,low,middle,high): i1 = low i2 = middle + 1 for i in range (low,high + 1 ): if i1 > middle: copyBuffer[i] = lyst[i2] i2 + = 1 elif i2 > high: copyBuffer[i] = lyst[i1] i1 + = 1 elif lyst[i1] < lyst[i2]: copyBuffer[i] = lyst[i1] i1 + = 1 else : copyBuffer[i] = lyst[i2] i2 + = 1 for i in range (low,high + 1 ): lyst[i] = copyBuffer[i] def main(size = 20 ,sort = mergeSort): lyst = [] for count in range (size): lyst.append(random.randint( 1 ,size + 1 )) print (lyst) sort(lyst) print (lyst) if __name__ = = "__main__" : main() |
以上为个人经验,希望能给大家一个参考,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/as1171799253/article/details/83685615