《直接插入排序》課件

直接插入排序直接插入排序是一種簡單直觀的排序算法。它將待排序的數(shù)組分成已排序和未排序兩部分。每次從未排序部分取出一個(gè)元素，將其插入到已排序部分的正確位置。什么是直接插入排序排序算法直接插入排序是一種簡單直觀的排序算法，它將待排序元素逐個(gè)插入到已排序的子序列中。插入過程排序過程類似于我們整理撲克牌的方式，將牌一張一張地插入到正確的位置。直接插入排序的原理直接插入排序是一種簡單的排序算法，類似于我們平時(shí)整理撲克牌。它將數(shù)組分成兩個(gè)部分：已排序部分和未排序部分，每次將未排序部分的第一個(gè)元素插入到已排序部分的合適位置。通過重復(fù)此過程，直到所有元素都插入到已排序部分，從而完成排序。直接插入排序的實(shí)現(xiàn)步驟1初始化將第一個(gè)元素視為已排序部分。2比較將未排序部分的第一個(gè)元素與已排序部分的元素進(jìn)行比較。3插入將未排序元素插入到已排序部分的正確位置。4重復(fù)重復(fù)上述步驟，直到所有元素都被排序。直接插入排序是一種簡單直觀的排序算法。它將待排序的元素逐個(gè)插入到已排序的部分中，直到所有元素都排序完成。直接插入排序的時(shí)間復(fù)雜度直接插入排序的時(shí)間復(fù)雜度取決于輸入數(shù)據(jù)的排序情況。在最壞情況下，輸入數(shù)據(jù)是逆序排列的，時(shí)間復(fù)雜度為O(n^2)。在最好情況下，輸入數(shù)據(jù)已經(jīng)排序，時(shí)間復(fù)雜度為O(n)。在平均情況下，時(shí)間復(fù)雜度為O(n^2)。直接插入排序的最佳情況分析直接插入排序在最佳情況下，輸入數(shù)組已經(jīng)是排序好的，此時(shí)無需進(jìn)行任何交換操作。1比較次數(shù)n-1次0交換次數(shù)0次n時(shí)間復(fù)雜度O(n)直接插入排序的平均情況分析平均情況時(shí)間復(fù)雜度基本有序O(n)隨機(jī)排列O(n^2)直接插入排序的平均時(shí)間復(fù)雜度為O(n^2)，這是因?yàn)樵谄骄闆r下，每個(gè)元素都需要與前面已經(jīng)排好序的元素進(jìn)行比較并插入到合適的位置。直接插入排序的最壞情況分析直接插入排序的最壞情況發(fā)生在待排序數(shù)組本身已經(jīng)是逆序排列的情況下。例如，數(shù)組[5,4,3,2,1]就是一個(gè)逆序排列的數(shù)組。N比較需要進(jìn)行N-1次比較N移動(dòng)需要進(jìn)行N(N-1)/2次移動(dòng)在這種情況下，每個(gè)元素都需要和前面的所有元素進(jìn)行比較，并進(jìn)行移動(dòng)，導(dǎo)致時(shí)間復(fù)雜度達(dá)到O(n^2)。直接插入排序的穩(wěn)定性穩(wěn)定性定義穩(wěn)定排序算法是指，對于排序前具有相同值的元素，排序后其相對位置保持不變。直接插入排序的穩(wěn)定性直接插入排序是一種穩(wěn)定的排序算法。當(dāng)待排序元素相同時(shí)，插入操作會(huì)將相同元素依次插入到目標(biāo)位置，不會(huì)改變其相對位置。直接插入排序的優(yōu)缺點(diǎn)優(yōu)點(diǎn)直接插入排序是一種簡單易懂的排序算法，實(shí)現(xiàn)起來比較容易。對于規(guī)模較小的數(shù)據(jù)集合，它的效率很高。此外，直接插入排序是一種穩(wěn)定的排序算法，可以保持相等元素的原始相對順序。缺點(diǎn)直接插入排序的時(shí)間復(fù)雜度在最壞情況下為O(n^2)，對于規(guī)模較大的數(shù)據(jù)集合，效率比較低。對于幾乎有序的數(shù)組，直接插入排序表現(xiàn)較好，但對于隨機(jī)排列的數(shù)組，其效率會(huì)受到影響。直接插入排序的應(yīng)用場景數(shù)據(jù)排序直接插入排序適用于小規(guī)模數(shù)據(jù)集排序，特別是數(shù)據(jù)已部分排序的情況。查找直接插入排序可以用于實(shí)現(xiàn)二分查找等搜索算法，提高搜索效率。游戲開發(fā)在一些游戲開發(fā)中，例如牌類游戲，直接插入排序可以用于對玩家手中的牌進(jìn)行排序。網(wǎng)絡(luò)協(xié)議在網(wǎng)絡(luò)協(xié)議中，直接插入排序可以用于數(shù)據(jù)包的排序，例如在數(shù)據(jù)包排序和傳輸過程中。示例1：數(shù)組[5,2,4,6,1,3]本例展示了直接插入排序算法在數(shù)組[5,2,4,6,1,3]上的執(zhí)行過程。該算法通過逐步將每個(gè)元素插入到已排序的子數(shù)組中，最終完成整個(gè)數(shù)組的排序。第一次插入1初始數(shù)組數(shù)組為：[5,2,4,6,1,3]，索引從0開始。2比較第一個(gè)元素第一個(gè)元素為5，無需比較，因?yàn)樗堑谝粋€(gè)元素。3插入第二個(gè)元素第二個(gè)元素為2，需要與第一個(gè)元素5比較。第二次插入比較將當(dāng)前元素2與已排序部分的最后一個(gè)元素5進(jìn)行比較。交換由于2小于5，所以將2與5交換位置。繼續(xù)比較將2與已排序部分的第二個(gè)元素4比較，由于2小于4，繼續(xù)交換。最終位置最后，2被插入到已排序部分的第一個(gè)位置，完成第二次插入。第三次插入14與前一個(gè)元素比較26大于4，無需交換32小于4，交換位置45此時(shí)數(shù)組為[2,5,4,6,1,3]。插入元素4，比較4與5，6，因?yàn)?大于2，所以4插入到第3個(gè)位置。第四次插入11將6插入到已排序的數(shù)組中22從后向前比較33找到6的插入位置44將元素后移將6插入到已排序的數(shù)組中，從后向前比較，找到6的插入位置。將大于6的元素后移，并將6插入到空出的位置。第五次插入比較將1與當(dāng)前已排序序列中的元素進(jìn)行比較。移動(dòng)由于1比3小，因此將3和4分別向后移動(dòng)一位。插入將1插入到空出的位置，完成第五次插入。第六次插入1比較將6與已排序數(shù)組中大于或等于6的元素比較，找到6的插入位置。2移動(dòng)將大于6的元素向右移動(dòng)一位，為6騰出空間。3插入將6插入到找到的位置，完成第六次插入操作。排序結(jié)果排序結(jié)果經(jīng)過六次插入操作，數(shù)組中的元素已按升序排列，最終結(jié)果為[1,2,3,4,5,6]。排序動(dòng)畫動(dòng)畫展示了直接插入排序的整個(gè)過程，幫助理解排序步驟和結(jié)果。示例2：數(shù)組[8,3,1,2,7,5,6,4]該示例中包含了八個(gè)數(shù)字，我們需要使用直接插入排序算法對它們進(jìn)行排序。這將展示如何將每個(gè)數(shù)字依次插入到已排序的子數(shù)組中，最終得到一個(gè)完整的排序數(shù)組。第一次插入1比較將第一個(gè)元素與第二個(gè)元素比較。2交換如果第一個(gè)元素大于第二個(gè)元素，則交換兩個(gè)元素。3移動(dòng)將第二個(gè)元素插入到第一個(gè)元素的位置。插入排序的第一步是最簡單的，只需將第一個(gè)元素與第二個(gè)元素比較，如果第一個(gè)元素大于第二個(gè)元素，則交換兩個(gè)元素。然后將第二個(gè)元素插入到第一個(gè)元素的位置。第二次插入比較將3與已排序部分的最后一個(gè)元素8進(jìn)行比較。由于3小于8，因此需要將8向右移動(dòng)一個(gè)位置。將3插入到當(dāng)前位置。第三次插入1比較將當(dāng)前元素與已排序部分的最后一個(gè)元素比較。2移動(dòng)如果當(dāng)前元素小于已排序部分的最后一個(gè)元素，則將最后一個(gè)元素向后移動(dòng)。3插入將當(dāng)前元素插入到已排序部分的正確位置。第三次插入時(shí)，將元素1與已排序部分的最后一個(gè)元素3進(jìn)行比較，發(fā)現(xiàn)1小于3，因此將3向后移動(dòng)，并將1插入到已排序部分的正確位置。第四次插入1比較將2與1比較2交換交換2和1的位置3插入將2插入到正確的位置4結(jié)果數(shù)組變?yōu)閇1,2,3,7,5,6,4,8]第四次插入，將數(shù)字2插入到已排序的序列中。首先將2與1比較，發(fā)現(xiàn)2大于1，因此不需要交換。然后將2與3比較，發(fā)現(xiàn)2小于3，因此將2插入到3之前的位置。最終數(shù)組變?yōu)閇1,2,3,7,5,6,4,8]。第五次插入1步驟1：比較比較待插入元素7和已排序序列中的元素，從右向左逐個(gè)比較。2步驟2：移動(dòng)由于7大于5，因此將5向右移動(dòng)一位，為7騰出位置。3步驟3：插入將7插入到空位，完成第五次插入操作。第六次插入1比較將5與6進(jìn)行比較2交換交換5和6的位置3插入將5插入到正確位置將5與6進(jìn)行比較，發(fā)現(xiàn)5比6小，交換它們的位置。然后將5插入到排序后的數(shù)組中，此時(shí)5的位置為數(shù)組索引5。第七次插入1已排序部分?jǐn)?shù)組的前六個(gè)元素已經(jīng)排序完成，為[1,2,3,4,5,6]。2待插入元素當(dāng)前待插入元素為7，位于數(shù)組的第7個(gè)位置。3比較與插入將7與已排序部分的最后一個(gè)元素6進(jìn)行比較，7大于6，因此直接將7插入到6的右側(cè)。第八次插入1比較將4與已排序部分的最大值5進(jìn)行比較2交換因?yàn)?小于5，所以交換位置3插入將4插入到排序部分的正確位置現(xiàn)在，已排序部分為[1,2,3,4,5,6,7,8]。排序結(jié)果經(jīng)過八次插入操作，數(shù)