sort
氣泡排序 BubbleSort
氣泡排序 遞增 相鄰兩數比較法
a = list(map(int,input("輸入未排序數字:").split()))
exCnt = 0
for i in range(1,len(a)):
for j in range(0,len(a)-i):
if a[j]>a[j+1]:
t = a[j]
a[j] = a[j+1]
a[j+1] = t
exCnt = exCnt + 1
#顯示排序過程
print("第",i,"回合",a)
#顯示排序結果
print("氣泡排序後:",a,"交換",exCnt,"次")
氣泡排序優化版
a = list(map(int,input("輸入未排序數字:").split()))
exCnt = 0
for i in range(1,len(a)):
ex = 0
for j in range(0,len(a)-i):
if a[j]>a[j+1]:
t = a[j]
a[j] = a[j+1]
a[j+1] = t
exCnt = exCnt + 1
ex = 1
#顯示排序過程
print("第",i,"回合",a)
if ex==0:
break
#顯示排序結果
print("氣泡排序後:",a,"交換",exCnt,"次")
選擇排序 SelectSort
選擇排序 改良氣泡排序交換過多問題
a = list(map(int,input("輸入未排序數列:").split()))
print(a)
cnt = 0
for i in range(len(a)-1):
min_index = i
for j in range(i+1,len(a)):
if a[min_index]>a[j]:
min_index = j
if min_index != i:
t = a[min_index]
a[min_index] = a[i]
a[i] = t
cnt = cnt + 1
print("第",i+1,"回合",a)
print("選擇排序後:",a,"交換",cnt,"次")
插入排序 InsertSort
插入排序 改良氣泡與選擇比較次數過多問題,只要n-1次循環
a = list(map(int,input("輸入未排序數列:").split()))
print(a)
#第一個當作已排序
for i in range(1,len(a)):
j = i
counter = 0
while j>0 and a[j-1]>a[j]:
temp = a[j]
a[j] = a[j-1]
a[j-1] = temp
counter += 1
j = j - 1
print("第",i,"次循環",a,counter)
print("插入排序",a)
快速排序 QuickSort
快速排序 分治法 遞迴
def quicksort(arr):
# 檢查陣列是否只有一個元素或是空的
if len(arr) <= 1:
# 如果是,直接返回該陣列
return arr
else:
# 選擇陣列中的第一個元素作為基準點(pivot)
pivot = arr[0]
# 分割陣列為比基準點小的部分(less)比pivot小的數放入less串列內
less = [x for x in arr[1:] if x <= pivot]
# 分割陣列為比基準點大的部分(greater)比pivot大的數放入greater串列內
greater = [x for x in arr[1:] if x > pivot]
# 遞迴地對這兩個部分進行排序,然後組合它們和基準點以得到最終的排序結果
print(less,pivot,greater)
return quicksort(less) + [pivot] + quicksort(greater)
# 測試資料
data = [9, 7, 2, 1, 4, 6, 8, 5, 3, 10]
print(data)
# 呼叫快速排序函數
result = quicksort(data)
# 顯示排序後的結果
print("排序後的結果:", result)