數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二路歸并排序說明書(已修改)
2025-06-19 14:51 本頁面
【正文】 塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì) 1 / 11 前 言 排序的重要性 生活中，無時(shí)不刻不充滿這排序，比如：班級(jí)同學(xué)的成績排名問題，公司產(chǎn)值高低的問題等等，解決這些問題的過程中，都涉及到了一個(gè)數(shù)據(jù)結(jié)構(gòu)的構(gòu)造思想過程。數(shù)據(jù)結(jié)構(gòu)中的排序，也有很多種，如： 插入排序、交換排序、選擇排序等等，此時(shí)我們就要注意選擇具有優(yōu)解的算法， 將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)有序的排列，便于我們查找。 假設(shè)含有 n 個(gè)記錄的序列為 {R1,R2,Rn},其相應(yīng)的關(guān)鍵字序列為 {K1,K2,… ,Kn}需確定 1， 2… n 的一種排序 P1,P2… Pn,使其相應(yīng)的關(guān)鍵字滿足如 下的非遞減的關(guān)系： Kp1≤Kp2≤ … ≤ Kpn,即按關(guān)鍵字 {Rp1,Rp2,… ,Rpn}有序的排列，這樣的一種操作稱為排序。一般情況下，排序又分為內(nèi)部排序和外部排序。而在內(nèi)部排序中又含有很多排序方法，就其全面性能而言，很難提出一種被認(rèn)為是最好的方法，因?yàn)槊恳环N方法都有它的優(yōu)缺點(diǎn)，適合在不同的環(huán)境下使用。我們學(xué)習(xí)的排序有 :直接插入排序、折半插入排序、希爾排序、快速排序、基數(shù)排序、歸并排序等。本次課題研究中，我主要進(jìn)行了二路歸并排序的研究和學(xué)習(xí)。 設(shè)計(jì)的背景和意義 排序是計(jì)算機(jī)領(lǐng)域的一類非常重要的問題，計(jì)算 機(jī)在出來數(shù)據(jù)的過程中，有 25%的時(shí)間花在了排序上，有許多的計(jì)算機(jī)設(shè)備，排序用去計(jì)算機(jī)處理數(shù)據(jù)時(shí)間的一半以上，這對(duì)于提高計(jì)算機(jī)的運(yùn)行速度有一定的影響。此時(shí)排序算法的高效率顯得尤為重要。 在排序算法匯中， 歸并排序（ Merging sort）是與插入排序、交換排序、選擇排序不同的另一類排序方法。歸并的含義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。歸并排序可分為多路歸并排序，兩路歸并排序，既可用于內(nèi)排序，也可以用于外排序。這里僅對(duì)內(nèi)排序的兩路歸并排序進(jìn)行討論。 而我們這里所探究學(xué)習(xí)的二路歸并排序，設(shè)計(jì)思路更加 清晰、明了，程序本身也不像堆結(jié)構(gòu)那樣復(fù)雜，同時(shí)時(shí)間復(fù)雜度僅為 0(N)，同時(shí)在處理大規(guī)模歸并排序的時(shí)候，排序速度也明顯優(yōu)于冒泡法等一些排序算法，提高排序算法的效率。 正 文 設(shè)計(jì)內(nèi)容 設(shè)計(jì)一個(gè)利用二路歸并算法實(shí)現(xiàn)的排序算法，針對(duì)輸入的一組無序的數(shù)，利用棧或者數(shù)組機(jī)芯存儲(chǔ)，然后進(jìn)行數(shù)據(jù)的兩兩分組、比較，構(gòu)造新的棧或者數(shù)組，依次類推，直到得到一個(gè)有序數(shù)組或者棧，最后輸出有序數(shù)據(jù)，得到有序數(shù)據(jù)。 設(shè)計(jì)要求 假設(shè)初始序列含有 n 個(gè)數(shù)據(jù)（ n 是已經(jīng)確定的數(shù)據(jù)個(gè)數(shù)），首先把 n 個(gè)記錄看成 n塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì) 2 / 11 個(gè)長度為 1 的有序 序列，進(jìn)行兩兩歸并，得到 [n/2]個(gè)長度為 2 的有序序列，再兩兩歸并直到所有記錄歸并成一個(gè)長度為 n 的有序序列為止。 設(shè)計(jì)思想 對(duì)于任意一組數(shù)據(jù)，先利用棧或者數(shù)組將數(shù)據(jù)存儲(chǔ)起來，其中，我們會(huì)用到線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)方法。然后對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行查找和篩選、排序，在出棧的過程中，同時(shí)對(duì)所取數(shù)據(jù)進(jìn)行分組、排列，再次構(gòu)造新的存儲(chǔ)?；蛘邤?shù)組，依次類推，直到得到一個(gè)有序的數(shù)據(jù)時(shí)，執(zhí)行出棧命令，輸出最后的排序結(jié)果。 為了更清晰地說清楚這里的思想，大家來看 圖 1，我們將本是無序的數(shù)組序列{16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14}，通過兩兩合并排序后，再合并，最終獲得了一個(gè)有序的數(shù)組。仔細(xì)觀察它的形狀， 很像 一棵倒置的完全二叉樹， 利用兩兩的比較，一次進(jìn)行遞歸排序，最終得到一個(gè)從小到大的有序序列。
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1