十大排序算法！整起來！建議收藏！??！

十大排序算法對比

關(guān)于最后一列的穩(wěn)定性，我稍微解釋下，例如對序列：1 2 4 2 6 排序，序列中存在兩個2，如果我們把這兩個2標(biāo)記上（讓他倆不同），排序之后，前面的2還在前面，那么就稱這種排序是穩(wěn)定的，反之不穩(wěn)定。

冒泡排序

簡單解釋：

?原理就如算法名字一樣，就像水中的氣泡一樣，每次我都把最大的或最小的放到最后面，這樣總共需要n-1趟即可完成排序，這就是第一層循環(huán)，第二次循環(huán)就是遍歷未被固定的那些數(shù)（理解成數(shù)組左邊的數(shù)，因為每層循環(huán)都會把最大或最小的數(shù)升到最右邊固定起來，下次就不遍歷這些數(shù)了），兩層循環(huán)遍歷結(jié)束后，所有的數(shù)就排好序了。

? ? ? ?兩層循環(huán)所以冒泡排序算法的時間復(fù)雜度一個非常高的時間復(fù)雜度，我在下面的代碼進(jìn)行了優(yōu)化，加了一個標(biāo)志位，如果上一次循環(huán)未發(fā)生交換，就說明已經(jīng)是有序的了，就不繼續(xù)下去了，反之繼續(xù)進(jìn)行下一輪。

完整代碼：

測試代碼：

升序排序（從小到大）

運行結(jié)果：

降序排序（從大到?。?/p>

運行結(jié)果：

下面幾個算法的測試也就是換了下類名和方法名（換成相應(yīng)的排序算法），如果想降序就在數(shù)組后面?zhèn)鱾€false即可。我就不一一復(fù)制了，我在最下面給出含所有算法的測試類，需要的自取即可。

快速排序

簡單解釋：

快速排序就是每次找一個基點（第一個元素），然后兩個哨兵，一個從最前面往后走，一個從最后面往前面走，如果后面那個哨兵找到了一個比基點大的數(shù)停下來，前面那個哨兵找到比基點大的數(shù)停下來，然后交換兩個哨兵找到的數(shù)，如果找不到最后兩個哨兵就會碰到一起就結(jié)束，最后交換基點和哨兵相遇的地方的元素，然后就將一個序列分為比基點小的一部分和比基點大的一部分，然后遞歸左半部分和右半部分，最后的結(jié)果就是有序的了。

完整代碼：

直接選擇排序

簡單解釋：

數(shù)組分為已排序部分（前面）和待排序序列（后面）

第一次肯定所有的數(shù)都是待排序的

從待排序的序列中找到最大或最小的那個元素，放到前面的已排序部分，然后一直找，不斷縮小待排序的范圍，直到所有的數(shù)都是已排序的了

完整代碼：

堆排序

先理解下大頂堆和小頂堆，看圖

大頂堆，雙親結(jié)點的值比每一個孩子結(jié)點的值都要大。根結(jié)點值最大

小頂堆，雙親結(jié)點的值比每一個孩子結(jié)點的值都要小。根結(jié)點值最小

簡單解釋：

構(gòu)建好大頂堆或小頂堆結(jié)構(gòu)，這樣最上面的就是最大值或最小值，那么我們?nèi)〕龆秧斣?，然后重新?gòu)建結(jié)構(gòu)，一直取，一直重新構(gòu)建，那么最后達(dá)到排序的效果了。

完整代碼：

歸并排序

簡單解釋：

該算法是采用分治法，把數(shù)組不斷分割，直至成為單個元素，然后比較再合并（合并的過程就是兩部分分別從頭開始比較，取出最小或最大元素的放到新的區(qū)域內(nèi)，繼續(xù)取兩部分中最大或最小的元素，直到這兩部分合并完，最后所有的都合并完，最后形成完整的有序序列）

完整代碼：

插入排序

簡單解釋：

最簡單的理解就是打地主時我們拿到牌后的整理過程，從第二個牌（假設(shè)我們拿起來這個牌開始比較）開始，（說下升序）從后往前比較如果比前面的那個牌小，就把牌往后移動，直到找到一個合適的位置（這個位置的前面的那個牌不比這個要放下的牌大）就把這個牌放到這個位置，慢慢的前面的部分變得有序，直至全部有序即可。

完整代碼：

希爾排序

簡單解釋：

希爾排序是插入排序的改進(jìn)版，我們理解一個叫做下標(biāo)差的的東西，也就是下面那個圖中的增量d，初始下標(biāo)差為arr.length/2，然后繼續(xù)/2，對在同一下標(biāo)差（相當(dāng)于把這幾個數(shù)單獨拿出來了）的若干個數(shù)進(jìn)行插入排序即可。

完整代碼：

計數(shù)排序

簡單解釋：

這個排序算法看名字也很好理解，就是就是額外找個數(shù)組來計數(shù)，然后在這個數(shù)組從小到大或從大到小把數(shù)取出來即可。

完整代碼：

桶排序

簡單解釋：

就是把一個數(shù)組分成幾個桶（其實是幾個區(qū)間，從小到大或從大到小的幾個區(qū)間）裝，然后讓每個桶（區(qū)間）有序，然后取出來放一起就可以了，相當(dāng)于把幾個有序的段拿出來放一起，自然還是有序的，當(dāng)然需要是按照區(qū)間的順序拿了。

完整代碼：

基數(shù)排序

簡單解釋：

首先說一下，我發(fā)現(xiàn)好多人寫的基數(shù)排序只能排序正整數(shù)，其實只要處理下就可以排序含有負(fù)數(shù)的了，就是我們排序前先把所有的數(shù)整體變大（就是減上最小的負(fù)數(shù)，也就是加了），都變成正數(shù)，然后排序好之后，在減下來（加上最小的負(fù)數(shù)，也就減了）就好了。

基數(shù)排序就是按數(shù)位排序可分為LSD（從最低位[也就是個位]開始排序）和MSD（從最高位開始排序），下面寫的事LSD基數(shù)排序。

基數(shù)排序就是把數(shù)按位考慮，讓后我們一位數(shù)只能是[0，9]，就是我們在考慮某位（個位、百位· · ·）的時候就只看這個位的數(shù)，放到在[0，9]相應(yīng)的位置，然后順序取出，最后再按其它位這樣操作（上面說了要不從低位開始到高位，要不就是從高位到低位）

完整代碼：

完整測試類

每天進(jìn)步一點點！

版權(quán)聲明：

原創(chuàng)博主：牛哄哄的柯南

博主原文鏈接：https://keafmd.blog.csdn.net/

看完如果對你有幫助，感謝點贊支持！看到右下角的 “一鍵三連” 了嗎，沒錯點它O(∩_∩)O