python排序算法-插入排序

文章目錄

• 原理
• 動圖示範
• 二、代碼
• • 1.插入排序
• 總結

原理

插入排序的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。插入排序在實作上，通常采用in-place排序，因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。

動圖示範

二、代碼

1.插入排序

代碼如下（示例）：

def insertion_sort(nums):
    """
    :param nums: 無序數組
    :return:
    """
    for i in range(1, len(nums)):
        for j in range(i, 0, -1):
            print(j, nums[j], nums[j - 1])
            if nums[j] < nums[j - 1]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break
            print(nums)
    return nums


if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6]
    insertion_sort(arr)
    print("排序後的數組:", arr)
           

時間複雜度：

O(n2)。

總結

工作随筆，希望可以幫助到大家！

如有不足之處，請多多指教！