def bubble_sort(list):
for i in range(0, len(list)):
is_sorted = True
for j in range(0, len(list) - i - 1):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
is_sorted = False
if is_sorted:
return
list1 = [97, 3, 6, 1, 8, 5, -20, 100, 50, 200, -32, 123]
bubble_sort(list1)
print(list1)
执行结果如下图:
def choose_sort(list):
list_len = len(list)
for i in range(0, list_len):
for j in range(i + 1, list_len):
if list[i] > list[j]:
list[i], list[j] = list[j], list[i]
list1 = [3, 6, 1, 8, 5, -20, 100, 50, 200]
choose_sort(list1)
print(list1)
执行结果如下图:
# -*- encoding: utf-8 -*-
import random
# O(n^2)
def selection_sort(lyst):
"""选择排序"""
i = 0
while i < len(lyst) - 1:
min_index = i
j = i + 1
while j < len(lyst):
if lyst[j] < lyst[min_index]:
min_index = j
j += 1
if i != min_index:
lyst[i], lyst[min_index] = lyst[min_index], lyst[i]
i += 1
# O(n^2)
def bubble_sort(lyst):
"""冒泡排序"""
# 外层循环len(lyst) - 1, j最大能取到倒数第二个值, j+1取到最后一个
for i in range(1, len(lyst)):
for j in range(0, len(lyst) - 1):
if lyst[j] > lyst[j + 1]:
lyst[j], lyst[j + 1] = lyst[j + 1], lyst[j]
# O(n^2)
def insertion_sort(lyst):
"""插入排序"""
# i=1, 表示假定 lyst[0] 为有序数据, 下一个为无序数据
for i in range(1, len(lyst)):
item = lyst[i]
j = i - 1
while j >= 0:
# 如果待排数据小于lyst[j], 就往后覆盖赋值
if item < lyst[j]:
lyst[j + 1] = lyst[j]
j -= 1
# 因为lyst[j] 是当前有序数值中最大的数, 如果比它还大就直接跳出
else:
break
# j 多减了1
lyst[j + 1] = item
# O(nlogn)
# 两种快速排序代码
def quick_sort(lyst, left, right):
"""快速排序"""
middle = (left + right) // 2
# 基准点
pivot = lyst[middle]
if left < right:
# 边界
boundary = left
# 将基准点与最后一个点交换
lyst[middle], lyst[right] = lyst[right], lyst[middle]
# 遍历边界右边, 是否小于基准点
for index in range(left, right):
if lyst[index] < pivot:
lyst[boundary], lyst[index] = lyst[index], lyst[boundary]
boundary += 1
lyst[boundary], lyst[right] = lyst[right], lyst[boundary]
# 左右子列表
quick_sort(lyst, left, boundary - 1)
quick_sort(lyst, boundary + 1, right)
def quick_sort2(lyst, left, right):
"""快速排序的另一种实现"""
if left >= right:
return None
# 基准点
pivot = lyst[left]
i, j = left, right
while i < j:
# 右分区向左
while i < j and lyst[j] > pivot:
j -= 1
if i < j: # 交换
lyst[i], lyst[j] = lyst[j], lyst[i]
i += 1
# 左分区向右
while i < j and lyst[i] < pivot:
i += 1
if i < j: # 交换
lyst[i], lyst[j] = lyst[j], lyst[i]
j -= 1
lyst[i] = pivot
quick_sort2(lyst, left, i - 1)
quick_sort2(lyst, i + 1, right)
def get_lyst(lyst):
lyst.clear()
for i in range(8):
lyst.append(random.randint(1, 8))
def main():
lyst = []
print("selection_sort:")
get_lyst(lyst)
print(lyst)
selection_sort(lyst)
print(lyst)
print("
bubble_sort:")
get_lyst(lyst)
print(lyst)
bubble_sort(lyst)
print(lyst)
print("
insertion_sort:")
get_lyst(lyst)
print(lyst)
insertion_sort(lyst)
print(lyst)
print("
quick_sort:")
get_lyst(lyst)
print(lyst)
quick_sort(lyst, 0, len(lyst) - 1)
print(lyst)
print("
quick_sort2:")
get_lyst(lyst)
print(lyst)
quick_sort(lyst, 0, len(lyst) - 1)
print(lyst)
if __name__ == '__main__':
main()
页面更新:2024-05-11
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号