一、排序的介绍

1. 排序是将多个数据，按照指定的顺序进行排列的过程
2. 排序的分类：
   1. 冒泡排序
   2. 选择排序
   3. 插入排序
   4. 希尔排序
   5. 归并排序
   6. 快速排序
   7. 堆排序
   8. 计数排序
   9. 桶排序
   10. 基数排序

二、冒泡排序法

1. 介绍：
   1. ​​​​​​​冒泡排序（Bubble Sorting）的基本思想是：重复地走访需要排序地元素列表，依次比较两个相邻的元素，如果顺序（如从大到小或从小到大）错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换，则元素列表排序完成
   2. 在冒泡排序中，值最大（或最小）的元素会通过交换慢慢“浮”到元素列表的“顶端”。就像冒泡一样，所以被称为冒泡排序
2. 冒泡排序法案例：

   列表：[24,69,80,57,13]有5个元素，使用冒泡排序法将其排成一个从小到大的有序列表
   
   第一轮排序：把最大的数字放到最后
   第1次比较：[24,69,80,57,13]
   第2次比较：[24,69,80,57,13]
   第3次比较：[24,69,57,80,13]
   第4次比较：[24,69,57,13,80]
   
   第二轮排序：把第二大的数字放到倒数第二的位置
   第1次比较：[24,69,57,13,80]
   第2次比较：[24,57,69,13,80]
   第3次比较：[24,57,13,69,80]
   
   第三轮排序：把第三大的数字放到倒数第三的位置
   第1次比较：[24,57,13,69,80]
   第2次比较：[24,13,57,69,80]
   
   第四轮排序：把第四大的数字放到倒数第四的位置
   第1次比较：[13,24,57,69,80]

3. 代码演示：

   # 如果只是完成排序功能，我们可以直接使用list的方法sort
   num_list = [24,69,80,57,13]
   print("排序前".center(32,"-"))
   print(f"num_list：{num_list}")
   
   # 使用sort方法完成排序
   num_list.sort()
   
   print("排序后".center(32,"-"))
   print(f"num_list：{num_list}")

   my_list = [24,69,80,57,13]
   """
   第一轮排序：把最大的数字放到最后
   第1次比较：[24,69,80,57,13]
   第2次比较：[24,69,80,57,13]
   第3次比较：[24,69,57,80,13]
   第4次比较：[24,69,57,13,80]
   """
   # j变量控制比较的次数，同时可以作为比较元素的索引下标
   for j in range(0,4):
       # 如果前面的元素 > 后面的元素，就交换
       if my_list[j] > my_list[j+1]:
           my_list[j],my_list[j+1] = my_list[j+1],my_list[j]
   print(my_list)
   
   """
   第二轮排序：把第二大的数字放到倒数第二的位置
   第1次比较：[24,69,57,13,80]
   第2次比较：[24,57,69,13,80]
   第3次比较：[24,57,13,69,80]
   """
   for j in range(0,3):
       # 如果前面的元素 > 后面的元素，就交换
       if my_list[j] > my_list[j+1]:
           my_list[j],my_list[j+1] = my_list[j+1],my_list[j]
   print(my_list)
   
   """
   第三轮排序：把第三大的数字放到倒数第三的位置
   第1次比较：[24,57,13,69,80]
   第2次比较：[24,13,57,69,80]
   """
   for j in range(0,2):
       # 如果前面的元素 > 后面的元素，就交换
       if my_list[j] > my_list[j+1]:
           my_list[j],my_list[j+1] = my_list[j+1],my_list[j]
   print(my_list)
   
   """
   第四轮排序：把第四大的数字放到倒数第四的位置
   第1次比较：[13,24,57,69,80]
   """
   for j in range(0,1):
       # 如果前面的元素 > 后面的元素，就交换
       if my_list[j] > my_list[j+1]:
           my_list[j],my_list[j+1] = my_list[j+1],my_list[j]
   print(my_list)
   
   # for i in range(0,4):
   #     for j in range(0,4-i):
   #         if my_list[j] > my_list[j + 1]:
   #             my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]
   # print(my_list)

三、查找

（1）基本介绍

在Python中，我们应当掌握两种常见的查找方法：

1. 顺序查找
2. 二分查找
3. 插值查找
4. 斐波那契查找
5. 树表查找
6. 分块查找
7. 哈希查找

（2）顺序查找

顺序查找案例：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王，猜名字游戏：从键盘中任意输入一个名称，判断列表中是否包含此名称【顺序查找】。要求：如果找到了，就提示找到，并给出下标值

name_list = ["白眉鹰王","金毛狮王","紫衫龙王","青翼蝠王"]
find_name = "金毛狮王"

# 使用list.index完成查找
find_index = name_list.index(find_name)

# 编写顺序查找函数seq_search
def seq_search(my_list,find_val):
    """
    功能：顺序查找指定的元素
    :param my_list: 传入的列表（即要查找的列表）
    :param find_val:要查找的值/元素
    :return:如果查找到则返回对应的索引下标，否则返回-1
    """
    """
        思路分析
        1.对列表进行遍历，如果找到了，则返回对应的下标
        2.如果遍历结束，没有找到，则返回-1
    """
    find_index = -1
    # 遍历
    for i in range(len(my_list)):
        if my_list[i] == find_val:
            print(f"恭喜，找到对应的值{find_val} 下标是{i}")
            find_index = i
            break
    else:
        print(f"没有找到对应的值 {find_val}")

    return find_index

res_index = seq_search(name_list,find_name)
print("res_index：",res_index)

（3）二分查找

1. 二分查找案例：请对一个列表（元素是从小到大排序的）进行二分查找[1,8,10,89,1000,1234]，输入一个数字看看该列表是否存在这个数，并且求出下标，如果没有就返回-1

   num_list = [1, 8, 10, 89, 1000, 1234]
   
   def binary_search(my_list, find_val):
       """
       功能：完成二分查找
       :param my_list:要查找的列表（该列表是由大小顺序）
       :param find_val:要查找的元素/值
       :return:如果找到返回对应的下标，如果没有找到，返回-1
       """
       # left_index：表示左边的索引
       # right_index：表示右边的索引
       left_index,right_index = 0, len(my_list)-1
       # 定义找到数的下标
       find_index = -1
       # 使用while循环，不断地折半比较
       while left_index <= right_index:
           # 中间数的下标/索引
           middle_index = (left_index + right_index) // 2
           if my_list[middle_index] > find_val:
               right_index = middle_index - 1
           elif my_list[middle_index] < find_val:
               left_index = middle_index + 1
           else:
               find_index = middle_index
               break   # 找到一个就退出while
       return find_index
   
   res_index = binary_search(num_list, 1)
   if res_index == -1:
       print("没有找到该数")
   else:
       print(f"找到数，对应的下标{res_index}")

2. 二分查找的注意事项和细节：
   1. ​​​​​​​二分查找的前提是该列表已经是一个排好序的列表（从小到大或者从大到小）
   2. 排列的顺序是从小到大还是从大到小，会影响二分查找的代码逻辑
3. 二分查找的思路分析：
   1. 前提是这个列表是一个排好序的列表（为了分析方便，就以从小到大的列表为例分析）
   2. 找到列表的中间数 mid_val 和 find_val 比较
   3. 如果 mid_val > find_val，则到 mid_val 的左边查找
   4. 如果 mid_val < find_val，则到 mid_val 的右边查找
   5. 如果 mid_val = find_val，则找到，返回对应的下标即可
   6. 不断地重复上述步骤，这里就是不断地折半，使用 while
   7. 如果 while 结束，都没有找到，说明 find_val 没有在列表

四、本章作业

1. 随机生成10个整数（1-100的范围）保存到列表，使用冒泡排序，对其进行从大到小排序

   # 随机生成10个整数（1-100的范围）保存到列表
   # random.randint(a,b)：返回随机整数N满足 a<=N<=b
   import random
   
   lst_num = []
   for i in range(10):
       lst_num.append(random.randint(1, 100))
   
   # 使用冒泡排序，对其进行从大到小排序
   def bubble_sort(my_list):
       for i in range(1,len(lst_num)-1):
           for j in range(0,len(lst_num)-1):
               if lst_num[j] < lst_num[j+1]:
                   lst_num[j], lst_num[j+1] = lst_num[j+1], lst_num[j]
   
   bubble_sort(lst_num)
   print(lst_num)

2. 在第一题的基础上，使用二分查找，查找是否有8这个数，如果有，就返回对应的下标。如果没有，就返回-1

   # 使用二分查找，查找是否有8这个数，如果有，就返回对应的下标。如果没有，就返回-1
   def binary_search(my_list,find_val):
       find_index = -1
       left_index,right_index=0,len(my_list)-1
       while left_index <= right_index:
           middle_index = (left_index + right_index) // 2
           if my_list[middle_index] > find_val:
               left_index = middle_index + 1
           elif my_list[middle_index] < find_val:
               right_index = middle_index - 1
           else:
               find_index = middle_index
               break
       return  find_index
   
   res_index = binary_search(lst_num, 8)
   if res_index == -1:
       print("Not Found")
   else:
       print(f"找到数，对应的下标{res_index}")