《算法設計與分析》課件 第2章 排序

算法設計與分析排序排序比較排序冒泡排序堆排序插入排序歸并排序線性排序桶排序計數排序基數排序1.1冒泡排序冒泡排序和選擇排序很相似，但冒泡排序是每次都選擇一個最大的元素，在第i次循環(huán)中，冒泡排序從未排序的元素中選擇一個最大的元素，并將其放在倒數第i個位置。比較：通過依次對兩兩相鄰的元素進行比較1.1冒泡排序一次冒泡過程1.1冒泡排序1.1冒泡排序和選擇排序比較1.2堆排序將元素組織成堆結構，然后每次取堆頂元素1.2堆排序將元素組織成堆結構，然后每次取堆頂元素1.2堆排序將元素組織成堆結構，然后每次取堆頂元素1.2堆排序1.2堆排序是否穩(wěn)定排序？1.3插入排序每次都從剩余的元素中取第一個元素，將其插入到前面已經排序好的序列中，使得插入后的序列依然是排序好的序列1.3插入排序1.3插入排序復雜度計算：插入排序是穩(wěn)定排序1.3插入排序平均復雜度：有沒有可能將插入排序的復雜度降低?1.3插入排序：希爾排序為了減少比較次數，可以跳著比，比如每隔4個元素比較一次1.3插入排序：希爾排序1.3插入排序：希爾排序1.3插入排序：希爾排序1.3插入排序：希爾排序1.3插入排序：希爾排序1.3插入排序：希爾排序1.4歸并排序（合并排序）二路歸并將兩個已經排序好的數組(如數組A和數組B)進行合并，合并后的數組依然是排序好的1.4歸并排序二路歸并1.4歸并排序歸并排序1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較有沒有可能降低比較次數?1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序1.4歸并排序多路歸并排序1.4歸并排序多路歸并排序1.4歸并排序基于錦標賽的多路合并在對k個排序好的子數組進行合并時，利用了一種聯賽的機制來選取最小值。1.4歸并排序勝者樹1.4歸并排序基于勝者樹的合并算法1.4歸并排序敗者樹1.4歸并排序基于敗者樹的合并算法1.4歸并排序基于敗者樹的合并算法2線性排序比較排序所能達到的最優(yōu)復雜度為O(nlog

n)能進一步降低排序的復雜度嗎？非比較排序只適合特定的場景2.1桶排序桶排序的基本步驟2.1桶排序幾個問題2.1桶排序幾個問題如果去比較一個元素是否屬于某個桶，則分發(fā)的復雜度為O(mn)。為了直接得出一個元素屬于哪個桶，需要計算元素所對應桶的下標。這個可以用前面任一復雜度為O(nlogn)的比較排序2.1桶排序算法2.1桶排序例子2.1桶排序2.2計數排序基本思想2.2計數排序問題2.2計數排序算法設置兩個數組B和C，其中B用于存放排序好的數組，而C起著計數的作用(也就是‘桶’的作用)。第一個for循環(huán)(語句4-6)對C進行初始化第二個for循環(huán)(語句7-9)統(tǒng)計每個元素的個數第三個for循環(huán)(語句10-12)就是依次對數組C中第1個元素開始到最后一個進行累加，其作用是統(tǒng)計某個元素前共有多少個元素。第四個for循環(huán)(語句13-16)從A數組的最后一個元素開始，通過C數組中對應的值確定其在B數組中的位置。2.2計數排序算法2.2計數排序2.3基數排序基本思想2.3基數排序流程2.3基數排序例子2.3基數排序問題：需要對‘位’上的數據進行排序，