1、十大經(jīng)典排序算法十大經(jīng)典排序算法目錄01.Introduction 介紹02.插入排序03.選擇排序04.交換排序05.分治遞歸06.'桶' 排序目錄01.Introduction 介紹02.插入排序03.Introduction 介紹Introduction 介紹Introduction 介紹D關(guān)于穩(wěn)定性E名詞解釋：A分支主題B來(lái)源網(wǎng)絡(luò)：C關(guān)于時(shí)間復(fù)雜度Introduction 介紹D關(guān)于穩(wěn)定性E名詞解釋：A分支Introduction 介紹來(lái)源網(wǎng)絡(luò)：0102/hustcc/JS-Sorting-Algorithmhttps:/sort.hust.cc/Introduct

2、ion 介紹來(lái)源網(wǎng)絡(luò)：0102https:1. 平方階 (O(n2) 排序 各類簡(jiǎn)單排序：直接插入、直接選擇和冒泡排序。3. O(n1+) 排序， 是介于 0 和 1 之間的常數(shù)。希爾排序2. 線性對(duì)數(shù)階 (O(nlog2n) 排序 快速排序、堆排序和歸并排序；4. 線性階 (O(n) 排序 基數(shù)排序，此外還有桶、箱排序。成功Introduction 介紹關(guān)于時(shí)間復(fù)雜度1. 平方階 (O(n2) 排序 各類簡(jiǎn)單排序：直接插入、BCA排序后兩個(gè)相等鍵值的順序和排序之前它們的順序相同穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。I

3、ntroduction 介紹關(guān)于穩(wěn)定性BCA排序后兩個(gè)相等鍵值的順序和排序之前它們的順序相同穩(wěn)定的Introduction 介紹名詞解釋：k：“桶”的個(gè)數(shù)Out-place：占用額外內(nèi)存n：數(shù)據(jù)規(guī)模In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存Introduction 介紹名詞解釋：k：“桶”的個(gè)數(shù)Ou插入排序插入排序3. insertionSort 插入排序011. 算法步驟2. 動(dòng)圖演示023. 代碼實(shí)現(xiàn)03穩(wěn)定性043. insertionSort 插入排序011. 算法步驟1. 將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。2. 從頭到尾依次掃

4、描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）3. insertionSort 插入排序1. 算法步驟1. 將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元3. insertionSort 插入排序2. 動(dòng)圖演示分支主題3. insertionSort 插入排序2. 動(dòng)圖演示分支3. 代碼實(shí)現(xiàn)PythonJavaScriptGoJavaPHP3. insertionSort 插入排序3. 代碼實(shí)現(xiàn)Python3. insertionSort 穩(wěn)定性穩(wěn)定3. insertionSort 插入排序穩(wěn)

5、定性穩(wěn)定3. insertionSort 插入排序4. shellSort 希爾排序01插入排序的一種1. 算法步驟023. 代碼實(shí)現(xiàn)03穩(wěn)定性044. shellSort 希爾排序01插入排序的一種1. 算1. 算法步驟1. 選擇一個(gè)增量序列 t1，t2，tk，其中 ti tj, tk = 1；2. 按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；3. 每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。4. shellSort 希爾排序1. 算法步驟1. 選擇一個(gè)增量序

6、列 t1，t2，tk3. 代碼實(shí)現(xiàn)PythonJavaScriptGoJavaPHP4. shellSort 希爾排序3. 代碼實(shí)現(xiàn)Python4. shellSort 希爾排序穩(wěn)定性不穩(wěn)定4. shellSort 希爾排序穩(wěn)定性不穩(wěn)定4. shellSort 希爾排序選擇排序選擇排序2. selectionSort 選擇排序011. 算法步驟2. 動(dòng)圖演示023. 代碼實(shí)現(xiàn)03穩(wěn)定性042. selectionSort 選擇排序011. 算法步驟1. 算法步驟1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置2. 再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序

7、列的末尾。3. 重復(fù)第二步，直到所有元素均排序完畢。2. selectionSort 選擇排序1. 算法步驟1. 首先在未排序序列中找到最小（大）元素，存2. 動(dòng)圖演示分支主題2. selectionSort 選擇排序2. 動(dòng)圖演示分支主題2. selectionSort 選擇3. 代碼實(shí)現(xiàn)PythonJavaScriptGoJavaPHP2. selectionSort 選擇排序3. 代碼實(shí)現(xiàn)Python2. selectionSort 穩(wěn)定性不穩(wěn)定2. selectionSort 選擇排序穩(wěn)定性不穩(wěn)定2. selectionSort 選擇排序6. quickSort 快速排序011. 算法

8、步驟2. 動(dòng)圖演示023. 代碼實(shí)現(xiàn)03穩(wěn)定性046. quickSort 快速排序011. 算法步驟2. 動(dòng)6. quickSort 快速排序1. 算法步驟1. 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）;2. 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這

9、個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。6. quickSort 快速排序1. 算法步驟1. 從數(shù)列2. 動(dòng)圖演示分支主題6. quickSort 快速排序2. 動(dòng)圖演示分支主題6. quickSort 快速排序3. 代碼實(shí)現(xiàn)PythonJavaScriptGoJavaPHPC+6. quickSort 快速排序3. 代碼實(shí)現(xiàn)Python6. quickSort 快速排序穩(wěn)定性不穩(wěn)定6. quickSort 快速排序穩(wěn)定性不穩(wěn)定6. quickSort 快速排序交換排序交換排序1. bubbleSort 冒泡排序1. 算法步驟4. 什么時(shí)

10、候最慢2. 動(dòng)圖演示5. 代碼實(shí)現(xiàn)穩(wěn)定性3. 什么時(shí)候最快1. bubbleSort 冒泡排序1. 算法步驟4. 什么1. 算法步驟1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。1. bubbleSort 冒泡排序1. 算法步驟1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就2. 動(dòng)圖演示分支主題1. bubbleSort 冒泡排序2. 動(dòng)圖演示分支主題1.

11、 bubbleSort 冒泡排序3. 什么時(shí)候最快當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí)（都已經(jīng)是正序了，我還要你冒泡排序有何用啊）。1. bubbleSort 冒泡排序3. 什么時(shí)候最快當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí)（都已經(jīng)是正序了，4. 什么時(shí)候最慢1. bubbleSort 冒泡排序當(dāng)輸入的數(shù)據(jù)是反序時(shí)（寫一個(gè) for 循環(huán)反序輸出數(shù)據(jù)不就行了，干嘛要用你冒泡排序呢，我是閑的嗎）。4. 什么時(shí)候最慢1. bubbleSort 冒泡排序當(dāng)輸入5. 代碼實(shí)現(xiàn)PythonJavaScriptGoJavaPHP1. bubbleSort 冒泡排序5. 代碼實(shí)現(xiàn)Python1. bubbleSort 冒泡排穩(wěn)定性穩(wěn)定

12、1. bubbleSort 冒泡排序穩(wěn)定性穩(wěn)定1. bubbleSort 冒泡排序7. heapSort 堆排序011. 算法步驟2. 動(dòng)圖演示025. 代碼實(shí)現(xiàn)03穩(wěn)定性047. heapSort 堆排序011. 算法步驟2. 動(dòng)圖演1. 算法步驟1. 將待排序序列構(gòu)建成一個(gè)堆 H0n-1，根據(jù)（升序降序需求）選擇大頂堆或小頂堆；2. 把堆首（最大值）和堆尾互換；3. 把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；4. 重復(fù)步驟 2，直到堆的尺寸為 1。7. heapSort 堆排序1. 算法步驟1. 將待排序序列構(gòu)建成一個(gè)堆 H0n-7.

13、heapSort 堆排序2. 動(dòng)圖演示分支主題7. heapSort 堆排序2. 動(dòng)圖演示分支主題5. 代碼實(shí)現(xiàn)PythonJavaScriptGoJavaPHP7. heapSort 堆排序5. 代碼實(shí)現(xiàn)Python7. heapSort 堆排序穩(wěn)定性不穩(wěn)定7. heapSort 堆排序穩(wěn)定性不穩(wěn)定7. heapSort 堆排序分治遞歸分治遞歸5. mergeSort 歸并排序011. 算法步驟2. 動(dòng)圖演示023. 代碼實(shí)現(xiàn)03穩(wěn)定性045. mergeSort 歸并排序011. 算法步驟2. 動(dòng)1. 算法步驟1. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；2.

14、 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；3. 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；4. 重復(fù)步驟 3 直到某一指針達(dá)到序列尾；5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。5. mergeSort 歸并排序1. 算法步驟1. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和2. 動(dòng)圖演示分支主題5. mergeSort 歸并排序2. 動(dòng)圖演示分支主題5. mergeSort 歸并排序3. 代碼實(shí)現(xiàn)PythonJavaScriptGoJavaPHP5. mergeSort 歸并排序3. 代碼實(shí)現(xiàn)Python5. mergeSort 歸并

15、排序穩(wěn)定性穩(wěn)定5. mergeSort 歸并排序穩(wěn)定性穩(wěn)定5. mergeSort 歸并排序'桶' 排序'桶' 排序8. countingSort 計(jì)數(shù)排序叁穩(wěn)定穩(wěn)定性貳PythonJavaScriptGoJavaPHP2. 代碼實(shí)現(xiàn)壹分支主題1. 動(dòng)圖演示8. countingSort 計(jì)數(shù)排序叁穩(wěn)定穩(wěn)定性貳Pyt9. bucketSort 桶排序011. 什么時(shí)候最快2. 什么時(shí)候最慢023. 代碼實(shí)現(xiàn)03穩(wěn)定性049. bucketSort 桶排序011. 什么時(shí)候最快2.1. 什么時(shí)候最快當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中。9. bucket

16、Sort 桶排序1. 什么時(shí)候最快當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中。92. 什么時(shí)候最慢當(dāng)輸入的數(shù)據(jù)被分配到了同一個(gè)桶中。9. bucketSort 桶排序2. 什么時(shí)候最慢當(dāng)輸入的數(shù)據(jù)被分配到了同一個(gè)桶中。9. b3. 代碼實(shí)現(xiàn)PythonJavaScriptGoJavaPHP9. bucketSort 桶排序3. 代碼實(shí)現(xiàn)Python9. bucketSort 桶排序穩(wěn)定性穩(wěn)定9. bucketSort 桶排序穩(wěn)定性穩(wěn)定9. bucketSort 桶排序10. radixSort 基數(shù)排序11. 基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序22. LSD 基數(shù)排序動(dòng)圖演示33. 代碼實(shí)現(xiàn)4穩(wěn)定性10. radixSort 基數(shù)排序11. 基數(shù)排序 vs 1. 基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序基數(shù)排序有兩種方法：這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異案例看大家發(fā)的： - 基數(shù)排序：根據(jù)鍵值的每位數(shù)字來(lái)分配桶； - 計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值； - 桶排序：