Python算法编程：冒泡排序、选择排序、快速排序
最近在做一些算法方面的练习题，总结出来与大家分享一下。有不组织之处，多多指教！
冒泡排序
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换连个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样， 慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”。
示例代码如下：
nums_lst = [6, 1, 7, 9, 10, 3, 5, 4, 2, 1, 0, 7, -1, 12]
for _ in range(len(nums_lst)):
for i in range(len(nums_lst) -1, 0, -1):
if nums_lst[i] < nums_lst[i-1]:
nums_lst[i], nums_lst[i-1] = nums_lst[i-1], nums_lst[i]
print(nums_lst)
运行结果如下：
D:\Python39\python.exe D:/My_Project/算法/bubble_sort.py
[-1, 0, 1, 1, 2, 3, 4, 5, 6, 7, 7, 9, 10, 12]
Process finished with exit code 0
选择排序
选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。在序列中寻找最小值时使用的是线性查找。
数据没有重复的情况下
nums_lst = [6, 1, 7, 9, -11, 10, 0, 3, 4, 2, 5, 12, -1]
for i in range(len(nums_lst)):
min_n = min(nums_lst[i:]) # 取列表中最小值
if nums_lst[i] > min_n:
nums_lst[nums_lst.index(min_n)], nums_lst[i] = nums_lst[i], min_n
print(nums_lst)
运行结果如下：
D:\Python39\python.exe D:/My_Project/算法/selection_sort.py
[-11, -1, 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 12]
Process finished with exit code 0
存在重复数据的情况下
nums_lst_origin = [6, 1, 7, 9, -11, 10, 0, 3, 4, 2, 5, 12, -1, 7, 3, 9, 0]
nums_lst = list(set(nums_lst_origin))
for i in range(len(nums_lst)):
min_n = min(nums_lst[i:])
if nums_lst[i] > min_n:
nums_lst[nums_lst.index(min_n)], nums_lst[i] = nums_lst[i], min_n
print(nums_lst_origin)
insert_data = {
}
for _ in nums_lst:
if nums_lst_origin.count(_) > 1:
insert_data[_] = nums_lst_origin.count(_)
for k, v in insert_data.items():
for _ in range(v-1):
nums_lst.insert(nums_lst.index(k), k)
print(nums_lst)
运行结果如下：
D:\Python39\python.exe D:/My_Project/算法/selection_sort.py
[6, 1, 7, 9, -11, 10, 0, 3, 4, 2, 5, 12, -1, 7, 3, 9, 0]
[-11, -1, 0, 0, 1, 2, 3, 3, 4, 5, 6, 7, 7, 9, 9, 10, 12]
Process finished with exit code 0
快速排序
在列表中取一个位置中间的数字，列表中位于中间位置数字的两侧数据与中间的数字比较，左侧大于中间数字，右侧小于中间数字互相交换
示例代码如下：
nums_lst = [4, 1, 5, 3, 2, -1, 8, 1, 11, 7]
def quick_sort(data):
def sort(s_data, fst, lst):
if fst > lst:
return
i, j = fst, lst
x = s_data[(fst + lst) // 2]
while i <= j:
while s_data[i] < x:
i += 1
while s_data[j] > x:
j -= 1
if i <= j:
s_data[i], s_data[j] = s_data[j], s_data[i]
i, j = i + 1, j -1
sort(s_data, fst, j)
sort(s_data, i, lst)
return s_data
return sort(list(data), 0, len(data) - 1)
sort_nums = quick_sort(nums_lst)
print(sort_nums)
运行结果如下:
D:\Python39\python.exe D:/My_Project/算法/quick_sort.py
[-1, 1, 1, 2, 3, 4, 5, 7, 8, 11]
Process finished with exit code 0
