前言

本章主要講述：用python編寫[冒泡排序]及[快速排序]

• ps：八大排序算法，以前用Java寫過，詳細請看
• Java編寫：https://blog.csdn.net/Makasa/article/details/90743414

一、具體代碼編寫

"""
用python編寫八大排序算法：
交換排序：冒泡排序、快速排序
插入排序：直接插入排序，希爾排序
選擇排序：簡單選擇排序，堆排序
歸並排序
基數排序
"""
# list = [1, 5, 4, 2, 7, 3, 8]
list = [1, 5, 3, 2]
li = [1, 5, 4, 2, 7, 3, 8]
def bubble_sort():
"""
冒泡排序：簡單來說就是相鄰兩個元素進行比較，大的放右邊，小的放左邊，
第一輪後，最大值就出現在最大索引處，指針從0開始
整個冒泡排序算法走了【n-1】趟
冒泡排序時間復雜度為O(n^2)
:return:
"""
for i in range(len(list) - 1): # 控制一共比較多少輪
for j in range(0, len(list) - i - 1): # 控制比較的次數
if list[j] > list[j + 1]:
# 如果 當前值 > 右邊的值，那就把當前值賦值到後面
temp = list[j]
list[j] = list[j + 1]
list[j + 1] = temp
print(list)
def quick_sort(alist, start, end):
"""
快速排序：取一個基數(一般都是第一個數和最後一個數)，比它大的數都放後面，比它小的都放它前面，然後依次遞歸
:return:
"""
if start >= end:
# 退出遞歸
return
pivot = alist[start]
right = end
left = start
# 控制right -= 1不滿足條件交換
while left < right:
while left < right and alist[right] > pivot:
right -= 1
else:
# 交換
alist[left] = alist[right]
# 控制 left += 1 , 不滿足條件交換
while left < right and alist[left] < pivot:
left += 1
else:
alist[right] = alist[left]
# 退出循環 left = right
# left 或者 right 對應的位置 賦值為基准值
alist[left] = pivot
# 遞歸自己調用自己
quick_sort(alist, start, left - 1) # 對左邊排序
quick_sort(alist, left + 1, end) # 對右邊排序
def select_sort():
"""
選擇排序：一趟排序記錄最小的數，放到第一個位置
在一趟排序記錄列表無序區最小的數，放到第二個位置
算法關鍵點:有序區和無序區、無序區最小值的位置
時間復雜度：O(n2)
:return:
"""
for i in range(len(li) - 1):
min_loc = i
for j in range(i + 1, len(li)):
if li[j] < li[min_loc]:
min_loc = j
if min_loc != i:
li[i], li[min_loc] = li[min_loc], li[i]
print(li)
if __name__ == '__main__':
# bubble_sort()
# select_sort()
quick_sort(list, 0, len(list) - 1)
print(list)