开发者

Python3实现自定义比较排序/运算符

开发者 https://www.devze.com 2022-12-10 11:10 出处:网络 作者: as1171799253
目录自定义比较排序/运算符1.cmp函数2.重写类方法python3实现各种排序方法自定义比较排序/运算符
目录
  • 自定义比较排序/运算符
    • 1.cmp函数
    • 2.重写类方法
  • python3实现各种排序方法

    自定义比较排序/运算符

    Python3和Python2相比有挺多变化。

    在Python2中可以直接写一个cmp函数作为参数传入sort来自定义排序,但是Python3取消了。

    在这里总结一下Python3的自定义排序的两种写法,欢迎补充。

    我们以二维空间中的点来作为待排序的数据结构,我们希望能先比较x后再比较y。

    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

    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=fwww.cppcns.comunctools.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中需要细分每一个比较运算符.

    __lt__: <
    __gt__: >
    __ge__: >=
    __eq__: ==
    __le__: <=

    实现如下

    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))
      http://www.cppcns.com      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__

    我们实践一下

    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!

    最后我们回到排序

    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实现各种排序方法

    # 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,http://www.cppcns.comleft,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 > middwww.cppcns.comle:
                copyBuffer[i] = lyst[i2]
            http://www.cppcns.com    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()
    

    以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

    0

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    关注公众号