【排序】笔记

封装函数

sort

stable_sort

排序目的

数值排序 2 3 21 33

字典排序 2 21 3 33

非比较排序

1.计数排序

负数与小数问题：加到整数（负数）或乘一定的值（小数）

去重问题：转set后再转list

s2=list(set(s))

2.基数排序

排序类型

冒泡排序

时间复杂度 o（n^2）

思想：通过相邻比较交换把最重/轻的放置其对应的位置

变体：还是一个暴力的思想，相邻交换，首先确定一个值，然后把后面的慢慢全部都确定下来。

排序后的操作

首尾比较

对合值有限定

相邻比较

对差值有限定

特殊操作

双属性

少量可以直接用pair（在python中的话就是用dict）来做,但是排序的方式还是得自己写。

习题

import math

n, r = map(int, input().split())
# 用dict来做本题
p = {}
for i in range(n):
    number, score = map(int, input().split())
    p[number] = score
# 第一关键词为value, 第二关键词为key
rp = sorted(p.items(), key=lambda item: (-item[1], item[0]))
m = int(r * 1.5)
r = m
while rp[r][1] == rp[m-1][1]:
    r = r + 1
m = r
print(rp[m-1][1], m)
for i in range(m):
    print( rp[i][0], rp[i][1])

多属性

c里面可以用结构体，对于python的话就用类

python

class Stu:
    no = 0
    chi = 0
    sum = 0

    def __init__(self, a, b, c, i):
        self.no = i
        self.chi = a
        self.sum = a + b + c


n = int(input())
stus = []
for i in range(n):
    a, b, c = map(int, input().split())
    stu = Stu(a, b, c, i + 1)
    stus.append(stu)
// 第一关键词总分（倒序），第二关键词语文（倒序），第三关键词学号（升序）
ls = sorted(stus, key=lambda x: (-x.sum, -x.chi, x.no))
for item in ls:
    print(item.no, item.sum, sep=" ")
    if item == ls[4]:
        break