守望者的理想及其象征

1、需求報(bào)告排序?qū)嵺`小組成員:0209040104 邱瑤隹麗麗 雒文杰 云楠 曹德仲02090401060209040107020904011202090401230209040124程序功能本程序用以下幾種內(nèi)部排序算法：插入排序（直插，折半插入，2-路插入,表插），希爾排序，起泡排序，快速排序，選擇排序（簡(jiǎn)單選擇排序和樹(shù)形選擇 排序），堆排序，歸并排序，實(shí)現(xiàn)利用隨機(jī)函數(shù)產(chǎn)生 30000個(gè)隨機(jī)整數(shù)，并統(tǒng)計(jì) 以上各種算法的上機(jī)花費(fèi)時(shí)間。實(shí)現(xiàn)方法采取用戶與計(jì)算機(jī)直接對(duì)話的方式執(zhí)行， 在計(jì)算機(jī)終端顯示“提示信息”下, 用戶輸入隨機(jī)整數(shù)，并選擇一種排序方法，排序后進(jìn)行時(shí)間復(fù)雜度計(jì)算，比較得 出最優(yōu)排序方法

2、。直接插入排序：在含有i-1個(gè)記錄的有序子序列r1.i-1中插入一個(gè)記錄ri，變成含有i個(gè)記錄的有序子序列r1.i, 在r0處設(shè)置監(jiān)視哨。先將序 列中的第一個(gè)記錄看成一個(gè)有序的子序列，然后從第二個(gè)記錄起，逐個(gè)進(jìn)行插 入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止。折半插入排序：用“折半查找”來(lái)實(shí)現(xiàn)查找操作。2-路插入排序：設(shè)一個(gè)和l.r同類型的數(shù)組d，首先將L.r1賦值給d1，并 將d1看成是在排好序的序列中處于中間位置的記錄，然后從 L.r中第二個(gè)記錄 起，依次插入到d1之前或之后的有序序列中。先將待插記錄的關(guān)鍵字和 d1的關(guān)鍵字進(jìn)行比較，若L.ri.key<d1.key,則將L.ri

3、插入到d1之前的有序表中。反之則將L.ri插入到d1之后的有序表中。在實(shí)現(xiàn)算法時(shí)，可將 d看成 是一個(gè)循環(huán)向量，并設(shè)兩個(gè)指針first和fin al ，分別指示排序過(guò)程中得到的有序 序列中第一個(gè)記錄和最后一個(gè)記錄在 d中的位置。表插入排序：首先將靜態(tài)鏈表中數(shù)組下標(biāo)為“ 1”的分量(結(jié)點(diǎn))和表頭結(jié)點(diǎn) 構(gòu)成一個(gè)循環(huán)鏈表。然后依次將下標(biāo)為“ 2”至“n”的分量(結(jié)點(diǎn))按記錄關(guān)鍵 字非遞減有序插入到循環(huán)鏈表中，對(duì)記錄進(jìn)行重新排列，順序掃描有序鏈表，將鏈表中第i個(gè)結(jié)點(diǎn)移動(dòng)到數(shù)組的第i個(gè)分量中。希爾排序：將整個(gè)待排序列分割成若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，再對(duì)全體記錄進(jìn)行一

4、次直接插入排序。起泡排序：第i趟起泡排序是從L.r1至到L.rn-i+1依次比較相鄰兩個(gè)記錄 的關(guān)鍵字，并在“逆序”時(shí)交換相鄰記錄，其結(jié)果是在n-i+1個(gè)記錄中關(guān)鍵字最大的記錄被交換到第n-i+1的位置上，整個(gè)排序過(guò)程需進(jìn)行k (1<=k<n)趟起泡排 序，判別起泡排序結(jié)束的條件應(yīng)該是“在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作”?？炫牛和ㄟ^(guò)一趟排序?qū)⒂涗浄指畛瑟?dú)立的兩部分， 其中一部分記錄的關(guān)鍵字 均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序， 以達(dá)到 整個(gè)序列有序。簡(jiǎn)單選擇排序：通過(guò)n-i次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最 小的記錄，并和的i(1

5、<=i<n)個(gè)記錄交換之，如此重復(fù)，直到排序結(jié)束。樹(shù)形選擇排序：首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在其中n/2 個(gè)較小比較者之間再進(jìn)行兩兩比較，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。堆排序：是記錄序列按關(guān)鍵字非遞減有序排列，則在堆排序的算法中先建一個(gè)“大頂堆”，技先選得一個(gè)關(guān)鍵字最大得為最大的記錄并與序列中最后一個(gè)記 錄交換，然后對(duì)序列中前n-1個(gè)記錄進(jìn)行篩選，重新將它調(diào)整為一個(gè)“大頂堆”， 如此反復(fù)，知道排序結(jié)束。歸并排序：假設(shè)初始序列含有n個(gè)記錄，則可看成是n個(gè)有序的子序列，每個(gè) 子序列的長(zhǎng)度是1,然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2或1的有序子序列，再兩 兩歸并，如此重復(fù)，直到得到一個(gè)長(zhǎng)度為 n的有序序列為止。四設(shè)計(jì)思路:快排歸并起泡選擇插入希爾堆排直插二路折半表插簡(jiǎn)單樹(shù)形Break輸出結(jié)果退出主程序結(jié)束五數(shù)據(jù)來(lái)源:用隨機(jī)函數(shù)產(chǎn)生30000個(gè)隨機(jī)整數(shù)。六模塊分配:邱瑤：希爾排序，歸并排序郭 凱：直接插入排序，2-路插入排序 崔麗麗：折半插入排序，表插入排序 雒文杰：簡(jiǎn)單選擇排序，樹(shù)形選擇排序 云 楠：快排，界面及主程序設(shè)計(jì) 曹德仲：起泡排序，堆排序七.總結(jié)：通過(guò)小組成員一起對(duì)此課程設(shè)計(jì)題目的分析、 討論、及分工，使我們明確了 題目的要求，確立了思路及大概實(shí)現(xiàn)過(guò)程。