單獨實現(xiàn)各種排序課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：33 大?。?.22MB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩32頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構課程設計設計報告　　課程設計題目　　單獨實現(xiàn)各種排序 　　2013 年 5 月 4 日　　目錄　　?

2、目錄1　　? 需求分析3　　? 概要設計4　　? 直接插入排序的設計思路4　　? 折半插入排序的設計思路4　　? 希爾排序

3、的設計思路5　　? 冒泡排序設計思路5　　? 快速排序設計思路5　　? 直接選擇排序的設計思路6　　? 堆排序的設計思路6　　? 歸并排序的設計思路8　　? 基數排序的設計思路

4、9　　? 詳細設計11　　? 直接插入排序11　　? 折半插入排序12　　? 希爾排序13　　? 冒泡排序15</b&

5、gt;　　? 快速排序16　　? 直接選擇排序17　　? 堆排序18　　? 歸并排序20

6、　? 基數排序22　　? 調試分析25　　? 直接插入排序25　　? 折半插入排序26　　? 希爾排序27

7、　　? 冒泡排序27　　? 快速排序28　　? 直接選擇排序28　　? 堆排序29　　? 歸并排序29&

8、lt;p>　　? 基數排序30　　? 數據結構課程設計總結31　　? 課程設計的收獲31　　? 遇到的問題及解決思路32　　? 對數據結構課程的思考32　　?

9、參考文獻33　　需求分析　　排序時計算機程序設計中一種重要的操作，它的功能將包含多個數據元素的任意序列，重新排列成一個按關鍵字有序的序列。　　由于待排序的元素數量不同，使得排序過程中的時空開銷也不同。沒有一種排序算法可以適合任何一種場合，每種排序算法都

10、有適合的特殊環(huán)境，只有在這種特殊環(huán)境中才能發(fā)揮這種排序算法的優(yōu)勢。　　排序在很多的場合都會用到，一個優(yōu)秀的排序算法可以使程序的運行效率提高，節(jié)約時空資源。　　其中對整數或者是實數的排序用得最多，大多數情況下都是要求對一組無序的數據按照數據值的大小以增序或者以降序排列數據。　　例如對一組學生的成績從高到低排序，以確

11、定學生的名次。又如要求對員工的工資排序，以方便管理。在現(xiàn)實生活中要用到排序的地方不勝枚舉，雖然很多高級程序設計語言都封裝了排序的算法，用來也方便，程序員也容易掌握和運用，但是這些封裝好了的排序算法將會一成不變的按照設計者當初設計時設計的步驟工作，無法在實際情況中進行優(yōu)化，也就不以利于提高程序的總體效率，所以根據實際的情況編寫實際的排序算法才是可行的。　　本次課程設計單獨實現(xiàn)直接插入排序、折半插入

12、排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序、基數排序。　　概要設計　　直接插入排序的設計思路　　直接插入排序是一種最簡單的排序方法，他的基本操作是將一個數據元素直接插入到已排好序的一組數據中，從而得到一個新的元素數加一的有序表。

13、　　由于數據存儲結構采用的是數組，所以插入一個元素就涉及到查找待插入元素的位置，移動其他元素，而數組頭一個結點設為哨兵結點。　　如圖1所示：在序列1，3，5，8中插入4　　圖1　　這樣就有完成了一次插入，重復這種操作直到整個數組有序為止。

14、　　折半插入排序的設計思路　　折半插入排序是在直接插入排序的基礎上減少了比較和移動的次數從而提高算法的效率，因為待插入數據前面的所有數據已經有序了。　　先用兩個指針low和high通過折半查找的方法確定待插入數據的位置，最后low所指向的位置即為待插入數據的位置，先將把待查入數據放到0號單元然后low以后的單元依次后移一位然后將0號

15、單元的數據插入到low指向的單元中，重復這個操作直到整個數組有序。　　希爾排序的設計思路　　希爾排序的設計思想是：先將整個待排序數列分割成若干子序列，對子序列分別進行直接插入排序，待整個序列基本有序時再對整個數列進行一次直接插入排序。　　冒泡排序設計思路&l

16、t;/b>　　冒泡排序很簡單，首先將第一個數據的關鍵字和第二個數據的關鍵字比較，若為逆序，則將兩個數據交換，然后比較第二個和第三個數據的關鍵字，以此類推，直到第n-1個數據和第n個數據進行比較。然后重復上述操作，第i次循環(huán)只進行到第n-i個為止，因為n-i以后的數據已經有序了。　　快速排序設計思路</p&

17、gt;　　快速排序是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分關鍵字均比另一部分關鍵字小，然后分別對這兩部分繼續(xù)排序直到整個有序。　　如圖2所示：　　第一次找到3的位置3和6交換，1和4交換；　　第二次找

18、到1的位置1和2交換，6的位置不變；　　第三次找到4的位置4和5交換，至此整個序列有序。　　圖2　　直接選擇排序的設計思路　　一趟直接選擇排序的操作為：通過n-i次關鍵字間的比較，從n-i+1個數據中選出關鍵字最小的數據，并和第i個數

19、據交換，重復n-1次就得到了一個有序的序列。　　堆排序的設計思路　　堆排序只需要一個數組就可以了，每個數據占一個存儲空間。堆的定義如下：對n個元素的序列{K1，K2，……，Kn}當且僅當滿足下列關系時稱之為堆：　　Ki<=K2i&&Ki<=K2i+

20、1 或者 K2i<=Ki&&K2i+1<=Ki　　前者稱為最小堆，后者稱為最大堆。　　如圖3所示：對序列8 ， 1 ， 7 ， 4， 5 ，3建堆　　如圖4.1-4.5所示排序過程：最終為1，3，4，5，7，8　　圖3圖4.1

21、　　圖4.2 圖4.3　　圖4.4圖4.5　　歸并排序的設計思路　　假設初始序列為n個數據元素，則可以看成是n個有序的子序列，每個子序列的長度

22、為1，然后兩兩歸并，得到n/2個長度為2或者為1的有序子序列，然后再兩兩歸并……直到得到一個長度為n的有序序列為止。　　這種排序稱為2路歸并排序。2路歸并排序的核心操作就是將兩個有序序列歸并為一個有序序列。　　如圖5所示：　　圖5<

23、/p>　　原始序列為4，1，5，3，2。　　第一趟排序后將4，1合并，5，3合并后為1，4，3，5，2　　第二趟合并后將1，4和3，5合并后為1，3，4，5，2　　第三趟合并后將1，3，4，5和2合并為1，2，3，4，5。

24、基數排序的設計思路　　基數排序是借助“分配”和“收集”兩種操作對單邏輯關鍵字進行排序。　　例如關鍵字k是數字且在0到999之間，則可以把每個十進制數字看成一個關鍵字，k由3個關鍵字（k1，k2，k3）組成，分別對應k的百位，十位，個位數字。所以如果有一個這樣的數字序列，從低位關鍵字起按關鍵字的不同值將數據元素分配到0~9標記的隊列中然

25、后在收集，如此重復3次即可。　　基數的“基”就是每個關鍵字的取值范圍，這里是10。　　假設每個關鍵字ki在[0，2]之間，則有三個隊列。　　有序列：002，202，011，210，001，101　　則排序過程如圖6.1~6.3所示：

26、;　　圖6.1　　第一趟排序之后的序列為：（以個位數字為關鍵字）　　210，011，001，101，002，202　　圖6.2　　第二趟排序之后序列為：（以十位數字為關鍵字）

27、　　001，101，002，202，210，011　　圖6.3　　第三趟排序之后序列為：（以百位數字為關鍵字）　　001，002，011，101，202，210　　詳細設計&l

28、t;/p>　　直接插入排序　　int * array代表待排序的數組，length代表待排序數組的長度，array[0]設為監(jiān)視哨。　　void InsertSort(int * array , int length)　　{<

29、;/b>　　for(int i = 2 ; i <= length ; i++)　　{　　if(array[i] < array[i-1])　　{<

30、p>　　array[0] = array[i];　　array[i] = array[i-1];　　int j;　　//查找合適的位置并移動數據　　for(j = i-2 ; array[0] < array[j] ; j

31、--)　　array[j+1] = array[j];　　//在合適的位置插入數據　　array[j+1] = array[0];　　}　　}</p

32、>　　}　　折半插入排序　　int * array代表待排序的數組，length代表待排序數組的長度　　void BInsertSort(int * array , int length)

33、　　{　　for(int i = 2 ; i <= length ; i++)　　{　　array[0] = array[i];　　int low = 1 , high

34、= i-1;　　//折半查找插入的合適的位置　　while(low <= high)　　{　　int mid = (low+high)/2;　　if(array[0] < arra

35、y[mid])　　high = mid-1;　　else　　low = mid+1;　　}　　//將low到i-1的數據向后移動一位

36、　　for(int j = i-1 ; j >= low ; j--)　　array[j+1] = array[j];　　//low的位置即array[0]的正確位置　　array[low] = array[0];　　}<

37、/b>　　}　　希爾排序　　int * array代表待排序的數組，length代表待排序數組的長度，increment代表增量　　void ShellInsert(int * array

38、, int length , int increment)　　{　　//間隔為增量的子序列使用直接插入排序　　for(int i = increment+1 ; i <= length ; i++)　　{&l

39、t;/b>　　if(array[i] < array[i-increment])　　{　　array[0] = array[i];　　int j;<p&g

40、t;　　for(j = i-increment ; j > 0 && array[0] < array[j] ;　　j -= increment)　　array[j+increment] = array[j];　　array[j+increment] = array[0];</p

41、>　　}　　}　　}　　//希爾排序主函數　　void ShellSort(int *arr

42、ay , int length)　　{　　//增量　　int increment = length/2;　　while(increment>=1)&

43、lt;b>　　{　　ShellInsert(array , length , increment);　　//逐步減小增量直至為1　　increment /= 2;　　}

44、;　　}　　冒泡排序　　int * array代表待排序的數組，length代表待排序數組的長度　　void BubbleSort(int * array , int length)<b&g

45、t;　　{　　for(int i = length , change = true; i > 1 && change ; i--)　　{　　change = false;　　for(int j

46、 = 1 ; j 　　{　　if(array[j]>array[j+1])　　{　　change = true;　　swa

47、p(array[j] , array[j+1]);　　}　　}　　}　　}&l

48、t;b>　　快速排序　　int * array代表待排序的數組，length代表待排序數組的長度，將p到r之間比array[r]小的數據已到array[r]前，比array[r]大的移到后面，并返回array[r]的正確位置。　　int Partition(int * array , int p , int r)</p&g

49、t;　　{　　int x = array[r];　　//下標小于等于i的數據都比x小，否則比x大　　int i = p-1;　　for(int j = p ; j < r ; j++)

50、　　{　　if(array[j] <= x)　　{　　i++;　　swap(array[i] , array[j]);</p&

51、gt;　　}　　}　　swap(array[i+1] , array[r]);　　//返回第一個比x大的位置，即arrray[r]的合適位置　　return i+1;<

52、/p>　　}　　//快速排序主函數　　void QuickSort(int * array , int p , int r)　　{

53、　　if(p < r)　　{　　int q = Partition(array , p , r);　　QuickSort(array , p , q-1);　　QuickSort(array

54、 , q+1 , r);　　}　　}　　直接選擇排序　　int * array代表待排序的數組，length代表待排序數組的長度，找到從bgn到length之

55、間最小的數據的位置　　int SelectMinKey(int * array , int length , int bgn)　　{　　int min = array[bgn] , j = bgn;　　for(int i = bgn+

56、1 ; i <= length ; i++)　　{　　if(min > array[i])　　{　　min = array[i];<b&

57、gt;　　j = i;　　}　　}　　return j;　　}<p&g

58、t;　　//選擇排序主函數　　void SelectSort(int * array , int length)　　{　　for(int i = 1 ; i < length ; i++)&

59、lt;b>　　{　　int j = SelectMinKey(array , length , i);　　//將最小的數據交換到位置i　　if(i != j) swap(array[i] , array[j]);　　}</

60、b>　　}　　堆排序　　int * array代表待排序的數組，heapLength代表堆的長度，i代表第i個結點，保持最大堆的性質　　void MaxHeapify(int * array

61、 , int heapLength , int i)　　{　　int l = i*2;　　int r = i*2+1;　　//父結點和左右兒子中最大值的位置　　int largest;<

62、/p>　　if(l <= heapLength && array[l] > array[i])　　largest = l;　　else　　largest = i;　　if(r &

63、lt;= heapLength && array[largest] < array[r])　　largest = r;　　//將最大值放到父結點，并繼續(xù)往下調整　　if(largest != i)　　{</

64、p>　　swap(array[i] , array[largest]);　　MaxHeapify(array , heapLength , largest);　　}　　}

65、;　　//建堆　　void BuildMaxHeap(int * array , int heapLength)　　{　　for(int i = heapLength/2 ; i >= 1 ; i--)<

66、;p>　　MaxHeapify(array , heapLength , i);　　}　　//堆排序主函數　　void HeapSort(int * array , int length)&

67、lt;b>　　{　　BuildMaxHeap(array , length);　　int heapLength = length;　　for(int i = length ; i >= 2 ; i--)　　{</b&

68、gt;　　//將堆頂的數據和堆最后個數據交換，堆頂的數據最大　　swap(array[1] , array[heapLength]);　　//堆的大小減一　　heapLength--;　　//

69、調整堆使之始終滿足最大堆的性質　　MaxHeapify(array , heapLength ,1);　　}　　}　　歸并排序<

70、p>　　將有序的ary1[i...m]和ary1[m+1,n]合并為有序的ary2[i...n]　　void Merge(int * ary1 , int * ary2 , int i , int m , int n)　　{　　int j , k;

71、　　for(j = m+1 , k = i ; i <= m && j <= n ; k++)　　{　　if(ary1[i] < ary1[j])　　ary2[k] = ary1[i++];<

72、p>　　else　　ary2[k] = ary1[j++];　　}　　if(i <= m)　　{　　fo

73、r(; i <= m ; i++)　　ary2[k++] = ary1[i];　　}　　if(j <= n)　　{　　for(; j <

74、= n ; j++)　　ary2[k++] = ary1[j];　　}　　}　　//將arySource[s...t]歸并為有序的aryResult[s...t]<p

75、>　　void MergeSort(int * arySource , int * aryResult , int s , int t)　　{　　if(s == t)　　{　　aryResu

76、lt[s] = arySource[s];　　}　　else　　{　　int m = (s+t)/2 , aryTmp[9];<

77、;p>　　//將arySource[s...m]歸并為有序的aryTmp[s...m]　　MergeSort(arySource , aryTmp , s , m);　　//將arySource[m+1...t]歸并為有序的aryTmp[m+1...t]　　MergeSort(arySource , ary

78、Tmp , m+1 , t);　　//將aryTmp[s...m]，aryTmp[m+1...t]歸并為有序的aryResult[s...t]　　Merge(aryTmp , aryResult , s , m , t);　　}<

79、;b>　　}　　基數排序　　元素的存儲結構，為方便計算將關鍵值設為string類型　　struct Data　　{　　strin

80、g key;//數據的關鍵字　　int next;//下一個數據的位置　　} array[12];　　//每個隊列的頭指針和為指針　　int front[10] , trail[10];　　//創(chuàng)建靜態(tài)鏈表<

81、;/b>　　void CreateLinkList(string key , int index , int pre)　　{　　array[pre].next = index;　　array[index].key = key;&

82、lt;/p>　　array[index].next = 0;　　}　　//獲得數據的第i位數（將字符變?yōu)檎麛担?lt;/p>　　int order(int i , string key)　　{</

83、b>　　return key[i]-'0';　　}　　分配函數，按數據的第i位關鍵字將數據放入相應的隊列中　　void Distribute(int i)

84、;　　{　　memset(front , 0 , sizeof(front));　　for(int p = array[0].next ; p ; p = array[p].next)　　{　　int j = or

85、der(i , array[p].key);　　if(!front[j])　　{　　front[j] = trail[j] = p;　　}

86、;　　else　　{　　array[trail[j]].next = p;　　trail[j] = p;　　}　　}

87、　　}　　收集函數，合并各個隊列中的數據，順序從0號隊列到9號隊列　　void Collect()　　{　　int i = 0;<

88、;/p>　　//找到第一個非空的隊列　　while(i < 10 && !front[i]) i++;　　array[0].next = front[i];　　int tmp = trail[i];　　for(i++; i

89、 < 10 ; i++)　　{　　//合并非空隊列　　if(front[i])　　{　　array[tmp].

90、next = front[i];　　tmp = trail[i];　　}　　}　　array[tmp].next = 0;　　}<

91、/b>　　//基數排序主函數　　void RadixSort(int keyNum)　　{　　//從個位一直到最高位進行分配和收集　　for(int

92、 i = keyNum-1 ; i >= 0 ; i--)　　{　　Distribute(i);　　Collect();　　}

93、}　　調試分析　　直接插入排序　　輸入數據：49，38，65，97，76，13，27，49　　正確結果：13，27，38，49，49，65，76，97&

94、lt;p>　　本算法時間復雜度為：O(n^2)　　運行結果：　　折半插入排序　　輸入數據：49，38，65，97，76，13，27，49　　正確結果：13，27，38，49，49，65，76

95、，97　　本算法時間復雜度：O(n^2)　　運行結果：　　希爾排序　　輸入數據：49，38，65，97，76，13，27，49，55，04　　正確結果：4

96、，13，27，38，49，49，55，65，76，97　　時間復雜度：O(n^(3/2))　　運行結果：　　冒泡排序　　輸入數據：49，38，65，97，76，13，27，49

97、　　正確結果：13，27，38，49，49，65，76，97　　時間復雜度：O(n^2)　　運行結果：　　快速排序　　輸入數據：49，38，65，97，76，13，27，49

98、　　正確結果：13，27，38，49，49，65，76，97　　時間復雜度：O(nlogn)　　運行結果：　　直接選擇排序　　輸入數據：49，38，65，

99、97，76，13，27，49　　正確結果：13，27，38，49，49，65，76，97　　時間復雜度：O(n^2)　　運行結果：　　堆排序　　輸入數據：

100、4，1，3，2，16，9，10，14，8，7　　正確結果：1，2，3，4，7，8，9，10，14，16　　時間復雜度：O(nlogn)　　運行結果：　　歸并排序<p&

101、gt;　　輸入數據：49 38 65 97 76 13 27　　正確結果：13 27 38 49 65 76 97　　時間復雜度：O(nlogn)　　運行結果：　　調試問題思考和算法改進：

102、由于在歸并排序主函數中用了3個數組arySource，aryResult，aryTmp，開始的時候aryTmp定義成全局變量結果程序老是運行錯誤，最后在每次遞歸調的用排序主函數本身時重新定義aryTmp，這樣問題就解決了，因為全局aryTmp在遞歸調用的時候會把前面的結果覆蓋掉。但是如果在數據量小的時候這樣做還是可行的，如果一旦數據量非常大了遞歸調用會非常的耗時，而且每次遞歸調用都要臨時開一個數組aryTmp這樣非常浪費空間，一個好的改

103、進思路就是把這個遞歸的算法該為非遞歸的。　　基數排序　　輸入數據：278，109，063，930，589，184，505，269，008，083　　正確結果：008，063，083，109，184，269，278，505，589，930

104、;　　時間復雜度：　　對于n個數據元素（假設每個數據元素含d個關鍵字，每個關鍵字的取值范圍為rd個值）進行基數排序的時間復雜度為　　O(d(n+rd))，其中每一趟分配的時間復雜度為O(n)，每一趟收集的時間復雜度為O(rd)，整個排序需進行d趟分配和收集。

105、　　運行結果：　　數據結構課程設計總結　　課程設計的收獲　　通過本次課程設計，我再次復習并掌握了各種排序算法，深刻的理解了數據結構在程序設計中的重要地位。學會了通過各種方法解決學習中遇到的問題，懂得了與人合作的真諦，合作才能提高效率才能共贏。</p&

106、gt;　　通過這次課程設計我初步理解了C/C++語言中排序庫函數的實現(xiàn)方法，它并不是傳說中的那么神秘，它也是封裝了最基本的排序算法，然后提供一個接口給程序員調用。　　通過本次課程設計還讓我認識到了，要想編寫一個高效率的算法學好數據結構真的很重要。　　遇到的問題及解決思路　　在編寫程序的時候總

107、是犯一些低級的錯誤，比如將“==”寫成了“=”，然后程序老是出錯，可是自己認真的想一下思路覺得沒有問題，當別人檢查的時候一眼就瞧出來了。像這種情況就只有把常量放在左邊，這樣在編譯的時候都通不過，可直接通過編譯器查出。　　比如我在寫歸并排序的時候，程序偽代碼上直接寫的三個數組，但是沒有說數組是定義的全局變量還是局部變量，而我初步看了偽代碼之后就按照自己的思路寫，可是老是得不到結果，最后調試了半天才

108、發(fā)現(xiàn)在Merge函數里面ary1的值和ary2的值相等，此時我才恍然大悟，由于是遞歸調用，這樣的話最后傳的參數ary1和ary2的值就是aryTmp。此時只要把aryTmp定義成局部變量就可以了。　　對數據結構課程的思考　　數據結構課程對計算機專業(yè)來說是核心課程了，如果沒有學數據結構那么在面對問題時，就很難想到好的解決思路。但是數據結構書上講的算法有時很

109、晦澀，難懂，有時一個重要的步驟一句偽代碼就解決了但是實際編程時卻不好解決。有時只講一個算法的實現(xiàn)卻不講它的應用，讓人感覺學了沒啥用處。　　不過總的來講學了數據結構后，我的編程能力和閱讀他人代碼的能力有了很大的提高。我想數據結構這門課程雖然結束了，但真正學習它才剛剛開始……　　參考文獻<p

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

單獨實現(xiàn)各種排序課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

單獨實現(xiàn)各種排序 課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載

單獨實現(xiàn)各種排序課程設計報告