常见排序算法

• 冒泡排序：通过反复比较相邻元素，若前者大于后者则交换位置，每轮将最大值沉到尾部，时间复杂度为 O (n^2)。
• 选择排序：用每个元素与其后的元素比较，若前者大于后者则交换，每轮将最小值放到头部，时间复杂度为 O (n^2)。
• 插入排序：将待排序数据插入到已排序区间内，时间复杂度为 O (n) 到 O (n^2) 之间。
• 此外，还有快速排序、归并排序、堆排序、桶排序等排序算法，文中未详细介绍其原理和复杂度。

冒泡排序示例

ls = [7, 8, 11, 5, 8, 999, 556, 44]
n = len(ls)
for x in range(1, n):
    for j in range(n - x):
        if ls[j] > ls[j + 1]:
            ls[j], ls[j + 1] = ls[j + 1], ls[j]
print(ls)

选择排序示例

ls = [7, 8, 11, 5, 8, 999, 556, 44]
n = len(ls)
for i in range(n):
    min_index = i
    for j in range(i + 1, n):
        if ls[j] < ls[min_index]:
            min_index = j
    ls[i], ls[min_index] = ls[min_index], ls[i]
print(ls)

插入排序示例

ls = [9, 5, 7, 4, 8, 6, 1, 1, 2, 5, 7, 98, 56, 77, 4564, 56]
for i in range(1, len(ls)):
    n = ls[i]
    pos = 0
    for j in range(i - 1, -1, -1):
        if n > ls[j]:
            pos = j + 1
            break
    for x in range(i - 1, pos - 1, -1):
        ls[x + 1] = ls[x]
    ls[pos] = n
print(ls)

Python 列表 sort 排序方法

• ls.sort(reverse=False, key=None)：无返回值，直接对原列表排序。
  • 默认按数据自然顺序排序，数字从小到大，字符串按字符大小排序。
  • reverse = True可反转排序规则，实现降序排序。
  • key为自定义排序规则函数，该函数接收列表元素并返回权重值，权重值小的元素靠前。

sort 方法示例

ls = [1, 2, 48, 9, 8, 96, 4, 2]
ls.sort(reverse=True)
print(ls)

ls2 = ['a', 'b', 'c', '123', 'abc', 'xyz', 'ttt']
ls2.sort()
print(ls2)

ls3 = ['a556', 'ab', 'c', 'xyz', 'cde']
ls3.sort(key=lambda d: len(d), reverse=True)
print(ls3)

Python 获取随机数

• import random后可使用相关函数获取随机数。
• random.random()：返回 [0, 1) 的随机小数。
• 生成 [m, n) 间随机整数：int(random.random() * (n - m) + m)或random.randrange(m, n)。
• 生成 [m, n] 间随机整数：random.randint(m, n)。

随机数示例

import random
ls = [46874, 87, 456, 123, 4, 2, 5, 7, 2, 85, 7, 52, 6, 4, 5, 7]
ls.sort(key=lambda d: random.random())
print(ls)

i = random.randint(0, 2)
print(i)

二维列表

• 定义：元素也是列表的列表。
• 访问元素：如ls = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]，可通过ls[0][1]访问元素 2。
• 输出二维列表示例

ls = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
for i in ls:
    for v in i:
        print(v, end='\t')
    print()

• 二维列表行列转换示例

ls = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
new_ls = [[0 for _ in range(4)] for _ in range(3)]
for y in range(len(ls)):
    arr = ls[y]
    for x in range(len(arr)):
        new_ls[x][y] = arr[x]
for arr in new_ls:
    for v in arr:
        print(v, end='\t')
    print()

 

1. 选择排序（Selection Sort）

ls = [7,5,9,6,3,4,2,6,8]
# 遍历列表，每次选择最小元素放到已排序部分末尾
for i in range(len(ls)-1):
    for j in range(i,len(ls)):
        if ls[i] > ls[j]:
            ls[i],ls[j] = ls[j],ls[i]
print(ls)  # 输出：[2, 3, 4, 5, 6, 6, 7, 8, 9]

2. 冒泡排序（Bubble Sort）

ls = [7,5,9,6,3,4,2,6,8]
n = len(ls)
# 重复遍历列表，比较相邻元素并交换位置，将最大元素"冒泡"到末尾
for i in range(n-1):
    for j in range(n-i-1):
        if ls[j] > ls[j+1]:
            ls[j],ls[j+1] = ls[j+1],ls[j]
print(ls)  # 输出：[2, 3, 4, 5, 6, 6, 7, 8, 9]

3. 随机打乱列表（Fisher-Yates Shuffle）

import random
list01 = list(range(10))
# 使用随机数作为排序键，实现列表随机打乱
list01.sort(key=lambda x:random.random())
print(list01)  # 输出随机打乱的列表

4. 猴子排序（Bogo Sort）

import random
list01 = [1,5,4,3,78,9,6]
# 不断随机打乱列表，直到列表有序（效率极低，仅作演示）
while True:
    list01.sort(key=lambda x:random.random())
    for i in range(0,len(list01)-1):
        if list01[i] > list01[i+1]:
            break
    else:
        break
print(list01)  # 输出有序列表：[1, 3, 4, 5, 6, 9, 78]

5. 判断列表是否有序

list01 = [1,2,3,4,5,6,89,9]
# 方法一：使用循环逐个比较元素
for i in range(0,len(list01)-1):
    if list01[i] > list01[i+1]:
        print('不是已经排序好的')
        break
else:
    print('是排序好的')

# 方法二：使用列表推导式生成相邻元素比较结果
ret = [list01[i] > list01[i+1] for i in range(len(list01)-1)]
print(ret)  # 输出：[False, False, False, False, False, False, True]

6. 生成不重复的随机数列表

import random
ls = []
# 生成10个0-9之间的不重复随机数
while len(ls) < 10:
    a = random.randrange(0, 10)
    if a not in ls:
        ls.append(a)
print(ls)  # 输出：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]（顺序随机）

7. 插入排序（Insertion Sort）

ls = [9,8,6,1,4,6,45,67,1,574,54,6,5]
n = len(ls)
# 将未排序数据插入到已排序部分的正确位置
for i in range(1,n):
    pos = 0
    x = ls[i]
    # 查找插入位置
    for j in range(i-1,-1,-1):
        if x > ls[j]:
            pos = j + 1
            break
    # 移动元素腾出插入位置
    for o in range(i-1,pos-1,-1):
        ls[o+1] = ls[o]
    ls[pos] = x
print(ls)  # 输出：[1, 1, 4, 5, 6, 6, 6, 8, 9, 45, 54, 67, 574]

8. 扑克牌发牌程序

import random

# 初始化牌面和花色
card_num = list(range(2, 11)) + ['J', 'Q', 'K', 'A']
card_color = ['♠', '♥', '♦', '♣']
card_sum = ['☺', '☻']  # 大小王

# 生成完整扑克牌
for i in range(len(card_num)):
    for j in range(len(card_color)):
        card_sum.append(str(card_num[i]) + card_color[j])

# 洗牌并分牌
card_sum.sort(key=lambda a: random.random())
card_1 = card_sum[0:49:3]  # 玩家1的牌（每3张取1张）
card_2 = card_sum[1:50:3]  # 玩家2的牌
card_3 = card_sum[2:51:3]  # 玩家3的牌
card_d = card_sum[51:]     # 底牌

print(f'第一个人的卡牌是{card_1}')
print(f'第二个人的卡牌是{card_2}')
print(f'第三个人的卡牌是{card_3}')
print(f'底牌是{card_d}')

9. 卡号验证算法（类似 IMEI 校验）

card_i = list('0123456789ABCDEFGHJKLMNPQRTUWXY')
W_i = [1,3,9,27,19,26,16,17,20,29,25,13,8,24,10,30,28]
a = 0

# 输入18位卡号并验证
card_num = input('输入十八位卡号:')
card_list = list(card_num)

# 计算校验值
for i in range(17):
    card_list[i] = card_i.index(card_list[i])
for i in range(17):
    a = a + int(card_list[i]) * int(W_i[i])
a = a % 31
a = card_i[(31 - a)]

# 验证校验位
if a == card_list[-1]:
    print('正确的卡号！')
else:
    print('错误的卡号！')

10. 杨辉三角（Pascal's Triangle）生成

n = int(input('请输入杨辉三角的行数： '))
ls = []

# 生成杨辉三角
for i in range(n):
    row = [1] * (i + 1)
    for j in range(1,i):
        row[j] = ls[i-1][j-1] + ls[i-1][j]
    ls.append(row)

# 输出杨辉三角
for row in ls:
    for j in row:
        print(j,end='\t')
    print()