列表排序
● 排序：将一组“无序”的记录序列调整为“有序”的记录序列。
● 列表有序：将无序列表变为有序列表
? ? ? ?? 输入：列表
? ? ? ? ?输出：有序列表
● 升序与降序
● 内置怕排序函数：sort()?
常见排序算法
| 排序Low B三人组 | 排序NB三人组 | 其他排序 |
| 冒泡排序 | 快速排序 | 希尔排序 |
| 选择排序 | 堆排序 | 计数排序 |
| 插入排序 | 归并排序 | 基数排序 |
（1）冒泡排序(Bubble Sort）
● 列表每两个相邻的数，如果前面比后面大，则交换这两个数。
● 一趟排序完成后，则无序区减少一个数，有序区增加一个数。
利用i来表示总共要走多少趟，i-1趟
j表示指针，控制是否要做交换，如果li[j] < li[j+1]，则交换；否则不交换；j++
# 冒泡排序要排序n个数(假设为升序排列)， 由于每遍历一趟只排好一个数字 即把最大数排到最后 # 则需要遍历n-1趟，所以最外层循环是要循环n-1次 # 每完成一趟遍历后,下趟需要比较的数字就会减少一个 # 所以第i趟需要比较的次数为len(list)-i-1，所以第二层循环要遍历是n-1-i次
import random
# 复杂度为：O(n^2)
def bubble_sort_simple(li):
"""暴力冒泡排序"""
# 外层循环控制总共需要遍历的次数,需要len(li)-1次
for i in range(len(li)-1): # i表示趟数
# 内层循环控制每一趟需要比较的次数,对于已经排好的数字(大数字)就不需要再比较了,
# 则需要比较len(list)-1-i次
for j in range(len(li)-i-1): # 排好的就不用遍历了
# 如果第j个数大于第j+1个数 则互换位置,在Python中,for循环中的变量会自动+1
if li[j] > li[j+1]:
# 满足条件,即交互位置
li[j], li[j+1] = li[j+1], li[j]
return li
li = [random.randint(0,10) for i in range(10)]
print(bubble_sort_simple(li))改进后的冒泡排序：
def bubble_sort(li):
"""改进后的冒泡排序"""
for i in range(len(li)-1):
# 创建一个标志位，用来记录本轮冒泡，是否有数据交换位置
status = False
for j in range(len(li)-i-1):
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
# 只要由数据交换位置，则修改statusd的值
status = True
# 每一轮冒泡结束之后，判断当前status是否为Flase,
# 如果为Flase，则说明上一轮冒泡没有修改任何数据的顺序（即数据是有序的）
if not status:
return li
return li
li = [random.randint(0,10) for i in range(10)]
print(bubble_sort(li))（2）选择排序（Select Sort）
一趟排序记录最小的数，放到第一个位置
再一趟排序记录列表无序区最小的数，放到第二个位置
......
算法关键点：有序区和无序区、无序区最小数的位置
选择排序的主要思想是：先从整个序列中选择最小的数据放到第一位，再从剩余的序列中选择最小的数据放在第二位，如此循环，直到最后一位。
代码参考：https://blog.csdn.net/zhicheng_xu/article/details/93747537
# 时间复杂度：O(n^2)
def select_sort_simple(li):
"""暴力选择排序"""
result = []
for i in range(len(li)):
min_val = min(li) # O(n)
result.append(min_val) # O(1)
li.remove(min_val) # O(n)
return result
# 时间复杂度：O(n^2)
def select_sort(li):
"""改进后的选择排序"""
for i in range(len(li) - 1):
min_index = i
for j in range(i+1, len(li)):
if li[j] < li[min_index]:
min_index = j
if i != min_index:
li[min_index], li[i] = li[i], li[min_index]
return li
if __name__ == '__main__':
li = [2,3,6,1,0,5,8]
select_sort_simple(li)
select_sort(li)（3） 插入排序
基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表.
每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。
模拟抓牌的过程：
● 初始时手里（有序区）只有一张牌
● 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置?
"""
======================
-*- coding: utf-8 -*-
@author: Qiufen.Chen
@time: 2021/7/22:23:31
@email: 1760812842@qq.com
@File: insert_sort.py
@Project: data_structure
======================
"""
# 时间复杂度：O(n^2)
def insert_sort(li):
for i in range(1, len(li)): # i表示摸到的牌的下标
tmp = li[i]
j = i-1 # j指的是手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+1] = li[j] # 右移
j -= 1
li[j+1] = tmp
print(li)
return li
if __name__ == "__main__":
li = [2, 3, 6, 1, 0, 5, 8]
insert_sort(li)
?未完待续。。。。。。。。。