Python3實(shí)現(xiàn)自定義比較排序/運(yùn)算符

更新時(shí)間：2022年02月09日 14:24:56 作者：as1171799253

這篇文章主要介紹了Python3實(shí)現(xiàn)自定義比較排序/運(yùn)算符，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

自定義比較排序/運(yùn)算符

Python3和Python2相比有挺多變化。

在Python2中可以直接寫一個(gè)cmp函數(shù)作為參數(shù)傳入sort來自定義排序，但是Python3取消了。

在這里總結(jié)一下Python3的自定義排序的兩種寫法，歡迎補(bǔ)充。

我們以二維空間中的點(diǎn)來作為待排序的數(shù)據(jù)結(jié)構(gòu)，我們希望能先比較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函數(shù)

第一種方法我們還是以重寫cmp或lambda表達(dá)式的形式，和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=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)) ?# ? ?親測(cè)此方法不能成功排序
? ? print(test_list) ?# 輸出結(jié)果 [(2, 4), (2, 5), (5, 1)]

2.重寫類方法

Python2中可以直接重寫__cmp__方法來實(shí)現(xiàn)比較，但是Python3中已經(jīng)取消了.

Python3中需要細(xì)分每一個(gè)比較運(yùn)算符.

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

實(shí)現(xiàn)如下

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__

我們實(shí)踐一下

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實(shí)現(xiàn)各種排序方法

# coding=gbk
import random
from array import array
def swap(lyst,i,j):
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp
#選擇排序，復(fù)雜度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
#冒泡排序，復(fù)雜的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
#冒泡排序優(yōu)化改進(jìn)最好情況
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
#插入排序，復(fù)雜的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
#快速排序,最好情況，復(fù)雜的O(n*(log2 n))，最壞情況，復(fù)雜的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()

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: