python 学习笔记

python不是有手就行吗？

python学习笔记

• python 学习笔记
• • python 运算符的用法：
  • • 算数运算符：
    • 赋值运算符：
    • 比较运算符（在 if 语句中也会提到）：
    • 逻辑运算符:
    • 优先级（非常重要）：
  • python 中 if 语句的用法：
  • • 只用 if 的：
    • 用 if 和 else 的：
    • 用 if 和 elif 和 else 的：
  • python 中循环语句的用法：
  • • for：
    • • 1.
      • 2.
    • while:
  • python 中一些有用的东西：
  • • 内置函数库：
    • 在 m a t h math math 库里的：
    • python 中的 STL：
    • • 字符串：
      • list：
      • queue：
      • stack：
      • deque：
      • set：
      • map：
      • 常用库函数：
      • • reverse()和reversed()：
        • sort和sorted：
        • 去重：
        • 随机打乱：
        • lower_bound:
        • upper_bound:

python 运算符的用法：

算数运算符：

赋值运算符：

比较运算符（在 if 语句中也会提到）：

先介绍一下布尔量是什么
布尔量只有 t r u e true true 和 f a l s e false false 两种量, 分别表示真或假

逻辑运算符:

非常重要! ! !
a=10,b=20

优先级（非常重要）：

python 中 if 语句的用法：

只用 if 的：

Python 编程中 if 语句用于控制程序的执行，基本形式为：

#判断条件可以用 "比较运算符" 来表示其关系
#如果需要多个条件同时判断时，可以使用逻辑运算符
if (判断条件…)：
	执行语句…

需要注意的是，python没有像其他大多数语言一样使用“{}”表示语句体，所以，它通过语句的缩进来判断语句体，缩进默认为4个空格，不要Tab和空格混用，否则回编译报错。（划重点）

用 if 和 else 的：

else 为可选语句，当需要在条件不成立时执行内容则可以执行相关语句：

if (判断条件…):
	执行语句…
else:
	执行语句…

用 if 和 elif 和 else 的：

当判断条件为多个值时，可以使用以下形式：

if (判断语句1…):
	执行语句1…
elif (判断语句2…)：
	执行语句2…
else:
	执行语句3…

python 中循环语句的用法：

循环语句一共有两种，分别是 for 和 while

for：

1.

#最简单的模板：
for i in range(1, n):
	执行语句…

这个式子的含义是将 i 的初始值赋为1，从1开始，每次加1，一直加到大于等于（n-1）

等于C++中的：

for (int i = 1; i < n; i++)
	执行语句…

2.

for i in range(1, n, 2):
	执行语句…

range里的值从两个变成了三个，这个式子的含义是将 i 的初始值赋为1，每次加 2，一直加到大于等于（n-1）

等于C++中的：

for (int i = 1; i < n; i += 2)
	执行语句…

while:

while (条件语句…):
	执行语句

非常好理解，重点就是在和许多STL套用的时候，需要你细心一点，分清每个语句的作用，多做题，灵活掌握即可。

python 中一些有用的东西：

内置函数库：

详细解析与举例

在 m a t h math math 库里的：

python 中的 STL：

python 竟然也有 STL！
STL大法好

• str
• List
• Queue
• stk
• Deque 双端队列
• Set
• Map
• 位运算
  常用库函数：

• 	翻转、去重、随机打乱、sort
  

• 	lower_bound/upper_bound
  

字符串：

# 字符串: 属于序列类型
def test2():
    print('--Hello World!--')  # --Hello World!--
    print("--Hello 'World'!--")  # --Hello 'World'!--
    print('''--'Hello' "World"--''')  # --'Hello' "World"--
    # 基础使用
    print("---------------------------------------")
    s = "0123456789"
    print(s[0])  # 获得s[0]  0
    print(s[0:2])  # 截取s[0, 2)的内容  01
    print(s[0:5:2])  # 每个两个截取s[0, 5)的内容  024
    print(s[0:-1])  # 最后一个字符被舍弃  012345678
    print(s[-4:])  # 截取最后四个字符  6789
    print(s[-1000:100])  # 首尾超过有效范围则取到首尾  0123456789
    print(s[::-1])  # 翻转字符串  9876543210
    print(2 * s)  # 复制两次字符串
    if "123" in s:
        print("'123'在字符串s中")
    else:
        print("'123'不在字符串s中")
    # 字符串处理函数
    print("---------------------------------------")
    print(len(s))  # 输出s的长度  10
    print(str("1.23"))
    print(ord('c'))  # unicode -> 数字
    print(chr(8364))  # 数字 -> unicode
    # 字符串处理方法
    print("---------------------------------------")
    t = "One world, one dream!"
    print(t.lower())  # 全部转为小写    one world, one dream!
    print(t.upper())  # 全部转为大写    ONE WORLD, ONE DREAM!
    print(t.count("one"))  # 计算某个字符换出现的次数    1
    print(t.replace("world", "life"))  # 将world全部替换为life
    print(t.center(30, "="))  # t居中，两侧用=填充    ====One world, one dream!=====
    print(t.strip("!O"))  # 从str中去掉在其左侧和右侧所列出的字符    ne world, one dream
    print("+".join("1234"))  # 1234用+隔开    1+2+3+4
    # 字符串格式化输出
    print("---------------------------------------")
    print("{0:.2f}".format(12345))  # 保留两位小数（四舍五入）    12345.00

list：

# list: 属于序列类型
def test3():
    # list创建
    s = [1, 2, "hi", (2, 3)]  # 或者 s = list([1, 2, "hi", (2, 3)])
    t = [[i + j for j in range(3)] for i in range(2)]
    # 序列类型通用操作符
    print("hi" in s)  # True
    print("hi" not in s)  # False
    print(s + t)  # [1, 2, 'hi', (2, 3), [0, 1, 2], [0, 1, 2]]
    print(2 * s)  # [1, 2, 'hi', (2, 3), 1, 2, 'hi', (2, 3)]
    print(s[2])  # hi
    print(s[1:3])  # 切片的详细信息请参考字符串    [2, 'hi']
    # 序列类型通用函数和方法
    print("---------------------------------------")
    print(len(s))  # 4
    print(min(t))  # 返回序列s的最小元素， s中元素需要可比较    [0, 1, 2]
    print(max(t))  # 返回序列s的最大元素， s中元素需要可比较    [1, 2, 3]
    print(s.index(2, 1, 3))  # 返回序列s从1开始到3位置中第一次出现元素2的位置，不存在产生ValueError异常
    print(s.count(12))  # 返回序列s中出现12的总次数    0

    # 列表类型操作函数和方法
    print("---------------------------------------")
    lt = []  # 定义空列表lt
    lt += [1, 2, 3, 4, 5]  # 向lt新增5个元素
    lt[2] = 6  # 修改lt中第2个元素  [1, 2, 6, 4, 5]
    lt.insert(2, 7)  # 向lt中第2个位置增加一个元素  [1, 2, 7, 6, 4, 5]
    del lt[1]  # [1, 7, 6, 4, 5]
    del lt[1:4]  # [1, 5]
    print(0 in lt)  # 判断lt中是否包含数字0  False
    lt.append(0)  # 向lt新增数字0  [1, 5, 0]
    print(lt.index(0))  # 返回数字0所在lt中的索引，不存在产生ValueError异常
    print(len(lt))  # lt的长度  3
    print(max(lt))  # lt中最大元素  5
    for x in lt:  # 遍历
        print(x, end=", ")
    print()
    for i, x in enumerate(lt):  # lt[i] = x
        print(i, x)
    lt.clear()  # 清空lt  []
    print("---------------------------------------")
    t = [i for i in range(5)]  # [0, 1, 2, 3, 4]
    t.pop(0)  # 删除列表中的头元素  [1, 2, 3, 4]
    t.append(3)  # 在列表的尾部添加元素3  [1, 2, 3, 4, 3]
    t.reverse()  # 反转列表  [3, 4, 3, 2, 1]
    t.remove(3)  # 删除第一个3  [4, 3, 2, 1]
    t.extend(["xyz", 'abc', 123])  # 追加一个列表  [4, 3, 2, 1, 'hi', 'k', 122]

queue：

# queue
def test2():
    # queue: 使用list模拟队列
    q = []  # 定义队列
    q.append(4)  # 入队  [4]
    q.append(3)  # 入队  [4, 3]
    q.append(7)  # 入队  [4, 3, 7]
    q.pop(0)  # 队首出队  [3, 7]
    print(q[0])  # 获得队首元素  3
    q.clear()  # 清空队列
    print(len(q))  # 获取队列中元素个数  0
    print(len(q) == 0)  # 判断队列是否为空  True

    # PriorityQueue: 默认小顶堆，是基于heapq实现的
    print("---------------------------------------")
    from queue import PriorityQueue
    heap = PriorityQueue()
    heap.put((2, 'hi'))
    heap.put((1, 'hello'))
    heap.put((3, 'world'))
    print(heap.queue)  # 输出堆中所有元素
    print(heap.queue[0])  # 输出堆顶元素, 不删除
    print(heap.get())  # 输出堆顶元素, 并删除堆顶元素
    print(heap.qsize())
    # python3中不能向PriorityQueue添加参数变为大顶堆，需要自己封装一个，可以参考下述网址
    # https://stackoverflow.com/questions/14189540/python-topn-max-heap-use-heapq-or-self-implement
    # 当做算法题使用到大顶堆是，不建议使用python
    import heapq
    class MaxHeap(object):
        def __init__(self, x):
            self.heap = [-e for e in x]
            heapq.heapify(self.heap)
        def put(self, value):
            heapq.heappush(self.heap, -value)
        def get(self):
            return -heapq.heappop(self.heap)

stack：

# stk
# stk
def test3():
    # python是没有栈的，我们可以列表模拟一个栈
    stk = []
    stk.append(20)  # 入栈
    stk.append(10)
    stk.append(30)
    stk.pop(len(stk) - 1)  # 出栈
    stk.clear()  # 清空栈
    print(len(stk))  # 获取栈中元素个数  0
    print(len(stk) == 0)  # 判断栈是否为空  True

deque：

# deque
def test4():
    from collections import deque
    # 定义 deque
    d = deque()
    # 插入、删除元素
    d.append(20)  # 队尾插入一个元素  deque([20])
    d.append(10)  # 队尾插入一个元素  deque([20, 10])
    d.pop()  # 弹出一个尾部数据  deque([20])
    d.appendleft(40)  # 队首插入一个元素  deque([40, 20])
    d.appendleft(30)  # 队首插入一个元素  deque([30, 40, 20])
    d.popleft()  # 弹出一个队首数据  deque([40, 20])
    # 遍历
    for x in d:
        print(x, end=", ")
    print()
    # 返回队首和队尾元素
    print(d[0])  # 队首元素  40
    print(d[len(d) - 1])  # 队尾元素  20
    # 清空 deque
    d.clear()
    print(len(d))  # 0
    print(len(d) == 0)  # True

set：

# set
def test5():
    """
    有序的集合：SortedSet
    网址：http://www.grantjenks.com/docs/sortedcontainers/sortedset.html
    """
    from sortedcontainers import SortedSet
    # 创建 SortedSet
    ss = SortedSet([3, 1, 2, 5, 4])
    print(ss)  # SortedSet([1, 2, 3, 4, 5])
    from operator import neg
    ss1 = SortedSet([3, 1, 2, 5, 4], neg)
    print(ss1)  # SortedSet([5, 4, 3, 2, 1], key=<built-in function neg>)
    # SortedSet 转为 list/tuple/set
    print(list(ss))  # SortedSet转为list    [1, 2, 3, 4, 5]
    print(tuple(ss))  # SortedSet转为tuple    (1, 2, 3, 4, 5)
    print(set(ss))  # SortedSet转为set    {1, 2, 3, 4, 5}
    # 插入、删除元素
    ss.discard(-1)  # 删除不存在的元素不报错
    ss.remove(1)  # 删除不存在的元素报错, KeyError
    ss.discard(3)  # SortedSet([1, 2, 4, 5])
    ss.add(-10)  # SortedSet([-10, 1, 2, 4, 5])
    # 返回第一个和最后一个元素
    print(ss[0])  # -10
    print(ss[-1])  # 5
    # 遍历 set
    for e in ss:
        print(e, end=", ")  # -10, 2, 4, 5,
    print()
    # set 中判断某元素是否存在
    print(2 in ss)  # True
    # bisect_left() / bisect_right()
    print(ss.bisect_left(4))  # 返回大于等于4的最小元素对应的下标    2
    print(ss.bisect_right(4))  # 返回大于4的最小元素对应的下标    3
    # 清空 set
    ss.clear()
    print(len(ss))  # 0
    print(len(ss) == 0)  # True

    """
    无序的集合: set
    """
    # 集合的定义：集合是不可变的，因此集合中元素不能是list
    A = {"hi", 2, ("we", 24)}
    B = set()  # 空集合的定义，不能使用B = {}定义集合，这样是字典的定义
    # 集合间的操作, 下面的运算法符都可以写成 op= 的形式
    print("---------------------------------------")
    S = {1, 2, 3}
    T = {3, 4, 5}
    print(S & T)  # 交集，返回一个新集合，包括同时在集合S和T中的元素
    print(S | T)  # 并集，返回一个新集合，包括在集合S和T中的所有元素
    print(S - T)  # 差集，返回一个新集合，包括在集合S但不在T中的元素
    print(S ^ T)  # 补集，返回一个新集合，包括集合S和T中的非相同元素
    # 集合的包含关系
    print("---------------------------------------")
    C = {1, 2}
    D = {1, 2}
    print(C <= D)  # C是否是D的子集  True
    print(C < D)  # C是否是D的真子集  False
    print(C >= D)  # D是否是C的子集  True
    print(C > D)  # D是否是C的真子集  False
    # 集合的处理方法
    print("---------------------------------------")
    S = {1, 2, 3, 5, 6}
    S.add(4)  # 如果x不在集合S中，将x增加到S
    S.discard(1)  # 移除S中元素x，如果x不在集合S中，不报错
    S.remove(2)  # 移除S中元素x，如果x不在集合S中，产生KeyError异常
    for e in S:  # 遍历
        print(e, end=",")
    print()
    print(S.pop())  # 从S中随机弹出一个元素，S长度减1，若S为空产生KeyError异常
    print(S.copy())  # 返回集合S的一个副本, 对该副本的操作不会影响S
    print(len(S))  # 返回集合S的元素个数
    print(5 in S)  # 判断S中元素x， x在集合S中，返回True，否则返回False
    print(5 not in S)  # 判断S中元素x， x在集合S中，返回True，否则返回False
    S.clear()  # 移除S中所有元素

# SortedList: 类似于C++中的multiset
def _test5():
    """
    网址：http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html
    """
    from sortedcontainers import SortedList
    # 定义
    sl = SortedList(key=lambda x: -x)  # 降序
    sl = SortedList([3, 1, 2, 1, 5, 4])  # 升序
    print(sl)  # SortedList([1, 1, 2, 3, 4, 5])
    # 插入、删除元素
    sl.add(3)
    sl.add(3)
    sl.discard(2)  # SortedList([1, 1, 3, 3, 3, 4, 5])
    print(sl)
    # 统计某个元素出现的次数
    print(sl.count(3))  # 3
    # 返回第一个和最后一个元素
    print(sl[0])  # 1
    print(sl[-1])  # 5
    # 遍历 set
    for e in sl:
        print(e, end=", ")  # 1, 1, 3, 3, 3, 4, 5,
    print()
    # 判断某元素是否存在
    print(2 in sl)  # False
    # bisect_left() / bisect_right()
    print(sl.bisect_left(3))  # 返回大于等于3的最小元素对应的下标    2
    print(sl.bisect_right(3))  # 返回大于3的最小元素对应的下标    5
    # 清空
    sl.clear()
    print(len(sl))  # 0
    print(len(sl) == 0)  # True

map：

# map
def test6():
    """
    有序的map: SortedDict
    网址: http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html
    """
    from sortedcontainers import SortedDict
    sd = SortedDict()
    # 插入、删除元素
    sd["wxx"] = 21
    sd["hh"] = 18
    sd["other"] = 20
    print(sd)  # SortedDict({'hh': 18, 'other': 20, 'wxx': 21})
    print(sd["wxx"])  # 访问不存在的键会报错, KeyError
    print(sd.get("c"))  # 访问不存在的键会返回None     None
    # SortedDict转dict
    print(dict(sd))  # {'hh': 18, 'other': 20, 'wxx': 21}
    # 返回最后一个元素和最后一个元素
    print(sd.peekitem(0))  # 类型tuple, 返回第一个元素    ('hh', 18)
    print(sd.peekitem())  # 类型tuple, 返回最后一个元素    ('wxx', 21)
    # 遍历
    for k, v in sd.items():
        print(k, ':', v, sep="", end=", ")  # sep取消每行输出之间的空格
    print()
    for k in sd:  # 遍历键k, 等价于for k in d.keys:
        print(str(k) + ":" + str(sd[k]), end=", ")
    print()
    for v in sd.values():  # 遍历值v
        print(v, end=", ")
    print()
    # 返回Map中的一个键
    print(sd.peekitem()[0])
    # 返回Map中的一个值
    print(sd.peekitem()[1])
    # 中判断某元素是否存在
    print("wxx" in sd)  # True
    # bisect_left() / bisect_right()
    sd["a"] = 1
    sd["c1"] = 2
    sd["c2"] = 4
    print(sd)  # SortedDict({'a': 1, 'c1': 2, 'c2': 4, 'hh': 18, 'other': 20, 'wxx': 21})
    print(sd.bisect_left("c1"))  # 返回键大于等于"c1"的最小元素对应的下标    1
    print(sd.bisect_right("c1"))  # 返回键大于"c1"的最小元素对应的下标    2
    # 清空
    sd.clear()
    print(len(sd))  # 0
    print(len(sd) == 0)  # True

    """
    无序的map: dict
    """
    print("---------------------------------------")
    d = {"c1": 2, "c2": 4, "hh": 18, "wxx": 21, 13: 14, 1: 0}
    print(d["wxx"])  # 21
    print(d[13])  # 14
    d[13] += 1
    print(d[13])  # 15
    d["future"] = "wonderful"  # 字典中添加键值对
    del d[1]  # 删除字典d中键1对应的数据值
    print("wxx" in d)  # 判断键"wxx"是否在字典d中，如果在返回True，否则False
    print(d.keys())  # 返回字典d中所有的键信息  dict_keys(['c1', 'c2', 'hh', 'wxx', 13])
    print(d.values())  # 返回字典d中所有的值信息  dict_values([2, 4, 18, 21, 14])
    print(d.items())  # dict_items([('c1', 2), ('c2', 4), ('hh', 18), ('wxx', 21), (13, 14)])
    for k, v in d.items():  # 遍历 k, v
        print(k, ':', v)
    for k in d:  # 遍历键k, 等价于for k in d.keys:
        print(str(k) + ":" + str(d[k]), end=", ")
    print()
    for v in d.values():  # 遍历值v
        print(v, end=", ")
    print()
    # 字典类型操作函数和方法
    print("---------------------------------------")
    d = {"中国": "北京", "美国": "华盛顿", "法国": "巴黎"}
    print(len(d))  # 返回字典d中元素的个数  3
    print(d.get("中国", "不存在"))  # 键k存在，则返回相应值，不在则返回<default>值  北京
    print(d.get("中", "不存在"))  # 不存在
    print(d.get("中"))  # None
    d["美国"] = "Washington"  # 修改键对应的值
    print(d.pop("美国"))  # 键k存在，则返回相应值，并将其从dict中删除
    print(d.popitem())  # 随机从字典d中取出一个键值对，以元组形式返回，并将其从dict中删除
    d.clear()  # 删除所有的键值对

常用库函数：

reverse()和reversed()：

reverse()方法：
属于列表的内置方法（即在字典、元组、字符串中没有这个内置方法），可用于列表中数据的翻转。
需要注意的是reverse()方法是直接对原列表进行翻转，没有返回值。

list = [1, 2, 3, 4]
lista.reverse()
print(list)

打印结果：

[4, 3, 2, 1]

reversed()方法:
属于python自带的一个方法，可用于列表、元组和字符串等。
1.列表的翻转:

a = [1,3,5,7]
print(list(reversed(a)))

2.元组的翻转:

a = (1, 2, 3)
print(tuple(reversed(a)))

打印结果：

[3, 2, 1]

3.字符串的翻转
使用join方法

ss = "qwer1234"
print(''.join(reversed(ss)))

打印结果：

4321rewq

sort和sorted：

Python list内置sort()方法用来排序，也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列。
 

1）排序基础
简单的升序排序是非常容易的。只需要调用sorted()方法。它返回一个新的list，新的list的元素基于小于运算符(__lt__)来排序。
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]
 
你也可以使用list.sort()方法来排序，此时list本身将被修改。通常此方法不如sorted()方便，但是如果你不需要保留原来的list，此方法将更有效。

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
 
另一个不同就是list.sort()方法仅被定义在list中，相反地sorted()方法对所有的可迭代序列都有效。

 

>>> sorted({1:  ' D ', 2:  ' B ', 3:  ' B ', 4:  ' E ', 5:  ' A '})
[1, 2, 3, 4, 5]
 

 
2）key参数/函数

从python2.4开始，list.sort()和sorted()函数增加了key参数来指定一个函数，此函数将在每个元素比较前被调用。 例如通过key指定的函数来忽略字符串的大小写：
>>> sorted( " This is a test string from Andrew ".split(), key=str.lower)
[ ' a ',  ' Andrew ',  ' from ',  ' is ',  ' string ',  ' test ',  ' This ']
 
key参数的值为一个函数，此函数只有一个参数且返回一个值用来进行比较。这个技术是快速的因为key指定的函数将准确地对每个元素调用。

 
更广泛的使用情况是用复杂对象的某些值来对复杂对象的序列排序，例如：

>>> student_tuples = [
        ( ' john ',  ' A ', 15),
        ( ' jane ',  ' B ', 12),
        ( ' dave ',  ' B ', 10),
]
>>> sorted(student_tuples, key= lambda student: student[2])    #  sort by age
[( ' dave ',  ' B ', 10), ( ' jane ',  ' B ', 12), ( ' john ',  ' A ', 15)]
 
同样的技术对拥有命名属性的复杂对象也适用，例如：

>>>  class Student:
         def  __init__(self, name, grade, age):
                self.name = name
                self.grade = grade
                self.age = age
         def  __repr__(self):
                 return repr((self.name, self.grade, self.age))
>>> student_objects = [
        Student( ' john ',  ' A ', 15),
        Student( ' jane ',  ' B ', 12),
        Student( ' dave ',  ' B ', 10),
]
>>> sorted(student_objects, key= lambda student: student.age)    #  sort by age
[( ' dave ',  ' B ', 10), ( ' jane ',  ' B ', 12), ( ' john ',  ' A ', 15)]
 
3）Operator 模块函数

上面的key参数的使用非常广泛，因此python提供了一些方便的函数来使得访问方法更加容易和快速。operator模块有itemgetter，attrgetter，从2.6开始还增加了methodcaller方法。使用这些方法，上面的操作将变得更加简洁和快速：
>>>  from operator  import itemgetter, attrgetter
>>> sorted(student_tuples, key=itemgetter(2))
[( ' dave ',  ' B ', 10), ( ' jane ',  ' B ', 12), ( ' john ',  ' A ', 15)]
>>> sorted(student_objects, key=attrgetter( ' age '))
[( ' dave ',  ' B ', 10), ( ' jane ',  ' B ', 12), ( ' john ',  ' A ', 15)]
 
operator模块还允许多级的排序，例如，先以grade，然后再以age来排序：

>>> sorted(student_tuples, key=itemgetter(1,2))
[( ' john ',  ' A ', 15), ( ' dave ',  ' B ', 10), ( ' jane ',  ' B ', 12)]
>>> sorted(student_objects, key=attrgetter( ' grade ',  ' age '))
[( ' john ',  ' A ', 15), ( ' dave ',  ' B ', 10), ( ' jane ',  ' B ', 12)]
 
4）升序和降序

list.sort()和sorted()都接受一个参数reverse（True or False）来表示升序或降序排序。例如对上面的student降序排序如下：
>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[( ' john ',  ' A ', 15), ( ' jane ',  ' B ', 12), ( ' dave ',  ' B ', 10)]
>>> sorted(student_objects, key=attrgetter( ' age '), reverse=True)
[( ' john ',  ' A ', 15), ( ' jane ',  ' B ', 12), ( ' dave ',  ' B ', 10)]
 
5）排序的稳定性和复杂排序

从python2.2开始，排序被保证为稳定的。意思是说多个元素如果有相同的key，则排序前后他们的先后顺序不变。
>>> data = [( ' red ', 1), ( ' blue ', 1), ( ' red ', 2), ( ' blue ', 2)]
>>> sorted(data, key=itemgetter(0))
[( ' blue ', 1), ( ' blue ', 2), ( ' red ', 1), ( ' red ', 2)]
注意在排序后'blue'的顺序被保持了，即'blue', 1在'blue', 2的前面。
 
更复杂地你可以构建多个步骤来进行更复杂的排序，例如对student数据先以grade降序排列，然后再以age升序排列。

>>> s = sorted(student_objects, key=attrgetter( ' age '))      #  sort on secondary key
>>> sorted(s, key=attrgetter( ' grade '), reverse=True)        #  now sort on primary key, descending
[( ' dave ',  ' B ', 10), ( ' jane ',  ' B ', 12), ( ' john ',  ' A ', 15)]
 

6）最老土的排序方法-DSU
我们称其为DSU（Decorate-Sort-Undecorate）,原因为排序的过程需要下列三步：
第一：对原始的list进行装饰，使得新list的值可以用来控制排序；
第二：对装饰后的list排序；
第三：将装饰删除，将排序后的装饰list重新构建为原来类型的list；
 

例如，使用DSU方法来对student数据根据grade排序：
>>> decorated = [(student.grade, i, student)  for i, student  in enumerate(student_objects)]
>>> decorated.sort()
>>> [student  for grade, i, student  in decorated]                #  undecorate
[( ' john ',  ' A ', 15), ( ' jane ',  ' B ', 12), ( ' dave ',  ' B ', 10)]
上面的比较能够工作，原因是tuples是可以用来比较，tuples间的比较首先比较tuples的第一个元素，如果第一个相同再比较第二个元素，以此类推。
 

并不是所有的情况下都需要在以上的tuples中包含索引，但是包含索引可以有以下好处：
第一：排序是稳定的，如果两个元素有相同的key，则他们的原始先后顺序保持不变；
第二：原始的元素不必用来做比较，因为tuples的第一和第二元素用来比较已经是足够了。
 

此方法被RandalL.在perl中广泛推广后，他的另一个名字为也被称为Schwartzian transform。
 

对大的list或list的元素计算起来太过复杂的情况下，在python2.4前，DSU很可能是最快的排序方法。但是在2.4之后，上面解释的key函数提供了类似的功能。
 

7）其他语言普遍使用的排序方法-cmp函数
在python2.4前，sorted()和list.sort()函数没有提供key参数，但是提供了cmp参数来让用户指定比较函数。此方法在其他语言中也普遍存在。
 

在python3.0中，cmp参数被彻底的移除了，从而简化和统一语言，减少了高级比较和__cmp__方法的冲突。
 

在python2.x中cmp参数指定的函数用来进行元素间的比较。此函数需要2个参数，然后返回负数表示小于，0表示等于，正数表示大于。例如：
>>>  def numeric_compare(x, y):
         return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)
[1, 2, 3, 4, 5]
 
或者你可以反序排序：

>>>  def reverse_numeric(x, y):
         return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric)
[5, 4, 3, 2, 1]
 
当我们将现有的2.x的代码移植到3.x时，需要将cmp函数转化为key函数，以下的wrapper很有帮助：

def cmp_to_key(mycmp):
     ' Convert a cmp= function into a key= function '
     class K(object):
         def  __init__(self, obj, *args):
            self.obj = obj
         def  __lt__(self, other):
             return mycmp(self.obj, other.obj) < 0
         def  __gt__(self, other):
             return mycmp(self.obj, other.obj) > 0
         def  __eq__(self, other):
             return mycmp(self.obj, other.obj) == 0
         def  __le__(self, other):
             return mycmp(self.obj, other.obj) <= 0
         def  __ge__(self, other):
             return mycmp(self.obj, other.obj) >= 0
         def  __ne__(self, other):
             return mycmp(self.obj, other.obj) != 0
     return K
 
当需要将cmp转化为key时，只需要：

>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]
从python2.7，cmp_to_key()函数被增加到了functools模块中。 



8)其他注意事项
* 对需要进行区域相关的排序时，可以使用locale.strxfrm()作为key函数，或者使用local.strcoll()作为cmp函数。
 

* reverse参数任然保持了排序的稳定性，有趣的时，同样的效果可以使用reversed()函数两次来实现：
>>> data = [( ' red ', 1), ( ' blue ', 1), ( ' red ', 2), ( ' blue ', 2)]
>>>  assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data))))
 
* 其实排序在内部是调用元素的__cmp__来进行的，所以我们可以为元素类型增加__cmp__方法使得元素可比较，例如：

>>> Student. __lt__ =  lambda self, other: self.age < other.age
>>> sorted(student_objects)
[( ' dave ',  ' B ', 10), ( ' jane ',  ' B ', 12), ( ' john ',  ' A ', 15)]
 
* key函数不仅可以访问需要排序元素的内部数据，还可以访问外部的资源，例如，如果学生的成绩是存储在dictionary中的，则可以使用此dictionary来对学生名字的list排序，如下：

>>> students = [ ' dave ',  ' john ',  ' jane ']
>>> newgrades = { ' john ':  ' F ',  ' jane ': ' A ',  ' dave ':  ' C '}
>>> sorted(students, key=newgrades. __getitem__)
[ ' jane ',  ' dave ',  ' john ']
 

*当你需要在处理数据的同时进行排序的话，sort(),sorted()或bisect.insort()不是最好的方法。在这种情况下，可以使用heap，red-black tree或treap。

或者：

# sort
# 可以参考：https://blog.csdn.net/weixin_41611054/article/details/113934296
def test10():
    # list成员函数sort()
    arr = [3, 5, 1, 6, 9, 2]
    arr.sort()  # 作用在arr上
    print(arr)  # [1, 2, 3, 5, 6, 9]
    # list成员函数sort() 自定义比较
    arr = [(2, 2), (3, 4), (4, 1), (1, 3)]
    def cmp(e):
        return e[1]
    arr.sort(reverse=True, key=cmp)  # 根据第二维降序排列
    print(arr)
    arr.sort(key=lambda x: (-x[0], x[1]))  # 第一维降序，第二维升序排列
    print(arr)

    # sorted
    print("---------------------------------------")
    arr = [3, 5, 1, 6, 9, 2]
    print(sorted(arr))  # 返回排序(默认升序)后的list
    print(sorted(arr, reverse=True))  # 返回排序(降序)后的list
    # sorted 自定义比较
    arr = [(2, 2), (3, 4), (4, 1), (1, 3)]
    print(sorted(arr, key=lambda e: -e[1]))  # 根据第二维降序排列

    # sorted对dict排序
    print("---------------------------------------")
    d = {'c': 21, 'a': 24, 'b': 12}
    print(sorted(d))  # 返回list  ['a', 'b', 'c']
    print(sorted(d.items()))  # 返回list  [('a', 24), ('b', 21), ('c', 12)]
    print(sorted(d.items(), key=lambda e: e[1], reverse=True))  # 按照值降序排列

去重：

# 方法一
# 利用集合的元素唯一性，对列表进行去重
def three_question():
    li = [11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    se = set(li)
    print('列表中不重复元素个数：',len(se))

# three_question()

# 方法二
# 定义一个空列表，用for循环遍历要去重的列表，判断不存在与新定义的空列表的元素就添加实现去#重
def three_question02():
    li = [11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    li2 = []
    for item in li:
        if item not in li2:
            li2.append(item)
        else:
            continue
    print('列表中不重复元素个数：',len(li2))

# three_question02()

# 方法三
# 利用嵌套for循环，比对出重复元素进行删除操作，实现列表去重
def three_question03():
    li = [11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    num=0
    for item in li[0:]:
        num+=1
        for id in li[num:]:
            if id == item:
                li.remove(id)
            else:
                continue
    print(li)
    print('列表中不重复元素个数：', len(li))

# three_question03()

# 第四种 将值转化为字典的键值,利用键值的唯一性
def three_question04():
    print("第三种 将值转化为字典的键值,利用键值的唯一性")
    li=[11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    dict1={}
    for i in li:
        dict1[i]=i
    number=len(dict1)
    print("列表中不重复的元素个数为：{}".format(number))

# three_question04()

# 方法五：
def three_question05():
    li = [11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    li3 =[]
    s=set()
    for i in li:
        if li.count(i) == 1:
            if i not in li3:
                li3.append(i)
        elif li.count(i)>1:
            s.add(i)
    for se in s:
        li3.append(se)
    print('不重复元素个数',len(li3))

# three_question05()

# 方法六：
def three_question06():
    li = [11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    li3 =[]
    s={}
    for i in li:
        if li.count(i) == 1:
            if i not in li3:
                li3.append(i)
        elif li.count(i)>1:
            s[i]=i
    for se in s.values():
        li3.append(se)
    print('不重复元素个数',len(li3))

# three_question06()



#方法七:(利用字典健值去重)字典函数去重

def three_question07():
    li=[11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    d = {}
    d = d.fromkeys(li)
    li2 = list(d.keys())
    print(li2)
    print('不重复元素个数', len(li2))

# three_question07()

# 方法八：
def three_question08():
    li=[11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    li3=[]
    index=0
    while index < len(li):
        if li[index] not in li3:
            li3.append(li[index])
        index += 1
        if index >= len(li):
            break

    print('不重复元素个数',len(li3))

# three_question08()

# 方法九：
def three_question09():
    li=[11, 22, 33, 22, 22, 44, 55, 77, 88, 99, 11]
    formatList = list(set(li))
    formatList.sort(key=li.index)

    print('不重复元素个数',len(formatList))

three_question09()

或者：
1.使用循环进行遍历，将重复的元素去掉。

def test1():
    lst = [1,2,5,6,3,5,7,3]
    tmp = []
    for it in lst:
        if it not in tmp:
            tmp.append(it)
    print(tmp)

结果：

[1, 2, 5, 6, 3, 7]

2.使用集合的唯一性，对列表进行去重。

def test2():
    lst = [1,2,5,6,3,5,7,3]
    tmp = list(set(lst))
    print(tmp)  # 顺序改变
    tmp.sort(key=lst.index)
    print(tmp)  # 顺序不变

结果：

[1, 2, 3, 5, 6, 7]
[1, 2, 5, 6, 3, 7]

随机打乱：

Random中有一个random.shuffle()方法提供了完美的解决方案。代码如下：

x = [1,2,3,4,5,6]
random.shuffle(x)
print(x)

输出结果：

第一次输出内容：[6, 5, 1, 3, 2, 4]
第二次输出内容：[6, 1, 3, 5, 2, 4]
第三次输出内容：[5, 3, 1, 2, 4, 6]

lower_bound:

lower_bound(nums, target)
在非递减数组nums中，lower_bound(nums, target)返回第一个大于等于target的值得位置，如果nums中元素均小于target（即不存在>=target的元素），则返回nums的长度（即target如果要插入到nums中，应该插入的位置）

#coding=utf-8
#返回nums中第一个>=target的值得位置，如果nums中都比target小，则返回len(nums)
def lower_bound(nums, target):
    low, high = 0, len(nums)-1
    pos = len(nums)
    while low<high:
        mid = (low+high)/2
        if nums[mid] < target:
            low = mid+1
        else:#>=
            high = mid
            #pos = high
    if nums[low]>=target:
        pos = low
    return pos

测试：

nums = [10, 10, 10, 20, 20, 20, 30, 30]   
print lower_bound(nums, 9),
print lower_bound(nums, 10),
print lower_bound(nums, 15),
print lower_bound(nums, 20),
print lower_bound(nums, 25),
print lower_bound(nums, 30),
print lower_bound(nums, 40)

运行结果：

0 0 3 3 6 6 8

upper_bound:

upper_bound(nums, target)
在非递减数组nums中，upper_bound(nums, target)返回第一个大于target的值的位置，如果nums中元素均小于等于target（即不存在>target的元素），则返回nums的长度（即target如果要插入到nums中，应该插入的位置）

#返回nums中第一个>target的值得位置，如果nums中都不比target大，则返回len(nums)
def upper_bound(nums, target):
    low, high = 0, len(nums)-1
    pos = len(nums)
    while low<high:
        mid=(low+high)/2
        if nums[mid]<=target:
            low = mid+1
        else:#>
            high = mid
            pos = high
    if nums[low]>target:
        pos = low
    return pos

测试：

nums = [10, 10, 10, 20, 20, 20, 30, 30] 
print upper_bound(nums, 9),
print upper_bound(nums, 10),
print upper_bound(nums, 15),
print upper_bound(nums, 20),
print upper_bound(nums, 25),
print upper_bound(nums, 30),
print upper_bound(nums, 40)

运行结果：

0 3 3 6 6 8 8