守望者的理想及其象征

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

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

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

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

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