十大经典排序算法(动态演示+代码)
時(shí)間復(fù)雜度是指程序執(zhí)行函數(shù)或方法的效率常用大寫的O表示，比如執(zhí)行一個(gè)循環(huán)我們記做O(n)，執(zhí)行一個(gè)加法運(yùn)算或者執(zhí)行一個(gè)if操作我們記為O(1)?。
?
時(shí)間、空間復(fù)雜度比較
1 冒泡排序
算法思想：
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
冒泡排序動(dòng)圖演示
代碼：
?
2?選擇排序
算法思想：
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾
以此類推，直到所有元素均排序完畢
選擇排序動(dòng)圖演示
代碼：
?
3 插入排序
算法思想：
從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素，將該元素移到下一位置
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟2~5
插入排序動(dòng)圖演示
代碼：
?
4 快速排序
算法思想：
選取第一個(gè)數(shù)為基準(zhǔn)
將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面
對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)
快速排序動(dòng)圖演示
代碼：
?
5 堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
算法思想：
將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)；
將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成。
代碼：
?
6 歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2路歸并。
算法思想：1.把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；2. 對(duì)這兩個(gè)子序列分別采用歸并排序；3. 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
歸并排序動(dòng)圖演示
代碼：
?
7?希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序.
算法思想：
選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
希爾排序動(dòng)圖演示
代碼：
?
8?計(jì)數(shù)排序
計(jì)數(shù)排序統(tǒng)計(jì)小于等于該元素值的元素的個(gè)數(shù)i，于是該元素就放在目標(biāo)數(shù)組的索引i位（i≥0）。
-
計(jì)數(shù)排序基于一個(gè)假設(shè)，待排序數(shù)列的所有數(shù)均為整數(shù)，且出現(xiàn)在（0，k）的區(qū)間之內(nèi)。
-
如果 k（待排數(shù)組的最大值） 過大則會(huì)引起較大的空間復(fù)雜度，一般是用來排序 0 到 100 之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。
-
計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
算法思想：
找出待排序的數(shù)組中最大和最小的元素；
統(tǒng)計(jì)數(shù)組中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項(xiàng)；
對(duì)所有的計(jì)數(shù)累加（從 C 中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）；
向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在新數(shù)組的第 C[i] 項(xiàng)，每放一個(gè)元素就將 C[i] 減去 1；
計(jì)數(shù)排序動(dòng)圖演示
代碼：
?
9 桶排序
將值為i的元素放入i號(hào)桶，最后依次把桶里的元素倒出來。
算法思想：
設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。
對(duì)每個(gè)不是空的桶子進(jìn)行排序。
從不是空的桶子里把項(xiàng)目再放回原來的序列中。
桶排序動(dòng)圖演示
代碼：
?
10 基數(shù)排序
一種多關(guān)鍵字的排序算法，可用桶排序?qū)崿F(xiàn)。
算法思想：
取得數(shù)組中的最大數(shù)，并取得位數(shù)；
arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；
對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）
基數(shù)排序動(dòng)圖演示
代碼：
?
總結(jié)
以上是生活随笔為你收集整理的十大经典排序算法(动态演示+代码)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 基于Django实现RBAC权限管理
- 下一篇： Android中Dialog与Dialo