我正在嘗試實作一種排序演算法，該演算法將找到陣列中的最大和最小元素，然后分別將它們與陣列的最后一個和第一個元素交換。該演算法然后將陣列縮小兩個元素（第一個和最后一個元素，已放置在已排序的位置），然后對子陣列重復執行相同的操作，直到陣列完全排序。
然而，我似乎無法讓它發揮作用，我不知道為什么。沒有任何型別的錯誤，但運行該函式后陣列完全保持不變。這是我所擁有的：
def novel_sort(arr, left, right):
if left < right:
min_index = left
max_index = left
for i in range(left, right 1):
if arr[i] < arr[min_index]:
min_index = i
if arr[i] > arr[max_index]:
max_index = i
arr[left], arr[min_index] = arr[min_index], arr[left]
arr[right], arr[max_index] = arr[max_index], arr[right]
novel_sort(arr, left 1, right - 1)
輸入
l = [235, 25, 123, 1]
novel_sort(l, 0, len(l) - 1)
print(l)
預期輸出
[1, 25, 123, 235]
觀察輸出
[235, 25, 123, 1]
如果我將for回圈更改為，for i in range(left, right)那么除了最后一個元素 ( [1, 123, 235, 25])之外，陣列的每個元素都將被排序。我已經嘗試通過迭代跟隨，但我似乎仍然無法弄清楚發生了什么。
uj5u.com熱心網友回復：
因為您在兩個單獨的步驟中進行交換，所以當您在那里放置最低值時，您冒著交換原始最高值（如果它恰好位于索引左側）的風險。然后，在下一行，最大值的索引（max_index 等于左）不再參考最大值（實際上有 3 種棘手的情況，例如：左邊的最大值，右邊的最小值，以及兩者都在同時）。
當您將回圈更改for i in range(left, right)為左右的相對位置時會受到影響，并且您可能不會遇到相同串列的情況（盡管不同的串列內容可能仍然存在相同的問題）。
正如不要只談代碼所指出的那樣，對索引沖突的補償將比僅僅在一個操作中執行交換涉及更多。
像這樣的事情（我沒有檢查所有邊緣情況，請注意）：
low,high,swapLow,swapHigh = arr[min_index],arr[max_index],arr[left], arr[right]
if right == min_index: swapLow,swapHigh = high,swapLow
if left == max_index: swapLow,swapHigh = swapHigh,low
arr[left],arr[right],arr[min_index],arr[max_index] = low,high,swapLow,swapHigh
當最小值位于右側時，交換會將位于索引左側的原始值放入我們實際希望最高值所在的 min_index 位置（這也是索引右側）。所以我們需要將臨時變數（swapLow）改為最高值。并且 max_index 位置現在需要接收最初位于 min_index 的位置。當最大值位于左側時，同樣的推理也適用。
避免該問題的另一種方法是，如果左值大于右值，則通過在回圈之前左右交換來確保不會發生索引沖突。通過使 index left 處的值小于 index right 處的值，它們都不會在回圈結束時成為對立的交換目標。
def novel_sort(arr, left, right):
if left < right:
min_index = left
max_index = left
if arr[left]>arr[right]: # avoid swapping conflicts
arr[left],arr[right]=arr[right],arr[left]
for i in range(left 1, right 1): # left 1 saves one comparison
if arr[i] < arr[min_index]:
min_index = i
if arr[i] >= arr[max_index]: # changed to >=
max_index = i
arr[left], arr[min_index] = arr[min_index], arr[left]
arr[right], arr[max_index] = arr[max_index], arr[right]
novel_sort(arr, left 1, right - 1)
請注意，我還更改了 max_index 的比較，以便排序正確處理包含重復值的串列。這確保交換的最大值是最高索引處的最大值（因此，如果左右相等且值為最大值，我們不會再次陷入索引沖突）
uj5u.com熱心網友回復：
您的第一次交換可能涉及最大值，使您max_index錯了。兩次交換之間的簡單修復：如果最大值為left，則在第一次交換之后現在為min_index：
arr[left], arr[min_index] = arr[min_index], arr[left]
if max_index == left:
max_index = min_index
arr[right], arr[max_index] = arr[max_index], arr[right]
您可以忽略 have max_indexbeen的情況min_index，因為所有剩余的值都相同，因此無關緊要。
uj5u.com熱心網友回復：
只要使用sort()，如果你想陣列排序。
例子
array=[1,20,4,56,78,3,307]
array.sort()
print(array)
# prints [1, 3, 4, 20, 56, 78, 307]
sort 方法會將原始變數更改為已排序的版本。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313552.html
上一篇：計算組成字串的方法數
下一篇：分而治之：多項式乘法時間復雜度