給定以下最初未排序的串列：
[77, 101, 40, 43, 81, 129, 85, 144]
哪種排序演算法在第 3 遍的末尾產生以下串列？是冒泡、插入還是選擇？
[40, 43, 77, 81, 85, 101, 129, 144]
有人可以給我一個關于如何解決這個問題的線索嗎？
uj5u.com熱心網友回復：
插入排序：
def insertion_sort(array):
for i in range(1, len(array)):
key_item = array[i]
j = i - 1
while j >= 0 and array[j] > key_item:
array[j 1] = array[j]
j -= 1
array[j 1] = key_item
print("Step",i,":",array)
return array
data=[77, 101, 40, 43, 81, 129, 85, 144]
insertion_sort(data)
輸出：
Step 1 : [77, 101, 40, 43, 81, 129, 85, 144]
Step 2 : [40, 77, 101, 43, 81, 129, 85, 144]
Step 3 : [40, 43, 77, 101, 81, 129, 85, 144]
Step 4 : [40, 43, 77, 81, 101, 129, 85, 144]
Step 5 : [40, 43, 77, 81, 101, 129, 85, 144]
Step 6 : [40, 43, 77, 81, 85, 101, 129, 144]
Step 7 : [40, 43, 77, 81, 85, 101, 129, 144]
冒泡排序：
def bubble_sort(array):
n = len(array)
for i in range(n):
already_sorted = True
for j in range(n - i - 1):
if array[j] > array[j 1]:
array[j], array[j 1] = array[j 1], array[j]
already_sorted = False
if already_sorted:
break
print("Step:",n-j-1)
print(array)
return array
data = [77, 101, 40, 43, 81, 129, 85, 144]
bubble_sort(data)
輸出：
Step: 1
[77, 40, 43, 81, 101, 85, 129, 144]
Step: 2
[40, 43, 77, 81, 85, 101, 129, 144]
選擇排序：
def selectionSort(array, size):
for step in range(size):
min_idx = step
for i in range(step 1, size):
if array[i] < array[min_idx]:
min_idx = i
(array[step], array[min_idx]) = (array[min_idx], array[step])
print("step",step 1,":",end="")
print(array)
data = [77, 101, 40, 43, 81, 129, 85, 144]
size = len(data)
selectionSort(data, size)
輸出：
step 1 :[40, 101, 77, 43, 81, 129, 85, 144]
step 2 :[40, 43, 77, 101, 81, 129, 85, 144]
step 3 :[40, 43, 77, 101, 81, 129, 85, 144]
step 4 :[40, 43, 77, 81, 101, 129, 85, 144]
step 5 :[40, 43, 77, 81, 85, 129, 101, 144]
step 6 :[40, 43, 77, 81, 85, 101, 129, 144]
step 7 :[40, 43, 77, 81, 85, 101, 129, 144]
step 8 :[40, 43, 77, 81, 85, 101, 129, 144]
您還可以從以下如何運行演算法的鏈接中獲得更多指南： https ://realpython.com/sorting-algorithms-python/
uj5u.com熱心網友回復：
插入排序將在 3 遍中更改最多 3 個專案的相對順序，導致前 3 個專案按順序排列，其余專案保持不變。選擇排序只會影響前 3 個專案和 3 個最小（或最大）專案的位置。只有冒泡排序會交換其他專案。40 和 129 的運動是指向冒泡排序的標志。
請注意，這可能是一個棘手的問題，因為除了其中 2 個（101 和 129，它們是第 2 和第 3 大并且在 2 次傳球后將在正確的位置結束）之外，所有需要移動的數字最多相差 2 個位置。正確實施的冒泡排序不會通過第三次。所以答案可能是“沒有”
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/427529.html
上一篇：使用其中一個POJO值排序？
下一篇：Vue3：按降序渲染物件問題