"""
68, 34, 12, 95, 73, 80, 57
34, 12, 68, 73, 80, 57, 95
12, 34, 68, 73, 57, 80
12, 34, 68, 57, 73
12, 34, 57, 68
12, 34, 57
12, 34
"""

def bubble_sort(unsorted_items, *, comp=lambda x, y: x > y):
    """冒泡排序"""
    items = unsorted_items[:]
    items_len = len(items)
    for i in range(items_len - 1):
        swapped = False
        for j in range(items_len - 1 - i):
            if comp(items[j], items[j + 1]):
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if swapped:
            swapped = False
            for j in range(items_len - 2 - i, 0, -1):
                if comp(items[j - 1], items[j]):
                    items[j], items[j - 1] = items[j - 1], items[j]
                    swapped = True
        if not swapped:
            break
    return items


# class Student():
#
#     def __init__(self, name, age):
#         self.name = name
#         self.age = age
#
#     def __repr__(self):
#         return f'{self.name}: {self.age}'
#
#     def __gt__(self, other):
#         return self.age > other.age
# 使用namedtuple可以更简洁的生成类
Student = namedtuple('Student', ('name', 'age'))


def main():
    """主函数"""
    items = [
        Student('Luo Hao', 38), Student('Wang Dachui', 19),
        Student('Lee Xiaolong', 25), Student('Zhang Sanfeng', 120)
    ]
    print(bubble_sort(unsorted_items=items,
                      comp=lambda x, y: x.age > y.age))
    items2 = ['pitaya', 'pear', 'apple', 'watermelon', 'waxberry']
    print(bubble_sort(items2, comp=lambda x, y: len(x) > len(y)))


if __name__ == '__main__':
    main()

"""
68, 34, 12, 95, 73, 80, 57
[69, 34, 12], [95, 73, 80, 57]
[69], [34, 12], [95, 73], [80, 57]
[69], [34], [12], [95], [73], [80], [57]
----------------------------------------
[34, 69], [12, 95], [73, 80], [57]
[12, 34, 69, 95], [57, 73, 80]
[12, 34, 57, 69, 73, 80, 95]
"""
# 分治法 - 将规模较大的问题划分为规模较小的子问题 用子问题解合并出原问题的解
# divide-and-conquer
def merge_sort(unsorted_items, *, comp=lambda x, y: x < y):
    if len(unsorted_items) <= 1:
        return unsorted_items[:]
    mid = len(unsorted_items) // 2
    left = merge_sort(unsorted_items[:mid], comp=comp)
    right = merge_sort(unsorted_items[mid:], comp=comp)
    return merge(left, right, comp=comp)


def merge(list1, list2, *, comp=lambda x, y: x < y):
    """将两个有序列表合并 合并之后仍然有序"""
    list3 = []
    index1, index2 = 0, 0
    while index1 < len(list1) and index2 < len(list2):
        if comp(list1[index1], list2[index2]):
            list3.append(list1[index1])
            index1 += 1
        else:
            list3.append(list2[index2])
            index2 += 1
    list3 += list1[index1:]
    list3 += list2[index2:]
    return list3
    
    def main():
    """主函数"""
    items3 = [68, 34, 12, 95, 73, 80, 57]
    print(merge_sort(items3))


if __name__ == '__main__':
    main()

# 爬楼梯 一次可以爬1个、2个、3个台阶
# 爬完10个台阶一共有多少种走法
def walk(num, result={}):
    if num == 0:
        return 1
    elif num < 0:
        return 0
    try:
        return result[num]
    except KeyError:
        result[num] = walk(num - 1) + walk(num - 2) + walk(num - 3)
        return result[num]
        
def main():
    for num in range(1, 11):
        print(f'{num}: {walk(num)}')
        
        
if __name__ == '__main__':
    main()

def factorial(num):
    if num in (0, 1):
        return 1
    return num * factorial(num - 1)

# 1 1 2 3 5 8 13 21 34 55 ...
# 动态规划 - 求解的问题有局部最优解或者最优子结构
def fib2(num, result={}):
    if num in (1, 2):
        return 1
    try:
        return result[num]
    except KeyError:
        result[num] = fib2(num - 1) + fib2(num - 2)
        return result[num]

select * from tb_student;
select * from tb_course;

select * from tb_student, tb_course;

select sname 姓名, ssex 性别 from tb_student;

select sname as 姓名, case ssex when 1 then '男' else '女' end as 性别 from tb_student;

select sname as 姓名, if(ssex, '男', '女') as 性别 from tb_student;

select sname, sbirth from tb_student where ssex=0;

select courseid, cname from tb_course where ccredit>2;

select sname, ssex, sbirth from tb_student 

where sbirth>='1980-1-1' and sbirth<='1989-12-31';

select sname, ssex, sbirth from tb_student 

where sbirth between '1980-1-1' and '1989-12-31';

select * from tb_student where sname='杨过';

select * from tb_student where sname like '杨%';

select * from tb_student where sname like '杨_';

select * from tb_student where sname like '杨__';

select * from tb_student where sname like '%杨%';

select stuid, sname, ssex from tb_student where sname regexp '^[张李].+';

select * from tb_student where sbirth is null or saddr is null;

select saddr from tb_student;

select saddr from tb_student where saddr is not null;

select distinct saddr from tb_student where saddr is not null;

select * from tb_student order by ssex;

select * from tb_student order by ssex desc;

select * from tb_student order by ssex asc, sbirth desc;

select sname, sbirth from tb_student where ssex=1 order by sbirth;

select sname, sbirth, saddr from tb_student where saddr is not null and ssex=1 order by sbirth desc;

select min(sbirth) from tb_student;
select max(sbirth) from tb_student;

select cid, avg(score) from tb_sc where cid=1111;

select sid, avg(score) from tb_sc 
where sid=1001;

select cid, avg(score) from tb_sc group by cid;

select cid, avg(score) as avgScore from tb_sc group by cid having avgScore<80;

select count(stuid) from tb_student;

select count(stuid) from tb_student where ssex=1;

select if(ssex, '男', '女')as 性别, count(*)as 人数 from tb_student group by ssex;

select if(ssex, '男', '女') as 性别, count(*) as 人数 
from tb_student group by ssex order by null;

select if(ssex, '男', '女')as 性别, count(*)as 人数 from tb_student where saddr is not null group by ssex order by ssex desc;

select sid, avg(score) from tb_sc 
group by sid having avg(score)<60;

select sname, sbirth from tb_student
where sbirth=(select min(sbirth) from tb_student);

select sname from tb_student 
where stuid in (
select sid from tb_sc
group by sid having count(sid)>2)；

select sname from tb_student 
where stuid in (
select sid from tb_sc
group by sid having count(sid)>2) and ssex=1;

select sname, cname, score 
from tb_sc, tb_student, tb_course
where sid=stuid and cid=courseid;

select sname, avgScore from tb_student,
(select sid, avg(score) as avgScore from tb_sc 
group by sid) t
where stuid=sid;

select sna me, avgScore from tb_student t1,
(select sid, avg(score) as avgScore from tb_sc 
group by sid) t2
where stuid=sid;

select sname, sidCount from tb_student,
(select sid, count(sid) as sidCount from tb_sc group by sid) t
where stuid=sid;

select sname, avgScore from tb_student t1
inner join
(select sid, avg(score) as avgScore from tb_sc 
group by sid) t2
on stuid=sid;

select sname, ifnull(total, 0) as total from tb_student t1
left outer join
(select sid, count(sid) as total from tb_sc 
group by sid) t2 
on stuid=sid;

select sname, total from 
(select sid, count(sid) as total from tb_sc
group by sid)t2 left outer join tb_student t1
on stuid=sid;

select sname, ifnull(total, 0) as total from
(select sid, count(sid) as total from tb_sc 
group by sid) t2 right outer join tb_student t1
on stuid=sid;

select sid, sname, cname, score from 
tb_sc inner join tb_student on stuid=sid
inner join tb_course on cid=courseid
limit 5;

grant all on student.tb_student to xiaoming;

grant all on *.* to xiaoming;