List之sort、sorted高级排序-Python3.7 And 算法<七>

1、sort(*, key=None, reverse=False)

sort（）接受两个参数，这两个参数只能通过关键字（关键字参数）传递。

• 参数key：带一个参数的函数（排序时，会依次传入列表的每一项，作为该函数的参数）。该函数用于在比较排序之前进行的操作，e.g：每个字符串比较之前，需要统一小写。默认值None，说明每次比较排序之前不对比较项进行任何操作。
  

>>> test=["A","a","E","W","o"]
>>> test.sort()
>>> test
['A', 'E', 'W', 'a', 'o']
>>>
>>> test.sort(key=lambda x:x.lower())
>>> test
['A', 'a', 'E', 'o', 'W']
>>>

　　key还可以是比较函数functools.cmp_to_key(func)，该函数主要用 Python 3 之前Python版本，因为 Python 3 中不支持比较函数。

>>> from functools import cmp_to_key
>>> test=[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
>>> myKey=cmp_to_key(lambda x,y:y[0]-x[0] if x[0]!=y[0] else x[1]-y[1]) #x 代表后面的数 y代表前面的数
>>> test.sort(key=myKey)
>>> test
[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

• 参数reverse：在比较排序之后，是否要进行反向排序。传入True或False或能转换为True或False的值

>>> test=[2,3,4,5,6,3,4,1]
>>> test.sort()
>>> test=[2,3,4,5,6,3,4,1]
>>> test.sort(reverse=True)
>>> test
[6, 5, 4, 4, 3, 3, 2, 1]
>>>

>>> test=[2,3,4,5,6,3,4,1]
>>> test.sort(reverse=0)
>>> test
[1, 2, 3, 3, 4, 4, 5, 6]
>>>

 2、sorted(iterable, *, key=None, reverse=False)

不改变原排序，在原排序的副本上修改，返回新排序。其他与sort一样。

>>> test1=[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
>>> sorted(test1,key=myKey)
[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]] #返回新的排序
>>> test1
[[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]] #test1没变

 

插入一道算法题：

LeetCode.406. 根据身高重建队列<七>

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

思路：先按大到小排，先把大的排好队，小的在往大的队列插入，这样前面排好的队列就不会受到影响。

class Solution:
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        from functools import cmp_to_key
        key1 = cmp_to_key(lambda x, y: y[0] - x[0] if x[0] != y[0] else x[1] -y[1])
        people.sort(key=key1)  # 排完序后[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
        sort_people=[]
        for p in people:
            sort_people.insert(p[1],p)
        return sort_people