玩轉(zhuǎn)Python插入排序：從基礎(chǔ)到進(jìn)階，成為排序?qū)＜?/h1>

來(lái)源： 責(zé)編： 時(shí)間：2023-09-20 21:55:16 368觀看

導(dǎo)讀插入排序是一種簡(jiǎn)單但有效的排序算法。它的基本思想是將待排序的元素逐個(gè)插入已排序序列中的正確位置，直到所有元素都被插入完成。插入排序的算法復(fù)雜度為O(n^2)，適用于小規(guī)模的數(shù)據(jù)排序。本文將介紹插入排序的原理、具

插入排序是一種簡(jiǎn)單但有效的排序算法。它的基本思想是將待排序的元素逐個(gè)插入已排序序列中的正確位置，直到所有元素都被插入完成。插入排序的算法復(fù)雜度為O(n^2)，適用于小規(guī)模的數(shù)據(jù)排序。本文將介紹插入排序的原理、具體實(shí)現(xiàn)和優(yōu)化，并提供相關(guān)的Python代碼示例。86f28資訊網(wǎng)——每日最新資訊28at.com

86f28資訊網(wǎng)——每日最新資訊28at.com

一、插入排序的基本原理

插入排序的基本原理可以用以下步驟描述：86f28資訊網(wǎng)——每日最新資訊28at.com

1. 將待排序序列的第一個(gè)元素看作已排序序列。
2. 從第二個(gè)元素開(kāi)始，逐個(gè)將元素插入已排序序列的正確位置。
3. 每次插入時(shí)，從后往前比較已排序序列中的元素，將比當(dāng)前元素大的元素依次向后移動(dòng)，直到找到合適的插入位置。
4. 重復(fù)步驟3，直到所有元素都被插入完成，得到有序序列。

插入排序的關(guān)鍵在于找到插入位置并進(jìn)行元素的后移操作。這種排序算法類(lèi)似于我們打撲克牌時(shí)整理手中的牌，每次將一張新牌插入到已排序的牌中的正確位置。86f28資訊網(wǎng)——每日最新資訊28at.com

二、插入排序的具體實(shí)現(xiàn)

下面是插入排序的具體實(shí)現(xiàn)代碼：86f28資訊網(wǎng)——每日最新資訊28at.com

def insertion_sort(arr):    for i in range(1, len(arr)):        key = arr[i]  # 當(dāng)前待插入元素        j = i - 1  # 已排序序列的最后一個(gè)元素的索引        while j >= 0 and arr[j] > key:            arr[j + 1] = arr[j]  # 比當(dāng)前元素大的元素向后移動(dòng)            j -= 1        arr[j + 1] = key  # 將當(dāng)前元素插入到正確位置    return arr

三、插入排序的優(yōu)化

插入排序是一種簡(jiǎn)單但是效率較低的排序算法，特別是對(duì)于大規(guī)模數(shù)據(jù)的排序。但是，我們可以通過(guò)一些優(yōu)化策略來(lái)提高插入排序的性能。86f28資訊網(wǎng)——每日最新資訊28at.com

優(yōu)化1：減少元素的比較次數(shù)

在內(nèi)層循環(huán)中，我們可以通過(guò)使用“哨兵”來(lái)避免每次比較都需要檢查邊界條件。我們可以將待插入的元素復(fù)制到一個(gè)臨時(shí)變量中，并將其作為哨兵，然后在內(nèi)層循環(huán)中只比較哨兵與已排序元素，而不是每次都訪問(wèn)原始數(shù)組。86f28資訊網(wǎng)——每日最新資訊28at.com

def insertion_sort(arr):    for i in range(1, len(arr)):        key = arr[i]  # 當(dāng)前待插入元素        j = i - 1  # 已排序序列的最后一個(gè)元素的索引        while arr[j] > key:            arr[j + 1] = arr[j]  # 比當(dāng)前元素大的元素向后移動(dòng)            j -= 1        arr[j + 1] = key  # 將當(dāng)前元素插入到正確位置    return arr

優(yōu)化2：使用二分查找確定插入位置

傳統(tǒng)的插入排序是通過(guò)逐個(gè)比較已排序元素找到正確的插入位置。但是，我們可以使用二分查找來(lái)確定插入位置，從而減少比較的次數(shù)。86f28資訊網(wǎng)——每日最新資訊28at.com

def insertion_sort(arr):    for i in range(1, len(arr)):        key = arr[i]  # 當(dāng)前待插入元素        left, right = 0, i - 1  # 已排序序列的左右邊界        while left <= right:            mid = (left + right) // 2  # 中間位置            if arr[mid] > key:                right = mid - 1            else:                left = mid + 1        for j in range(i - 1, left - 1, -1):            arr[j + 1] = arr[j]  # 比當(dāng)前元素大的元素向后移動(dòng)        arr[left] = key  # 將當(dāng)前元素插入到正確位置    return arr

四、總結(jié)

本文介紹了插入排序的原理、具體實(shí)現(xiàn)和優(yōu)化。插入排序是一種簡(jiǎn)單但有效的排序算法，適用于小規(guī)模的數(shù)據(jù)排序。通過(guò)不斷將元素插入已排序序列的正確位置，最終得到有序序列。我們還介紹了兩種優(yōu)化策略，包括減少元素的比較次數(shù)和使用二分查找確定插入位置。這些優(yōu)化可以提高插入排序的性能。通過(guò)掌握插入排序的原理和優(yōu)化方法，我們可以更好地理解和應(yīng)用這一常用的排序算法。86f28資訊網(wǎng)——每日最新資訊28at.com

本文鏈接：http://m.www897cc.com/showinfo-26-10586-0.html玩轉(zhuǎn)Python插入排序：從基礎(chǔ)到進(jìn)階，成為排序?qū)＜?/p>

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com

上一篇： 深入理解Java內(nèi)存工作原理

下一篇： 極速Python編程：利用緩存加速你的應(yīng)用程序

標(biāo)簽：

• 熱門(mén)焦點(diǎn)

• MIX Fold3包裝盒泄露 新機(jī)本月登場(chǎng)

  小米的全新折疊屏旗艦MIX Fold3將于本月發(fā)布，近日該機(jī)的真機(jī)包裝盒在網(wǎng)上泄露。從圖上來(lái)看，新的MIX Fold3包裝盒在外觀設(shè)計(jì)方面延續(xù)了之前的方案，變化不大，這也是目前小米旗艦

• 不容錯(cuò)過(guò)的MSBuild技巧，必備用法詳解和實(shí)踐指南

  一、MSBuild簡(jiǎn)介MSBuild是一種基于XML的構(gòu)建引擎，用于在.NET Framework和.NET Core應(yīng)用程序中自動(dòng)化構(gòu)建過(guò)程。它是Visual Studio的構(gòu)建引擎，可在命令行或其他構(gòu)建工具中使用

• Java NIO內(nèi)存映射文件：提高文件讀寫(xiě)效率的優(yōu)秀實(shí)踐！

  Java的NIO庫(kù)提供了內(nèi)存映射文件的支持，它可以將文件映射到內(nèi)存中，從而可以更快地讀取和寫(xiě)入文件數(shù)據(jù)。本文將對(duì)Java內(nèi)存映射文件進(jìn)行詳細(xì)的介紹和演示。內(nèi)存映射文件概述內(nèi)存

• 量化指標(biāo)是與非：挽救被量化指標(biāo)扼殺的技術(shù)團(tuán)隊(duì)

  作者 | 劉新翠整理 | 徐杰承本文整理自快狗打車(chē)技術(shù)總監(jiān)劉新翠在WOT2023大會(huì)上的主題分享，更多精彩內(nèi)容及現(xiàn)場(chǎng)PPT，請(qǐng)關(guān)注51CTO技術(shù)棧公眾號(hào)，發(fā)消息【W(wǎng)OT2023PPT】即可直接領(lǐng)取

• 十個(gè)簡(jiǎn)單但很有用的Python裝飾器

  裝飾器（Decorators）是Python中一種強(qiáng)大而靈活的功能，用于修改或增強(qiáng)函數(shù)或類(lèi)的行為。裝飾器本質(zhì)上是一個(gè)函數(shù)，它接受另一個(gè)函數(shù)或類(lèi)作為參數(shù)，并返回一個(gè)新的函數(shù)或類(lèi)。它們通常用

• JVM優(yōu)化：實(shí)戰(zhàn)OutOfMemoryError異常

  一、Java堆溢出堆內(nèi)存中主要存放對(duì)象、數(shù)組等，只要不斷地創(chuàng)建這些對(duì)象，并且保證 GC Roots 到對(duì)象之間有可達(dá)路徑來(lái)避免垃 圾收集回收機(jī)制清除這些對(duì)象，當(dāng)這些對(duì)象所占空間超過(guò)

• 為什么你不應(yīng)該使用Div作為可點(diǎn)擊元素

  按鈕是為任何網(wǎng)絡(luò)應(yīng)用程序提供交互性的最常見(jiàn)方式。但我們經(jīng)常傾向于使用其他HTML元素，如 div span 等作為 clickable 元素。但通過(guò)這樣做，我們錯(cuò)過(guò)了許多內(nèi)置瀏覽器的功能。

• 東方甄選單飛：有些鳥(niǎo)注定是關(guān)不住的

  文/彭寬鴻編輯/羅卿東方甄選創(chuàng)始人俞敏洪帶隊(duì)的“7天甘肅行”直播活動(dòng)已在近日順利收官。成立后一年多時(shí)間里，東方甄選要脫離抖音自立門(mén)戶(hù)的傳聞不絕于耳，“7

• OPPO K11樣張首曝：千元機(jī)影像“卷”得真不錯(cuò)！

  一直以來(lái)，OPPO K系列機(jī)型都保持著較為均衡的產(chǎn)品體驗(yàn)，歷來(lái)都是2K價(jià)位的明星機(jī)型，去年推出的OPPO K10和OPPO K10 Pro兩款機(jī)型憑借各自的出色配置，堪稱(chēng)有