資源簡(jiǎn)介

(共16張PPT)
5-3-2 排序算法的應(yīng)用
5-3-2 排序算法的應(yīng)用
窮舉算法
遞歸算法
動(dòng)態(tài)規(guī)劃算法
算法
數(shù)據(jù)存儲(chǔ)
數(shù)組
鏈表
跳躍表算法
遍歷
線性遍歷
樹結(jié)構(gòu)遍歷
平衡樹
排序算法的發(fā)展變化
解決n個(gè)數(shù)的升序排列問(wèn)題
冒泡排序
依次比較前后兩個(gè)元素，如果逆序就交換兩個(gè)位置上的元素，將最小數(shù)交換到最前面，這樣的過(guò)程重復(fù)n-1遍即可實(shí)現(xiàn)，算法的時(shí)復(fù)雜度為O(n2)。
n個(gè)元素冒泡排序的比較次數(shù)是n(n-1)/2，最壞情況下的交換次數(shù)要達(dá)到n(n-1)/2，交換頻繁，影響效率。
選擇排序
如果不交換元素位置，待找到無(wú)序區(qū)中的最小元素后，直接把最小元素交換到有序區(qū)的末位位置，這樣就減少了交換的次數(shù)，但時(shí)間復(fù)雜度依然為O(n2)。
插入排序
在訪問(wèn)無(wú)序區(qū)元素的過(guò)程中，將當(dāng)前訪問(wèn)的元素直接在有序區(qū)中找一個(gè)合適的位置插入即可。
希爾排序
既然插入排序在基本有序的情況下性能相對(duì)較好，那就想辦法達(dá)到這樣的狀態(tài)，于是有人想出了跳躍分割的方式，將相距某個(gè)增量的數(shù)據(jù)組成一個(gè)子序列，這樣就能保證在子序列內(nèi)分別進(jìn)行插入排序后，得到的結(jié)果基本有序。
排序算法的發(fā)展變化
解決n個(gè)數(shù)的升序排列問(wèn)題
快速排序和歸并排序
快速排序和歸并排序都利用了分治思想，核心在于“分而治之，各個(gè)擊破“
快速排序計(jì)算過(guò)程：
（1）從數(shù)值隊(duì)列中選擇一個(gè)基準(zhǔn)元素。
（2）將隊(duì)列中的其他元素與基準(zhǔn)元素比較，比基準(zhǔn)元素小的元素放在基準(zhǔn)元素的左邊，比基準(zhǔn)元素大的放在右邊，則隊(duì)列被基準(zhǔn)元素分為左右兩個(gè)區(qū)間。
（3）對(duì)兩個(gè)區(qū)間的值分別遞歸步驟（2），使其最終形成有序的序列。
排序算法的發(fā)展變化
解決n個(gè)數(shù)的升序排列問(wèn)題
例1
對(duì)于隊(duì)列數(shù)值“4、3、6、2、5”采用快速排序進(jìn)行升序排序
以上采用的排序方法都屬于內(nèi)排序，內(nèi)排序是指能夠在內(nèi)存中完成的排序，當(dāng)計(jì)算機(jī)內(nèi)存小于數(shù)據(jù)本身大小時(shí)，無(wú)法一次性將數(shù)據(jù)加載到內(nèi)存，這時(shí)候就需要采用外排序的方式。
外排序主要是針對(duì)大文件的排序，將需要排序的數(shù)據(jù)文件存放到存儲(chǔ)器中，每次加載部分?jǐn)?shù)據(jù)到內(nèi)存，不斷進(jìn)行內(nèi)存和外部存儲(chǔ)器之間的數(shù)據(jù)交換，最終保證文件中的每個(gè)數(shù)據(jù)都完成排序。
例2 有4GB的數(shù)據(jù)文件需要進(jìn)行排序，當(dāng)前操作系統(tǒng)的有效可用內(nèi)存為1GB，則需要按照外歸并排序的流程完成排序。
（3）采用四路歸并的方式進(jìn)行歸并排序：在4個(gè)1GB文件中，分別讀取200MB數(shù)據(jù)存入內(nèi)存的輸入緩沖區(qū)，共占用計(jì)算內(nèi)存800MB，將剩余的200MB作為輸出緩沖區(qū)，如圖所示。
（1）將4GB的數(shù)據(jù)文件平均拆分為4個(gè)1GB的數(shù)據(jù)文件
（2）將每份1GB數(shù)據(jù)文件加載到內(nèi)存，采用內(nèi)排序的方式（如快速排序）在內(nèi)存中完成對(duì)該數(shù)據(jù)文件的排序，并將排序后的結(jié)果寫入文件。
（4）將輸入緩沖區(qū)的四路數(shù)據(jù)進(jìn)行歸并排序，依次存入輸出緩沖區(qū)，當(dāng)輸出緩沖區(qū)滿時(shí)，則寫入文件，當(dāng)緩沖區(qū)中某路數(shù)據(jù)輸入完畢后，則再向文件中讀取200MB數(shù)據(jù)存入輸入緩沖區(qū)，不斷進(jìn)行該過(guò)程直到所有的數(shù)據(jù)通過(guò)四路歸并的方式完成排序。
例2 有4GB的數(shù)據(jù)文件需要進(jìn)行排序，當(dāng)前操作系統(tǒng)的有效可用內(nèi)存為1GB，則需要按照外歸并排序的流程完成排序。
設(shè)有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，請(qǐng)寫出按二路歸并方法對(duì)該序列進(jìn)行升序排序的過(guò)程。
問(wèn)題與討論
Q D F X A P N B Y M C W
Q D F X A P
N B Y M C W
Q D F
X A P
N B Y
M C W
Q D
X A
F
P
D
Q
X
A
N B
M C
Y
W
N
B
M
C
D Q
A X
B N
C M
F
P
Y
W
D F Q
A P X
B N Y
C M W
A D F P Q X
B C M N W Y
A B C D F M N P Q W X Y
F
P
Y
W
分治法
分解成子問(wèn)題
分別解決
合并答案
4.1.2 立足系統(tǒng)架構(gòu)的算法發(fā)展
并行計(jì)算是指同時(shí)使用多種計(jì)算資源解決計(jì)算問(wèn)題的過(guò)程，是提高計(jì)算機(jī)系統(tǒng)計(jì)算速度和處理能力的一種有效手段。
它的基本思想是用多個(gè)處理器來(lái)協(xié)同求解同一問(wèn)題，即將被求解的問(wèn)題分解成若干個(gè)部分，各部分均由一個(gè)獨(dú)立的處理機(jī)來(lái)并行計(jì)算。
4.1.2 立足系統(tǒng)架構(gòu)的算法發(fā)展
從程序和算法設(shè)計(jì)的角度來(lái)看，并行計(jì)算可分為任務(wù)并行和數(shù)據(jù)并行。
任務(wù)并行是不同的CPU執(zhí)行不同的任務(wù)，處理相同的數(shù)據(jù)。
數(shù)據(jù)并行是每個(gè)核心執(zhí)行相同的命令，處理不同的數(shù)據(jù)。
在現(xiàn)有算法不適應(yīng)時(shí)，要善于發(fā)掘和利用現(xiàn)有串行算法中的并行性，合理地選擇算法，并且合理地設(shè)置閾值，能夠十分有效地提高計(jì)算機(jī)的運(yùn)行效率。
4.1.2 立足系統(tǒng)架構(gòu)的算法發(fā)展
4.1.3 基于大數(shù)據(jù)和人工智能的算法發(fā)展
課堂小結(jié)
思考與練習(xí)
題目描述：給定一個(gè)由數(shù)字組成的序列，編程實(shí)現(xiàn)利用歸并排序?qū)⑵浒凑諒男〉酱蟮捻樞蜻M(jìn)行排序。
輸入數(shù)據(jù)：7,6,3,8,2,9,1,4,5
輸出結(jié)果：1,2,3,4,5,6,7,8,9

展開更多......

收起↑