我正在學習排序演算法，現在是Insertion Sort. 在網上復制代碼之前，我想先根據我對演算法的理解撰寫代碼。
我的理解Insertion Sort是：要排序list a，首先創建一個包含排序元素的串列（稱為a_sorted），第一個元素是a[0]。然后我將嘗試將每個元素a融入到a_sorted（希望我理解這個想法正確）。所以我實作的想法如下：
a = [4, 3, 1, 5, 7, 9, 6, 2]
n = len(a)
def insertion_sort(a, n):
a_sorted = [a[0]] # Create a list contain sorted elements, first ele is a[0] => [4]
for i in range(1,n): # Iterate through original list, from 1th ele (start from 3)
if a[i] <= a_sorted[0]:
# First check if the ith ele is smaller than the first ele in the sorted list (smallest). If so insert it to the start of a_sorted
# For example, a_sorted is [3,4], ith ele is 1, 1<3 so add 1 to the start of a_sorted => [1,3,4]
# Then continue to the next ith element
a_sorted.insert(0, a[i])
continue
for j in range(len(a_sorted)-1,-1,-1):
# Compare ith ele to each ele of a_sorted, from largest to the smallest (right to left)
# If ith ele > jth ele in a_sorted, insert ith ele right after the position of jth ele in a_sorted
# For example ith ele is 6, a_sorted is [1, 3, 4, 5, 7, 9], then compare 6 to 9,7,5; 6>5 so insert 6 right after 5 => [1, 3, 4, 5, 6, 7, 9]
# Continue to next ith
if a[i] > a_sorted[j]:
a_sorted.insert(j 1, a[i])
break
print(insertion_sort(a, n))
一切都很好，我得到了正確的輸出。我只是嘗試堅持插入的想法。但是當我在谷歌上搜索插入排序演算法的代碼時。該代碼看起來與我的完全不同（它無處不在，所以我認為這是插入排序的標準優化代碼）。下面是代碼：
def insertionSort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >=0 and key < arr[j] :
arr[j 1] = arr[j]
j -= 1
arr[j 1] = key
它更短。但我根本不明白它是如何作業的。不過，這不是我的問題，我的問題是：
- 我的代碼是否仍然考慮插入排序？
- 我的代碼是否與互聯網上的最佳代碼一樣高效（時間復雜度 O(n^2) 平均值、空間復雜度......）
我只是想確保當他們要求插入排序時，我可以在面試或考試中使用我的代碼。我更喜歡我的代碼，因為我理解它并自己撰寫它，因此更容易記住。
uj5u.com熱心網友回復：
是的，您的代碼是具有 O(n2) 時間復雜度的插入排序：它維護一個排序串列，然后通過移動元素在線性時間的正確位置插入專案。
您找到的常見實作就地作業（僅使用交換）。這意味著它具有更好的空間復雜度：它只需要恒定的輔助存盤 O(1)，而您需要線性輔助存盤 O(n) 來存盤排序串列a_sorted。
它通過將串列“磁區”為“已排序”和“未排序”部分，并在每個步驟中不斷地將“已排序”部分增加一個。我已經在您找到的實作中添加了注釋來解釋這一點。
def insertionSort(arr):
# after this loop has run len(arr) - 1 times, the sorted part starting from the first index will have grown to the full array length and the unsorted part will be empty
for i in range(1, len(arr)):
# at this point, arr[:i] is sorted; you can verify this by doing
# print(arr[:i]) here
key = arr[i] # this element has to be inserted at the correct pos in arr[:i 1]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position: These elements
# have to be shifted "up" in order to allow inserting
# the key at the right position; this step is responsible
# for the quadratic complexity as it requires linear time
j = i-1
while j >= 0 and key < arr[j] :
arr[j 1] = arr[j]
j -= 1
# the index to insert the key at is j, because arr[j] < key holds
arr[j 1] = key
# after this step, the sorted part has grown by one, from arr[:i] to arr[:i 1]
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/471196.html
上一篇：最長子序列：缺少最后一個元素