【正文】 { array[tmp].next = front[i]。 tmp = trail[i]。 } } array[tmp].next = 0。}//基數(shù)排序主函數(shù)void RadixSort(int keyNum){ //從個(gè)位一直到最高位進(jìn)行分配和收集 for(int i = keyNum1 。 i = 0 。 i) { Distribute(i)。 Collect()。 }}v 調(diào)試分析216。 直接插入排序輸入數(shù)據(jù)：49，38，65，97，76，13，27，49正確結(jié)果：13，27，38，49，49，65，76，97本算法時(shí)間復(fù)雜度為：O(n^2)運(yùn)行結(jié)果：216。 折半插入排序輸入數(shù)據(jù)：49，38，65，97，76，13，27，49正確結(jié)果：13，27，38，49，49，65，76，97本算法時(shí)間復(fù)雜度：O(n^2)運(yùn)行結(jié)果：216。 希爾排序輸入數(shù)據(jù)：49，38，65，97，76，13，27，49，55，04正確結(jié)果：4，13，27，38，49，49，55，65，76，97時(shí)間復(fù)雜度：O(n^(3/2))運(yùn)行結(jié)果：216。 冒泡排序輸入數(shù)據(jù)：49，38，65，97，76，13，27，49正確結(jié)果：13，27，38，49，49，65，76，97時(shí)間復(fù)雜度：O(n^2)運(yùn)行結(jié)果：216。 快速排序輸入數(shù)據(jù)：49，38，65，97，76，13，27，49正確結(jié)果：13，27，38，49，49，65，76，97時(shí)間復(fù)雜度：O(nlogn)運(yùn)行結(jié)果：216。 直接選擇排序輸入數(shù)據(jù)：49，38，65，97，76，13，27，49正確結(jié)果：13，27，38，49，49，65，76，97時(shí)間復(fù)雜度：O(n^2)運(yùn)行結(jié)果：216。 堆排序輸入數(shù)據(jù)：4，1，3，2，16，9，10，14，8，7正確結(jié)果：1，2，3，4，7，8，9，10，14，16時(shí)間復(fù)雜度：O(nlogn)運(yùn)行結(jié)果：216。 歸并排序輸入數(shù)據(jù)：49 38 65 97 76 13 27正確結(jié)果：13 27 38 49 65 76 97時(shí)間復(fù)雜度：O(nlogn)運(yùn)行結(jié)果：調(diào)試問(wèn)題思考和算法改進(jìn)： 由于在歸并排序主函數(shù)中用了3個(gè)數(shù)組arySource，aryResult，aryTmp，開始的時(shí)候aryTmp定義成全局變量結(jié)果程序老是運(yùn)行錯(cuò)誤，最后在每次遞歸調(diào)的用排序主函數(shù)本身時(shí)重新定義aryTmp，這樣問(wèn)題就解決了，因?yàn)槿謅ryTmp在遞歸調(diào)用的時(shí)候會(huì)把前面的結(jié)果覆蓋掉。但是如果在數(shù)據(jù)量小的時(shí)候這樣做還是可行的，如果一旦數(shù)據(jù)量非常大了遞歸調(diào)用會(huì)非常的耗時(shí)，而且每次遞歸調(diào)用都要臨時(shí)開一個(gè)數(shù)組aryTmp這樣非常浪費(fèi)空間，一個(gè)好的改進(jìn)思路就是把這個(gè)遞歸的算法該為非遞歸的。216。 基數(shù)排序輸入數(shù)據(jù)：278，109，063，930，589，184，505，269，008，083正確結(jié)果：008，063，083，109，184，269，278，505，589，930時(shí)間復(fù)雜度： 對(duì)于n個(gè)數(shù)據(jù)元素（假設(shè)每個(gè)數(shù)據(jù)元素含d個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字的取值范圍為rd個(gè)值）進(jìn)行基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+rd))，其中每一趟分配的時(shí)間復(fù)雜度為O(n)，每一趟收集的時(shí)間復(fù)雜度為O(rd)，整個(gè)排序需進(jìn)行d趟分配和收集。運(yùn)行結(jié)果：v 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)216。 課程設(shè)計(jì)的收獲 通過(guò)本次課程設(shè)計(jì)，我再次復(fù)習(xí)并掌握了各種排序算法，深刻的理解了數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的重要地位。學(xué)會(huì)了通過(guò)各種方法解決學(xué)習(xí)中遇到的問(wèn)題，懂得了與人合作的真諦，合作才能提高效率才能共贏。 通過(guò)這次課程設(shè)計(jì)我初步理解了C/C++語(yǔ)言中排序庫(kù)函數(shù)的實(shí)現(xiàn)方法，它并不是傳說(shuō)中的那么神秘，它也是封裝了最基本的排序算法，然后提供一個(gè)接口給程序員調(diào)用。 通過(guò)本次課程設(shè)計(jì)還讓我認(rèn)識(shí)到了，要想編寫一個(gè)高效率的算法學(xué)好數(shù)據(jù)結(jié)構(gòu)真的很重要。216。 遇到的問(wèn)題及解決思路 在編寫程序的時(shí)候總是犯一些低級(jí)的錯(cuò)誤，比如將“==”寫成了“=”，然后程序老是出錯(cuò)，可是自己認(rèn)真的想一下思路覺(jué)得沒(méi)有問(wèn)題，當(dāng)別人檢查的時(shí)候一眼就瞧出來(lái)了。像這種情況就只有把常量放在左邊，這樣在編譯的時(shí)候都通不過(guò)，可直接通過(guò)編譯器查出。 比如我在寫歸并排序的時(shí)候，程序偽代碼上直接寫的三個(gè)數(shù)組，但是沒(méi)有說(shuō)數(shù)組是定義的全局變量還是局部變量，而我初步看了偽代碼之后就按照自己的思路寫，可是老是得不到結(jié)果，最后調(diào)試了半天才發(fā)現(xiàn)在Merge函數(shù)里面ary1的值和ary2的值相等，此時(shí)我才恍然大悟，由于是遞歸調(diào)用，這樣的話最后傳的參數(shù)ary1和ary2的值就是aryTmp。此時(shí)只要把a(bǔ)ryTmp定義成局部變量就可以了。216。 對(duì)數(shù)據(jù)結(jié)構(gòu)課程的思考 數(shù)據(jù)結(jié)構(gòu)課程對(duì)計(jì)算機(jī)專業(yè)來(lái)說(shuō)是核心課程了，如果沒(méi)有學(xué)數(shù)據(jù)結(jié)構(gòu)那么在面對(duì)問(wèn)題時(shí)，就很難想到好的解決思路。但是數(shù)據(jù)結(jié)構(gòu)書上講的算法有時(shí)很晦澀，難懂，有時(shí)一個(gè)重要的步驟一句偽代碼就解決了但是實(shí)際編程時(shí)卻不好解決。有時(shí)只講一個(gè)算法的實(shí)現(xiàn)卻不講它的應(yīng)用，讓人感覺(jué)學(xué)了沒(méi)啥用處。 不過(guò)總的來(lái)講學(xué)了數(shù)據(jù)結(jié)構(gòu)后，我的編程能力和閱讀他人代碼的能力有了很大的提高。我想數(shù)據(jù)結(jié)構(gòu)這門課程雖然結(jié)束了，但真正學(xué)習(xí)它才剛剛開始……v 參考文獻(xiàn)《算法導(dǎo)論》原書第二版，Thomas Charles Ronald Clifford Stein 著，潘金貴 顧鐵成 李成法 葉懋 譯，機(jī)械工業(yè)出版社《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》嚴(yán)蔚敏 吳偉民 著， 清華大學(xué)出版社第 32 頁(yè) 共 33 頁(yè)