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

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

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

4、次直接插入排序。起泡排序：第i趟起泡排序是從L.r1至到L.rn-i+1依次比較相鄰兩個記錄 的關鍵字，并在“逆序”時交換相鄰記錄，其結果是在n-i+1個記錄中關鍵字最大的記錄被交換到第n-i+1的位置上，整個排序過程需進行k (1<=k<n)趟起泡排 序，判別起泡排序結束的條件應該是“在一趟排序過程中沒有進行過交換記錄的操作”。快排：通過一趟排序將記錄分割成獨立的兩部分， 其中一部分記錄的關鍵字 均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序， 以達到 整個序列有序。簡單選擇排序：通過n-i次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最 小的記錄，并和的i(1

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