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

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

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