內(nèi)部排序課程設(shè)計(jì)---內(nèi)部排序算法的比較(編輯修改稿)
2025-07-11 13:36 本頁面
【文章內(nèi)容簡(jiǎn)介】 ，直到全部待排序的數(shù)據(jù)元素排序完畢。 排序 這是一種最簡(jiǎn)單的排序方法，它的基本操作時(shí)將一個(gè)記錄插入到一個(gè)已經(jīng)排好序的有序表中，從而得到一個(gè)新的記錄數(shù)增 1的有序表。其效率：從空間的角度來看待，它只需要一個(gè)輔助的空間，從時(shí)間上來看的話，排序的基本操作是比較兩個(gè)關(guān)鍵字的大小和移動(dòng)（本程序中將移動(dòng)和交換看成一樣）記錄。在整個(gè)排序的過程中，當(dāng)待排序列中的關(guān)鍵字非遞減有序的話 ，那么比較次數(shù)最小 n1，且不需要移動(dòng)，當(dāng)待排序列逆序時(shí)，比較次數(shù)達(dá)到最大（ n+2）（ n1） /2，記錄的移動(dòng)的次數(shù)也達(dá)到最大值（ n+4）（ n1）/2。取平均值得時(shí)候直接插入排序的時(shí)間復(fù)雜度 O(n178。)。排序是穩(wěn)定的。 排序 這種排序的比較基本思想就是兩兩比較待排序的數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)候，就進(jìn)行交換，知道沒有反序的數(shù)據(jù)為止。冒泡排序是一次的比較找出最?。ㄗ畲螅┲?，然后將其放置序列的最后一個(gè)位置，再將剩下的從第一個(gè)位置開始至 ni的位置進(jìn)行重復(fù)的操作。 首先 在 r[1..n]中，第一趟，確定一個(gè)軸 r[1]，并把軸上的關(guān)鍵字復(fù)制給 r[0]。先從最高位開始比較 ,若 r[1]=r[high]，則 high—— ；若 r[1]r[high],r[low]=r[high],在高位找到第一個(gè)比 r[1]小的的值后 .再?gòu)牡臀婚_始比較，若 r[low]=r[1],則 low++，若 r[low]r[1],r[high]=r[low],在低位找到第一個(gè)比 r[1]大的數(shù)，依次重復(fù)上敘兩個(gè)比較動(dòng)作，直到全部比較完成，將 r[i]放到 中間 某個(gè)位置上使得 r[1]左邊所有的關(guān)鍵字小于 r[1]右邊 所有記的關(guān)鍵字，并保留該位置，使得數(shù)組分成了兩組。再采用遞歸，直至每組只有一個(gè)數(shù)據(jù)，即已排好了序。 算法分析 就平均速度而言，快速排序是已知內(nèi)部排序方法中最好的一種排序方法，其時(shí)間復(fù)雜度為O(nlog(n))。但是，在最壞情況下（基本有序時(shí)）快速排序所需的比較次數(shù)和冒泡排序的比較次相同，其時(shí)間復(fù)雜度為 O（ n^2）?？焖倥判蛐枰粋€(gè)棧作輔助空間，用來實(shí)現(xiàn)遞歸處理左、右子兩組。在最壞情況下，遞歸深度為 n，因此所需棧的空間大小為 O(n)數(shù)量級(jí)?？焖倥判蚴遣环€(wěn)定的。 8 排序 屬于一種插入排序類的方法，先將整 個(gè)待排序記錄分成若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)整體記錄進(jìn)行一次直接插入排序。實(shí)質(zhì)上就是一個(gè)將序列分塊化，然后再對(duì)各個(gè)塊進(jìn)行排序，化整為零的操作，最后待序列差不多有序的時(shí)候進(jìn)行一次化零為整操作，實(shí)現(xiàn)最后一次的插入排序。 9 第三章 總結(jié) 我做的課程設(shè)計(jì)是內(nèi)部排序的比較，之所以選擇這個(gè)題目是因?yàn)槔蠋熣f這個(gè)實(shí)用性比較強(qiáng)。并且，對(duì)于排序我是懂的少之又少，也希望通過這次實(shí)訓(xùn)能夠?qū)⑺莆蘸?。這次實(shí)訓(xùn)的理論基礎(chǔ)是建立在最后一 段時(shí)間的學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》中的內(nèi)部排序算法上，通過對(duì)各個(gè)內(nèi)部排序的算法的分析，比較它們所要花費(fèi)的時(shí)間，移動(dòng)次數(shù)、比較次數(shù)等等 。 確實(shí)，這次的課程設(shè)計(jì)讓我對(duì)排序有了很深刻的了解。首先，幾乎是一籌莫展，因?yàn)?，在上理論課將排序的時(shí)候沒認(rèn)真聽。所以，不得不把書關(guān)于排序的一字一字的仔細(xì)看，仔細(xì)理解。然后就開始編寫代碼。先是把 各個(gè)排序的代碼寫出來，我所用的排序有希爾排序、快速排序 、冒泡排序、插入排序、選擇排序。 當(dāng)然，在寫代碼的過程中也遇到了些許問題。比如說寫那個(gè)隨機(jī)取數(shù)的函數(shù)的時(shí)候 不知道怎么寫，后來自己百度了一下，然后 也詢問了老師、同學(xué)最后才把它寫出來。另外，我覺得還有一個(gè)難點(diǎn)就是計(jì)算每個(gè)排序用的時(shí)間。因?yàn)椋玫揭粋€(gè)時(shí)間函數(shù)嘛，然后之前又沒有接觸過，所以，在寫代碼的時(shí)候，在那里就卡殼了。后來還是問了同學(xué)，老師的指點(diǎn)才弄明白。 總的來說，覺得這次的課程設(shè)計(jì)還是偏容易的，我也有很大的收獲。加強(qiáng)了自己的動(dòng)手操作能力，也讓自己學(xué)會(huì)獨(dú)立思考，同時(shí)增加了自己的知識(shí)。最重要的是，對(duì)排序有了更為深刻的了解。當(dāng)然，通過這次的課程設(shè)計(jì)也發(fā)現(xiàn)了自己很多的不足。深深地意識(shí)到了自己的操作能力還有待加強(qiáng)。在平時(shí)，應(yīng)該多編寫一些程序，同時(shí)，也應(yīng)該 擴(kuò)大自己的知識(shí)面，多去鉆研，多動(dòng)腦、動(dòng)手。 。 最后，對(duì)傳授自己數(shù)據(jù)結(jié)構(gòu)知識(shí)的曾俊勇老師說一聲謝謝！ 參考文獻(xiàn) 譚浩強(qiáng)著，《 C 語言設(shè)計(jì)題解與上機(jī)指導(dǎo)》，清華大學(xué)出版社， 附錄代碼 A include include include include define MAX 20210 define SWAP(x,y) {int t。 t = x。 x = y。 y = t。} // 交換函數(shù) void selsort(int[],int amp。,int amp。)。 // 選擇排序 void insort(int[],int amp。,int amp。)。 // 插入排序 void bubsort(int[],int amp。,int amp。)。 // 冒泡排序 void quicksort(int[],int,int,int amp。,int amp。)。 // 快速排序 int printfTime()。 // 獲取時(shí)間 void shells
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1