版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、各種排序算法總結(jié)排序算法是最基本最常用的算法,不同的排序算法在不同的場景或應(yīng)用中會有不同的表現(xiàn),我們需要對各種排序算法熟練才能將它們應(yīng)用到實(shí)際當(dāng)中,才能更好地發(fā)揮它們的優(yōu)勢。今天,來總結(jié)下各種排序算法。下面這個表格總結(jié)了各種排序算法的復(fù)雜度與穩(wěn)定性:各種排序算法復(fù)雜度比較.png冒泡排序冒泡排序可謂是最經(jīng)典的排序算法了,它是基于比較的排序算法,時間復(fù)雜度為O(n2),其優(yōu)點(diǎn)是實(shí)現(xiàn)簡單,n較小時性能較好。· 算法原理相鄰的數(shù)據(jù)進(jìn)行兩兩比較,小數(shù)放在前面,大數(shù)放在后面,這樣一趟下來,最小的數(shù)就被排在了第一位,第二趟也是如此,如此類推,直到所有的數(shù)據(jù)排序完成· c+代碼實(shí)現(xiàn)1.
2、void bubble_sort(int arr, int len) 2. 3. for (int i = 0; i < len - 1; i+) 4. 5.
3、; for (int j = len - 1; j >= i; j-) 6. 7. if (arrj < arrj -
4、;1) 8. 9. int temp = arrj; 10.
5、0; arrj = arrj - 1; 11. arrj - 1 = temp; 12.
6、160; 13. 14. 15. 選擇排序· 算法原理先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推,直到所有元素均排序完畢。 · c+代碼實(shí)現(xiàn)1. void
7、 select_sort(int arr, int len) 2. 3. for (int i = 0; i < len; i+) 4. 5.
8、;int index = i; 6. for (int j = i + 1; j < len; j+) 7. 8.
9、160; if (arrj < arrindex) 9. index = j; 10. 11.
10、 if (index != i) 12. 13. int temp = arri; 14.
11、0; arri = arrindex; 15. arrindex = temp; 16.
12、0; 17. 18. 插入排序· 算法原理將數(shù)據(jù)分為兩部分,有序部分與無序部分,一開始有序部分包含第1個元素,依次將無序的元素插入到有序部分,直到所有元素有序。插入排序又分為直接插入排序、二分插入排序、鏈表插入等,這里只討論直接插入排序。它是穩(wěn)定的排序算法,時間復(fù)雜度為O(n2) · c+代碼實(shí)現(xiàn)1. void insert_sort(int arr, int len) 2.
13、0; 3. for (int i = 1; i < len; i +) 4. 5. int j = i - 1; 6.
14、160; int k = arri; 7. while (j > -1 && k < arrj ) 8. 9
15、. arrj + 1 = arrj; 10. j -; 11.
16、;12. arrj + 1 = k; 13. 14. 快速排序· 算法原理快速排序是目前在實(shí)踐中非常高效的一種排序算法,它不是穩(wěn)定的排序算法,平均時間復(fù)雜度為O(nlogn),最差情況下復(fù)雜度為O(n2)。它的基本思想是:通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部
17、分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個排序過程可以遞歸進(jìn)行,以此達(dá)到整個數(shù)據(jù)變成有序序列。 · c+代碼實(shí)現(xiàn)1. void quick_sort(int arr, int left, int right) 2. 3. if (left < right) 4. 5. int i
18、= left, j = right, target = arrleft; 6. while (i < j) 7. 8. while (i < j &am
19、p;& arrj > target) 9. j-; 10. if (i < j) 11.
20、160; arri+ = arrj; 12. 13. while (i < j && arri < target) 14.
21、160;i+; 15. if (i < j) 16. arrj = arri; 17. 18.
22、; arri = target; 19. quick_sort(arr, left, i - 1); 20. quick_sort(arr, i + 1, right); 21. 22. 歸并排序· 算法原理歸并排序具體工作原理如下(假設(shè)序列共有
23、n個元素):o 將序列每相鄰兩個數(shù)字進(jìn)行歸并操作(merge),形成floor(n/2)個序列,排序后每個序列包含兩個元素 o 將上述序列再次歸并,形成floor(n/4)個序列,每個序列包含四個元素 o 重復(fù)步驟2,直到所有元素排序完畢歸并排序是穩(wěn)定的排序算法,其時間復(fù)雜度為O(nlogn),如果是使用鏈表的實(shí)現(xiàn)的話,空間復(fù)雜度可以達(dá)到O(1),但如果是使用數(shù)組來存儲數(shù)據(jù)的話,在歸并的過程中,需要臨時空間來存儲歸并好的數(shù)據(jù),所以空間復(fù)雜度為O(n)· c+代碼實(shí)現(xiàn)1. void merge(int arr, int temp_arr,
24、0;int start_index, int mid_index, int end_index) 2. 3. int i = start_index, j = mid_index + 1; 4. int k = 0; 5.
25、60; while (i < mid_index + 1 && j < end_index + 1) 6. 7. if (arri > arrj) 8. &
26、#160; temp_arrk+ = arrj+; 9. else 10. temp_arrk+ = arri+; 11.
27、 12. while (i < mid_index + 1) 13. 14. temp_arrk+ = arri+; 15. 16.
28、 while (j < end_index + 1) 17. temp_arrk+ = arrj+; 18. 19. for (i = 0, j = start_index; j < end_index +&
29、#160;1; i +, j +) 20. arrj = temp_arri; 21. 22. 23. void merge_sort(int arr, int temp_arr, int start_index, int end_index) 24.
30、0;25. if (start_index < end_index) 26. 27. int mid_index = (start_index + end_index) / 2; 28.
31、; merge_sort(arr, temp_arr, start_index, mid_index); 29. merge_sort(arr, temp_arr, mid_index + 1, end_index); 30.
32、;merge(arr, temp_arr, start_index, mid_index, end_index); 31. 32. 堆排序二叉堆二叉堆是完全二叉樹或者近似完全二叉樹,滿足兩個特性· 父結(jié)點(diǎn)的鍵值總是大于或等于(小于或等于)任何一個子節(jié)點(diǎn)的鍵值 · 每個結(jié)點(diǎn)的左子樹和右子樹都是一個二叉堆 當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個子節(jié)點(diǎn)的鍵值時為最大堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于任何一個子節(jié)點(diǎn)的鍵值時為最小堆。一般二叉樹
33、簡稱為堆。堆的存儲一般都是數(shù)組來存儲堆,i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i 1) / 2。它的左右子結(jié)點(diǎn)下標(biāo)分別為2 * i + 1和2 * i + 2。如第0個結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為1和2。存儲結(jié)構(gòu)如圖所示:堆結(jié)構(gòu).png 堆排序原理堆排序的時間復(fù)雜度為O(nlogn)· 算法原理(以最大堆為例)o 先將初始數(shù)據(jù)R1.n建成一個最大堆,此堆為初始的無序區(qū) o 再將關(guān)鍵字最大的記錄R1(即堆頂)和無序區(qū)的最后一個記錄Rn交換,由此得到新的無序區(qū)R1.n-1和有序區(qū)Rn,且滿足R1.n-1.keysRn.key o 由于交換后新的根R1可能違反堆性質(zhì),故應(yīng)將當(dāng)前無序區(qū)R1.n-1調(diào)
34、整為堆。 o 重復(fù)2、3步驟,直到無序區(qū)只有一個元素為止。 · c+代碼實(shí)現(xiàn)1. /* 2. * 將數(shù)組arr構(gòu)建大根堆 3. * param arr 待調(diào)整的數(shù)組 4. * param i 待調(diào)整的數(shù)組元素的下標(biāo) 5. * param len 數(shù)組的長度 6. */ 7. void heap_adjust(int arr,
35、 int i, int len) 8. 9. int child; 10. int temp; 11. 12. for (; 2 * i + 1 < len; i = child) 13. &
36、#160; 14. child = 2 * i + 1; / 子結(jié)點(diǎn)的位置 = 2 * 父結(jié)點(diǎn)的位置 + 1 15. / 得到子結(jié)點(diǎn)中鍵值較大的結(jié)點(diǎn) 16.
37、; if (child < len - 1 && arrchild + 1 > arrchild) 17. child +; 18. /
38、;如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動,替換它的父結(jié)點(diǎn) 19. if (arri < arrchild) 20. 21. temp = arri; 2
39、2. arri = arrchild; 23. arrchild = temp; 24. 25. else 26. break; 27. 28. 29. 30. /* 31. * 堆排序算法 32. */ 33. void hea
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年度貴州省安全員之B證(項(xiàng)目負(fù)責(zé)人)模擬試題(含答案)
- 2024年度甘肅省安全員之B證(項(xiàng)目負(fù)責(zé)人)考前沖刺試卷B卷含答案
- -業(yè)務(wù)藍(lán)圖設(shè)計(jì)報(bào)告-(CRM分冊)-V0
- 2024年云數(shù)融合項(xiàng)目建議書
- 2024年激光轉(zhuǎn)速測量儀項(xiàng)目建議書
- 2024年鍋爐爐膛安全監(jiān)控裝置項(xiàng)目合作計(jì)劃書
- 2024年電調(diào)收音機(jī)項(xiàng)目建議書
- 2024年運(yùn)載火箭控制系統(tǒng)單元檢測設(shè)備項(xiàng)目合作計(jì)劃書
- 科研所實(shí)驗(yàn)室建設(shè)運(yùn)輸合同
- 藥品恒溫運(yùn)輸協(xié)議
- 車間安全管理考核細(xì)則范文
- 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)(第3版)PPT完整全套教學(xué)課件
- 中班健康《身體上的洞洞》課件
- 函數(shù)的單調(diào)性與最值-完整課件
- 幼兒園大班科學(xué)《奇妙的信》課件
- 華為BEM戰(zhàn)略解碼體系完整版
- 學(xué)校食堂開放日制度三篇
- 安全教育讀本(高中生版)
- 預(yù)防意外傷害安全教案8篇
- ERP 用友U8基礎(chǔ)設(shè)置
- 【基于杜邦分析的企業(yè)財(cái)務(wù)現(xiàn)狀探究國內(nèi)外文獻(xiàn)綜述5200字】
評論
0/150
提交評論