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