數(shù)據(jù)結(jié)構(gòu)-排序課件

數(shù)據(jù)結(jié)構(gòu)-排序ppt課件CATALOGUE目錄排序算法概述插入排序選擇排序交換排序歸并排序基數(shù)排序各種排序算法的比較與總結(jié)01排序算法概述0102排序算法的定義排序算法在計(jì)算機(jī)科學(xué)中扮演著非常重要的角色，它們是許多計(jì)算任務(wù)的基礎(chǔ)。排序算法是一種能將一串?dāng)?shù)據(jù)按照特定順序進(jìn)行排列的算法。指將需要排序的數(shù)據(jù)全部加載到內(nèi)存中進(jìn)行排序，例如：插入排序、選擇排序、交換排序、歸并排序等。內(nèi)部排序指需要排序的數(shù)據(jù)量太大，無(wú)法全部加載到內(nèi)存中，需要借助外部存儲(chǔ)設(shè)備進(jìn)行排序，例如：外部歸并排序等。外部排序排序算法的分類排序算法的應(yīng)用場(chǎng)景數(shù)據(jù)庫(kù)系統(tǒng)需要對(duì)大量數(shù)據(jù)進(jìn)行排序，以便進(jìn)行高效的查詢和檢索操作。文件系統(tǒng)需要對(duì)文件和目錄進(jìn)行排序，以便用戶可以更方便地瀏覽和管理文件。數(shù)據(jù)挖掘和分析中需要對(duì)數(shù)據(jù)進(jìn)行排序，以便發(fā)現(xiàn)數(shù)據(jù)中的模式和趨勢(shì)。計(jì)算機(jī)圖形學(xué)中需要對(duì)圖形數(shù)據(jù)進(jìn)行排序，以便進(jìn)行高效的渲染和操作。數(shù)據(jù)庫(kù)系統(tǒng)文件系統(tǒng)數(shù)據(jù)挖掘和分析計(jì)算機(jī)圖形學(xué)02插入排序?qū)⒋判虻脑匕雌渑判虼a的大小，逐個(gè)插入到已經(jīng)排好序的有序序列中，直到所有元素插入完畢。從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；如果該元素（已排序）大于新元素，將該元素移到下一位置；重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；將新元素插入到該位置后；重復(fù)步驟2~5。最好情況下為O(n)，最壞和平均情況下為O(n^2)?；舅枷胨惴ú襟E時(shí)間復(fù)雜度直接插入排序在直接插入排序的基礎(chǔ)上，利用二分查找的思想來(lái)減少比較次數(shù)。從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；取出下一個(gè)元素，在已經(jīng)排序的元素序列中利用二分查找的方法找到其應(yīng)該插入的位置；將該位置及其之后的元素后移一位，為新元素騰出空間；將新元素插入到該位置；重復(fù)步驟2~4。雖然比較次數(shù)減少，但移動(dòng)次數(shù)并未改變，所以時(shí)間復(fù)雜度仍為O(n^2)?；舅枷胨惴ú襟E時(shí)間復(fù)雜度折半插入排序希爾排序算法步驟選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj,tk=1；按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k趟排序；每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度?；舅枷胂葘⒄麄€(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。時(shí)間復(fù)雜度最壞情況下為O(n^2)，最好情況下為O(n^1.3)。03選擇排序基本思想在未排序序列中找到最?。ɑ蜃畲螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ɑ蜃畲螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。時(shí)間復(fù)雜度簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為O(n^2)，其中n為待排序元素的個(gè)數(shù)。穩(wěn)定性簡(jiǎn)單選擇排序是不穩(wěn)定的排序算法。簡(jiǎn)單選擇排序基本思想：將待排序序列構(gòu)造成一個(gè)大頂堆，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。時(shí)間復(fù)雜度：堆排序的時(shí)間復(fù)雜度為O(nlogn)，其中n為待排序元素的個(gè)數(shù)。穩(wěn)定性：堆排序是不穩(wěn)定的排序算法。優(yōu)點(diǎn)：堆排序在最壞的情況下也能保證時(shí)間復(fù)雜度為O(nlogn)，并且其空間復(fù)雜度為O(1)，是一種效率較高的排序算法。堆排序04交換排序010405060302基本思想：通過(guò)相鄰元素之間的比較和交換，使得每一趟循環(huán)都能將最大（或最?。┑脑亍案　钡叫蛄械囊欢恕Ｋ惴ú襟E1.從序列的第一個(gè)元素開(kāi)始，比較相鄰的兩個(gè)元素，如果前一個(gè)元素比后一個(gè)元素大，則交換它們的位置。2.每一趟循環(huán)都將最大（或最小）的元素放到了正確的位置，因此下一趟循環(huán)可以少比較一次。3.重復(fù)執(zhí)行上述步驟，直到整個(gè)序列都有序?yàn)橹埂r(shí)間復(fù)雜度：最好情況下為O(n)，最壞和平均情況下為O(n^2)。冒泡排序基本思想：通過(guò)一趟排序?qū)⒋判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列?？焖倥判蛩惴ú襟E1.選擇一個(gè)基準(zhǔn)元素，通常選擇序列的第一個(gè)元素。2.將序列中比基準(zhǔn)元素小的元素放到它的左邊，比它大的元素放到它的右邊。快速排序快速排序3.對(duì)基準(zhǔn)元素左邊的子序列和右邊的子序列分別進(jìn)行快速排序。時(shí)間復(fù)雜度：最好情況下為O(nlogn)，最壞情況下為O(n^2)，平均情況下為O(nlogn)。05歸并排序歸并排序采用分治法的思想，將待排序序列分成若干個(gè)子序列，對(duì)每個(gè)子序列進(jìn)行排序，最后將有序子序列合并得到完全有序的序列。歸并排序通常采用遞歸的方式實(shí)現(xiàn)，將待排序序列不斷二分，直到子序列長(zhǎng)度為1時(shí)遞歸結(jié)束，開(kāi)始合并相鄰的有序子序列。歸并排序的基本思想遞歸實(shí)現(xiàn)分治法將待排序序列平均分成兩個(gè)子序列，直到子序列長(zhǎng)度為1。分解解決合并對(duì)兩個(gè)有序子序列進(jìn)行合并，得到一個(gè)新的有序序列。將所有有序子序列進(jìn)行合并，得到最終的完全有序序列。030201歸并排序的實(shí)現(xiàn)過(guò)程

歸并排序的時(shí)間復(fù)雜度分析最好情況時(shí)間復(fù)雜度O(nlogn)，當(dāng)待排序序列已經(jīng)有序時(shí)，歸并排序的時(shí)間復(fù)雜度為O(nlogn)。最壞情況時(shí)間復(fù)雜度O(nlogn)，當(dāng)待排序序列為逆序時(shí)，歸并排序的時(shí)間復(fù)雜度為O(nlogn)。平均情況時(shí)間復(fù)雜度O(nlogn)，歸并排序的平均時(shí)間復(fù)雜度為O(nlogn)。其中，n為待排序序列的長(zhǎng)度。06基數(shù)排序基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。分配和收集基數(shù)排序是一種穩(wěn)定的排序算法，即相同的元素在排序后仍保持原有的順序。穩(wěn)定性基數(shù)排序適用于整數(shù)和字符串等可以分割成多個(gè)部分的數(shù)據(jù)類型。適用性基數(shù)排序的基本思想結(jié)束將臨時(shí)數(shù)組中的元素復(fù)制回原數(shù)組，排序結(jié)束。迭代重復(fù)分配和收集的過(guò)程，直到處理完最高位。收集將計(jì)數(shù)數(shù)組中的元素按照順序收集到臨時(shí)數(shù)組中。初始化確定待排序數(shù)組的最大位數(shù)，并初始化計(jì)數(shù)數(shù)組和臨時(shí)數(shù)組。分配從最低位開(kāi)始，將待排序數(shù)組中的元素按照當(dāng)前位數(shù)分配到計(jì)數(shù)數(shù)組中?；鶖?shù)排序的實(shí)現(xiàn)過(guò)程空間復(fù)雜度基數(shù)排序的空間復(fù)雜度為O(n+k)，其中n為待排序數(shù)組的長(zhǎng)度，k為計(jì)數(shù)數(shù)組的長(zhǎng)度。時(shí)間復(fù)雜度基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+k))，其中d為最大位數(shù)，n為待排序數(shù)組的長(zhǎng)度，k為計(jì)數(shù)數(shù)組的長(zhǎng)度。適用場(chǎng)景當(dāng)待排序數(shù)組的元素位數(shù)較少且范圍較小時(shí)，基數(shù)排序具有較高的效率。然而，當(dāng)元素位數(shù)較多或范圍較大時(shí)，基數(shù)排序可能不是最優(yōu)選擇。基數(shù)排序的時(shí)間復(fù)雜度分析07各種排序算法的比較與總結(jié)123平均時(shí)間復(fù)雜度為O(n^2)，在數(shù)據(jù)量較大時(shí)效率較低。冒泡排序、選擇排序、插入排序平均時(shí)間復(fù)雜度為O(nlogn)，在大多數(shù)情況下效率較高。快速排序、歸并排序、堆排序時(shí)間復(fù)雜度可達(dá)到O(n)，但需要滿足一定的數(shù)據(jù)條件。計(jì)數(shù)排序、桶排序、基數(shù)排序時(shí)間復(fù)雜度比較空間復(fù)雜度比較冒泡排序、選擇排序、插入排序、快速排序空間復(fù)雜度為O(1)，原地排序，不需要額外空間。歸并排序空間復(fù)雜度為O(n)，需要額外的空間來(lái)存儲(chǔ)合并后的有序序列。堆排序空間復(fù)雜度為O(1)，原地排序，但需要建立堆結(jié)構(gòu)。計(jì)數(shù)排序、桶排序、基數(shù)排序空間復(fù)雜度與數(shù)據(jù)范圍相關(guān)，可能需要較多的額外空間。03計(jì)數(shù)排序、桶排序、基數(shù)排序穩(wěn)定排序，但需要滿足一定的數(shù)據(jù)條件。01冒泡排序、插入排序、歸并排序穩(wěn)定排序，相同元素的相對(duì)位置不會(huì)改變。02選擇排序、快速排序、堆排序不穩(wěn)定排序，相同元素的相對(duì)位置可能會(huì)改變。穩(wěn)定性比較在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體需求和數(shù)據(jù)特點(diǎn)選擇合適的排序算法。對(duì)于小規(guī)模數(shù)據(jù)，簡(jiǎn)單直觀的算法如冒泡排序、選擇排序和插入排序可能足夠使用。