在這篇博文中，我們將采用問題驅(qū)動(dòng)的方法來了解插入排序算法的基礎(chǔ)知識(shí)。當(dāng)我試圖找到一種更好的方法來理解插入算法和我即將學(xué)習(xí)的其他算法時(shí)，我想到了這種方法。我想建立一個(gè)可以應(yīng)用于我將要學(xué)習(xí)的大多數(shù)（如果不是全部）算法的策略。當(dāng)我思考這個(gè)問題時(shí)，我確信我可能必須使用第一原理思考

受到第一原理思維的啟發(fā)，這種方法首先要嘗試掌握算法，無論我們最初的理解是模糊的還是清晰的。然后，我們確定構(gòu)成算法的微小概念或機(jī)制。通過圍繞這些機(jī)制或微小概念提出問題。我們本質(zhì)上是試圖從不同的小角度理解算法的工作原理，重點(diǎn)是嘗試解決我們自己形成的問題。

您形成的答案最初可能與實(shí)際算法中使用的語法相似，也可能不相似。目標(biāo)應(yīng)該是自己回答問題，無論語法是否接近。一旦你有了清晰的理解，你就可以轉(zhuǎn)換、合并你的答案以使用語法，類似于算法的實(shí)際實(shí)現(xiàn)。我相信這個(gè)過程可以讓您探索代碼的替代形式，理解為什么使用特定語法，以更好的方式自行處理邊緣情況。

我相信這種方法可以確保我們理解每行代碼背后的理論和推理，使實(shí)現(xiàn)過程更加直觀和有意義。以下問題和我經(jīng)歷的思考過程幫助我更好地理解插入排序，并使我能夠有效地編碼。

對(duì)于你來說，問題可能會(huì)有所不同；它們可以更多、更少或完全不同。有人可能會(huì)說這類似于逆向工程，不管你怎么稱呼它，這個(gè)方法讓我對(duì)插入排序算法有了透徹的了解。我希望它對(duì)您的任何其他算法也能起到同樣的作用。蘇，讓我們開始吧！

插入排序?qū)崿F(xiàn)

這是我們最終將實(shí)現(xiàn)插入排序的代碼形式。

def insertion_sort(values):

    for new_value_index in range(1,len(values)):

        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1

        values[index+1] = new_value

問題

給定一個(gè)排序列表，使用 while 循環(huán)，從右到左打印值。

values = [4,8,12,16,20,24,30]
# given a sorted list, using while loop, print values from right to left.

index = len(values)-1
while index>=0:
    print(values[index],end = " ")
    index-=1

給定一個(gè)排序列表和一個(gè)新值，找到要插入新值的索引以保持列表排序。

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# using while loop, if traversing from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value: break
    index-=1

print(values,new_value,index)

給定一個(gè)排序列表和一個(gè)新值，將新值插入到列表中，使其保持排序狀態(tài)。

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# if traversal from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value:break
    index-=1

values = values[:index+1] + [new_value] + values[index+1:]
print(values)

給定一個(gè)排序列表，然后附加一個(gè)新值，將新值移動(dòng)到給定的索引位置。

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

given_index = 3

# above given

n = len(values)-1

index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

print(values)

values[given_index+1] = new_value

print(values)

給定一個(gè)排序列表，然后附加一個(gè)新值，對(duì)列表進(jìn)行排序。

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

print(values)

### given a sorted list, then appended with new value, sort the list
####

n = len(values)-1
new_value = values[-1]

# find the index at which the value is to be inserted
# right to left
index = n-1
while index>=0:
    if values[index]<new_value:break
    index-=1
given_index = index 
print("given_index : "  , given_index)

# move the values forward by one step until we reach the given index
index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

values[index+1] = new_value

print(values)

給定一個(gè)排序列表，然后附加一個(gè)新值，對(duì)列表進(jìn)行排序。

values = [4, 8, 12, 16, 20, 24, 30]

new_values = [14,32]

values += new_values

print(values)

# given a sorted list, then appended with two new value(s), sort the list

n = len(values)-1

new_value_start_index = n - 1

print(new_value_start_index, values[new_value_start_index])

for new_value_index in range(new_value_start_index,len(values)):

    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value: break
        values[index+1] = values[index]
        index-=1

    values[index+1] = new_value

print(values)

給定一個(gè)列表，對(duì)其進(jìn)行排序。

import random

values = random.sample(range(10,90), k = 10)

values

print(values)

for new_value_index in range(1,len(values)):
    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value:break
        values[index+1] = values[index]
        index-=1
    values[index+1] = new_value

print(values)

插入排序?qū)崿F(xiàn)

def insertion_sort(values):
    for new_value_index in range(1,len(values)):
        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1
        values[index+1] = new_value

其他資源

雖然我最初通過一系列全面的問題來更好地理解該算法，但我認(rèn)為上述一組問題對(duì)于更好地理解插入排序非常重要。如果包含我所解決的所有問題，這篇文章就會(huì)變得相當(dāng)冗長。

對(duì)于那些有興趣查看所有問題的人，我創(chuàng)建了一個(gè) Jupyter Notebook，其中包含全套問題和我自己的答案，這使我能夠完全理解插入排序的實(shí)現(xiàn)。

如果您想進(jìn)一步深入研究，我鼓勵(lì)您查看筆記本。

歡迎指正和建議。

以上是理解插入排序：問題驅(qū)動(dòng)的方法的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！