本文介紹常見(jiàn)的八大排序算法：直接插入排序、希爾排序、選擇排序、堆排序、冒泡排序、快排、歸并排序以及計(jì)數(shù)排序

文章內(nèi)容很干，也很長(zhǎng)，不過(guò)有多種動(dòng)圖圖解，希望可以給枯燥的算法學(xué)習(xí)帶來(lái)一抹亮色！

如果對(duì)于復(fù)雜度還不清楚，可以查看下面的文章

五分鐘復(fù)雜度

1冒泡排序

對(duì)于冒泡排序相信我們都比較熟悉了，其核心思想就是相鄰元素兩兩比較，把較大的元素放到后面，在一輪比較完成之后，最大的元素就位于最后一個(gè)位置了，就好像是氣泡，慢慢的浮出了水面一樣

Java 版實(shí)現(xiàn)

public?class?BubbleSort1?{public?static?void?BubbleSort(int[]?arr)?{boolean?flag?=?true;while(flag){int?temp;//定義一個(gè)臨時(shí)變量for(int?i=0;i<arr.length-1;i++){//冒泡趟數(shù)，n-1趟for(int?j=0;j<arr.length-i-1;j++){if(arr[j+1]<arr[j]){temp?=?arr[j];arr[j]?=?arr[j+1];arr[j+1]?=?temp;flag?=?true;}}if(!flag){break;//若果沒(méi)有發(fā)生交換，則退出循環(huán)}}}}public?static?void?main(String[]?args)?{int?arr[]?=?new?int[]{1,6,2,2,5};BubbleSort.BubbleSort(arr);System.out.println(Arrays.toString(arr));} }

Python 版實(shí)現(xiàn)

def?bubble_sort(data,?reverse=False):""":param?data:?list?type?data:param?reverse::return:?list?type?data"""if?not?reverse:for?i?in?range(len(data)?-?1):for?j?in?range(len(data)?-?1?-i):if?data[j]?>?data[j+1]:data[j],?data[j+1]?=?data[j+1],?data[j]return?dataelse:for?i?in?range(len(data)?-?1):for?j?in?range(len(data)?-?1?-i):if?data[j]?<?data[j+1]:data[j],?data[j?+?1]?=?data[j?+?1],?data[j]return?data

冒泡排序算法還是比較好理解的，只需要進(jìn)行兩次循環(huán)，最外層的循環(huán)代表排序元素的個(gè)數(shù)，內(nèi)部循環(huán)則進(jìn)行兩兩比較，時(shí)間復(fù)雜度為 O(n^2)

2快速排序

快排的思想為首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱(chēng)為一趟快速排序，之后再遞歸排序兩邊的數(shù)據(jù)

Jave 版實(shí)現(xiàn)

public?class?QuickSort?{public?static?void?quickSort(int[]?arr,int?low,int?high){int?i,j,temp,t;if(low>high){return;}i=low;j=high;//temp就是基準(zhǔn)位temp?=?arr[low];while?(i<j)?{//先看右邊，依次往左遞減while?(temp<=arr[j]&&i<j)?{j--;}//再看左邊，依次往右遞增while?(temp>=arr[i]&&i<j)?{i++;}//如果滿足條件則交換if?(i<j)?{t?=?arr[j];arr[j]?=?arr[i];arr[i]?=?t;}}//最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換arr[low]?=?arr[i];arr[i]?=?temp;//遞歸調(diào)用左半數(shù)組quickSort(arr,?low,?j-1);//遞歸調(diào)用右半數(shù)組quickSort(arr,?j+1,?high);}public?static?void?main(String[]?args){int[]?arr?=?{10,7,2,4,7,62,3,4,2,1,8,9,19};quickSort(arr,?0,?arr.length-1);for?(int?i?=?0;?i?<?arr.length;?i++)?{System.out.println(arr[i]);}} }

Python 版實(shí)現(xiàn)

def?quick_sort(data):if?not?data:return?datafirst?=?data[0]left?=?quick_sort([l?for?l?in?data[1:]?if?l?<?first])right?=?quick_sort([r?for?r?in?data[1:]?if?r?>=?first])return?left?+?[first]?+?right

相比冒泡排序，快速排序每次交換是跳躍式的。每次排序的時(shí)候設(shè)置一個(gè)基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時(shí)候就不會(huì)像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了，時(shí)間復(fù)雜度為 O（N*logN）

3直接插入排序

插入排序的思想是把一個(gè)數(shù)據(jù)插入到一個(gè)有序序列中，從而得到一個(gè)新的序列加一的有序序列，可以通過(guò)下圖來(lái)進(jìn)一步加深理解

Java 版實(shí)現(xiàn)

public?static?void?InsertSort(int[]?arr) {int?i,?j;int?n?=?arr.Length;int?target;//假定第一個(gè)元素被放到了正確的位置上//這樣，僅需遍歷1?-?n-1for?(i?=?1;?i?<?n;?i++){j?=?i;target?=?arr[i];while?(j?>?0?&&?target?<?arr[j?-?1]){arr[j]?=?arr[j?-?1];j--;}arr[j]?=?target;} }

Python 版實(shí)現(xiàn)

def?insert_sort(data,?reverse=False):if?not?reverse:for?i?in?range(1,?len(data)):key?=?data[i]j?=?i?-?1while?j?>=?0:if?data[j]?>?key:data[j+1]?=?data[j]data[j]?=?keyj?-=?1return?dataelse:for?i?in?range(1,?len(data)):key?=?data[i]j?=?i?-?1while?j?>=?0:if?data[j]?<?key:data[j+1]?=?data[j]data[j]?=?keyj?-=?1return?data

由于每次遍歷有序序列時(shí)，都會(huì)有序列中所有的數(shù)據(jù)做對(duì)比，故而時(shí)間復(fù)雜度為O(n^2)

4選擇排序

選擇排序，是逐個(gè)確定元素位置的思想。同樣是 n 遍循環(huán)，第一輪時(shí)，每一個(gè)元素都與第一個(gè)元素比較，如果比第一個(gè)元素大，則與之交換，這樣一輪過(guò)后，第一個(gè)元素就是最小的了，第二輪開(kāi)始每個(gè)元素與第二個(gè)位置的元素比較，如果大，則與第二位置的元素交換，以此類(lèi)推，達(dá)到排序的目的

Java 版實(shí)現(xiàn)

public?static?int[]?selectionSort(int[]?array)?{int?len?=?array.length;//?如果數(shù)組長(zhǎng)度為0或者1，都是不用排序直接返回if(len?==?0?||?len?==?1)?{return?array;}for(int?i?=?0;?i?<?len?-?1;?i++)?{int?minIdx?=?i;for(int?j?=?i?+?1;?j?<?len;?j++)?{//?找到最小的數(shù)if(array[minIdx]?>?array[j])?{//?保存最小數(shù)的索引minIdx?=?j;}}//?如果一輪比較下來(lái)都沒(méi)有變更最小值的索引則無(wú)需調(diào)換順序if(minIdx?!=?i)?{int?tmp?=?array[i];array[i]?=?array[minIdx];array[minIdx]?=?tmp;}}return?array; }

Python 版實(shí)現(xiàn)

def?selection_sort(data,?reverse=False):""":param?data:?list?type?data:param?reverse::return:?list?type?data"""if?not?reverse:for?i?in?range(len(data)-1):min_index?=?ifor?j?in?range(i+1,?len(data)):if?data[j]?<?data[min_index]:min_index?=?jdata[i],?data[min_index]?=?data[min_index],?data[i]return?dataelse:for?i?in?range(len(data)?-?1):min_index?=?ifor?j?in?range(i+1,?len(data)):if?data[j]?>?data[min_index]:min_index?=?jdata[i],?data[min_index]?=?data[min_index],?data[i]return?data

選擇排序和冒泡排序還是很相似的，但是選擇排序會(huì)比冒泡排序少一次交換的過(guò)程，但是同樣是兩層循環(huán)，所有時(shí)間復(fù)雜度也是 O(n^2)

5并歸排序

可以把一個(gè)數(shù)組分成兩半，對(duì)于每一個(gè)數(shù)組當(dāng)他們是有序的就可以進(jìn)行一次合并操作。對(duì)于他們的兩個(gè)區(qū)間進(jìn)行遞歸，一直遞歸下去劃分區(qū)間，當(dāng)區(qū)間只有一個(gè)值的時(shí)候我們就可以進(jìn)行合并返回上一層，讓上一層合并再返回

Java 版實(shí)現(xiàn)

public?static?int[]?sort(int[]?a,int?low,int?high){int?mid?=?(low+high)/2;if(low<high){sort(a,low,mid);sort(a,mid+1,high);//左右歸并merge(a,low,mid,high);}return?a;}public?static?void?merge(int[]?a,?int?low,?int?mid,?int?high)?{int[]?temp?=?new?int[high-low+1];int?i=?low;int?j?=?mid+1;int?k=0;//?把較小的數(shù)先移到新數(shù)組中while(i<=mid?&&?j<=high){if(a[i]<a[j]){temp[k++]?=?a[i++];}else{temp[k++]?=?a[j++];}}//?把左邊剩余的數(shù)移入數(shù)組?while(i<=mid){temp[k++]?=?a[i++];}//?把右邊邊剩余的數(shù)移入數(shù)組while(j<=high){temp[k++]?=?a[j++];}//?把新數(shù)組中的數(shù)覆蓋nums數(shù)組for(int?x=0;x<temp.length;x++){a[x+low]?=?temp[x];}}

Python 版實(shí)現(xiàn)

def?merge(a,?b):c?=?[]h?=?j?=?0while?j?<?len(a)?and?h?<?len(b):if?a[j]?<?b[h]:c.append(a[j])j?+=?1else:c.append(b[h])h?+=?1if?j?==?len(a):for?i?in?b[h:]:c.append(i)else:for?i?in?a[j:]:c.append(i)return?cdef?merge_sort(lists):if?len(lists)?<=?1:return?listsmiddle?=?len(lists)//2left?=?merge_sort(lists[:middle])right?=?merge_sort(lists[middle:])return?merge(left,?right)

歸并排序采用分而治之的原理：首先將一個(gè)序列從中間位置分成兩個(gè)序列，然后再將這兩個(gè)子序列按照第一步繼續(xù)二分下去，最后直到所有子序列的長(zhǎng)度都為1，也就是不可以再二分截止。這時(shí)候再兩兩合并成一個(gè)有序序列即可。時(shí)間復(fù)雜度 O（NlogN)

6隨機(jī)快速排序

隨機(jī)快速排序與快速排序的思路一樣，差異就是取主元之前，隨機(jī)快速排序多了一個(gè)步驟：隨機(jī)快速排序是隨機(jī)取得一個(gè)元素，并且會(huì)與最后一個(gè)元素交換位置。取得主元的下標(biāo)位置實(shí)際上還是最后一個(gè)下標(biāo)，快速排序是習(xí)慣取得最后一個(gè)元素作為主元

Java 版實(shí)現(xiàn)

package?quicksort;import?java.util.Random;public?class?RandomQuickSort?{public?void?Sort(int[]?a,?int?p,?int?r)?{if?(p?<?r)?{int?q?=?Partition(a,?p,?r);Sort(a,?p,?q-1);Sort(a,q+1,?r);}}private?int?Partition(int[]?A,?int?p,?int?r)?{/*隨機(jī)選取主元元素*/Random?random?=?new?Random();int?random_index?=?random.nextInt(r-p+1)+p;System.out.println("random_index="+random_index);int?temp?=?A[random_index];A[random_index]?=?A[r];A[r]?=?temp;int?x?=?A[r];??//pivot?=?A[p]int?i?=?p-1;for?(int?j?=?p;?j?<?r;?j++)?{if?(A[j]?<=?x)?{??//與pivot作比較i++;int?tmp?=?A[j];A[j]?=?A[i];A[i]?=?tmp;}}int?tmp?=?A[r];A[r]?=?A[i+1];A[i+1]?=?tmp;return?i+1;}}

Python 版實(shí)現(xiàn)

import?random def?random_quicksort(a,left,right):if(left<right):mid?=?random_partition(a,left,right)random_quicksort(a,left,mid-1)random_quicksort(a,mid+1,right)def?random_partition(a,left,right):?t?=?random.randint(left,right)?????#生成[left,right]之間的一個(gè)隨機(jī)數(shù)a[t],a[right]?=?a[right],a[t]????x?=?a[right]i?=?left-1?????????????????????????#初始i指向一個(gè)空，保證0到i都小于等于?xfor?j?in?range(left,right):????????#j用來(lái)尋找比x小的，找到就和i+1交換，保證i之前的都小于等于xif(a[j]<=x):i?=?i+1a[i],a[j]?=?a[j],a[i]a[i+1],a[right]?=?a[right],a[i+1]??#0到i?都小于等于x?,所以x的最終位置就是i+1return?i+1while(True):try:s?=?input("輸入待排序數(shù)組：\n")?????????????#待排數(shù)組l?=s.split()a?=?[int(t)?for?t?in?l]random_quicksort(a,0,len(a)-1)print?("排序后：")for?item?in?a:print(item,end=‘?‘)print("\n")except:break

7計(jì)數(shù)排序

首先統(tǒng)計(jì)原數(shù)組中每個(gè)值出現(xiàn)的次數(shù)

然后進(jìn)行排序：遍歷Count數(shù)組，對(duì)應(yīng)位置的值出現(xiàn)多少次就往原數(shù)組寫(xiě)幾個(gè)這個(gè)值

當(dāng)然，在對(duì)于數(shù)據(jù)比較大的時(shí)候我們可以通過(guò)相對(duì)映射，讓（該值-min）后的數(shù)組加一，最后還原回去即可

Java 版實(shí)現(xiàn)

public?static?int[]?CountingSort(int[]?a)?{int?b[]?=?new?int[a.length];int?max?=?a[0],?min?=?a[0];for?(int?i=1;i<a.length;i++)?{if?(a[i]?>?max)?{max?=?a[i];}if?(a[i]?<?min)?{min?=?a[i];}}?//?k的大小是要排序的數(shù)組中，元素大小的極值差+1int?k?=?max?-?min?+?1;int?c[]?=?new?int[k];//統(tǒng)計(jì)A數(shù)組元素出現(xiàn)次數(shù)for?(int?i?=?0;?i?<?a.length;?++i)?{c[a[i]?-?min]?+=?1;}//更新計(jì)算C數(shù)組for?(int?i?=?1;?i?<?c.length;?++i)?{c[i]?=?c[i]?+?c[i?-?1];}//填充B數(shù)組for?(int?i?=?a.length?-?1;?i?>=?0;?--i)?{b[--c[a[i]?-?min]]?=?a[i];}return?b; }

Python 版實(shí)現(xiàn)

def?countSort(arr):max_value?=?max(arr)res?=?[]count_nums?=?[0?for?i?in?range(max_value?+?1)]for?num?in?arr:count_nums[num]?+=?1for?i?in?range(len(count)):if?count_nums[i]?!=?0: #?元素i有?count_nums[i]個(gè)，添加入最終的排序數(shù)組res.extend(count_nums[i]?*?[i])return?res

8基數(shù)排序

基數(shù)排序核心思想是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類(lèi)推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前

Java 版實(shí)現(xiàn)

public?class?RadixSort?{public?static?void?main(String[]?args)?{int[]?arr?=?{63,?157,?189,?51,?101,?47,?141,?121,?157,?156,194,?117,?98,?139,?67,?133,?181,?12,?28,?0,?109};radixSort(arr);System.out.println(Arrays.toString(arr));}/***?高位優(yōu)先法**?@param?arr?待排序列，必須為自然數(shù)*/private?static?void?radixSort(int[]?arr)?{//待排序列最大值int?max?=?arr[0];int?exp;//指數(shù)//計(jì)算最大值for?(int?anArr?:?arr)?{if?(anArr?>?max)?{max?=?anArr;}}//從個(gè)位開(kāi)始，對(duì)數(shù)組進(jìn)行排序for?(exp?=?1;?max?/?exp?>?0;?exp?*=?10)?{//存儲(chǔ)待排元素的臨時(shí)數(shù)組int[]?temp?=?new?int[arr.length];//分桶個(gè)數(shù)int[]?buckets?=?new?int[10];//將數(shù)據(jù)出現(xiàn)的次數(shù)存儲(chǔ)在buckets中for?(int?value?:?arr)?{//(value?/?exp)?%?10?:value的最底位(個(gè)位)buckets[(value?/?exp)?%?10]++;}//更改buckets[i]，for?(int?i?=?1;?i?<?10;?i++)?{buckets[i]?+=?buckets[i?-?1];}//將數(shù)據(jù)存儲(chǔ)到臨時(shí)數(shù)組temp中for?(int?i?=?arr.length?-?1;?i?>=?0;?i--)?{temp[buckets[(arr[i]?/?exp)?%?10]?-?1]?=?arr[i];buckets[(arr[i]?/?exp)?%?10]--;}//將有序元素temp賦給arrSystem.arraycopy(temp,?0,?arr,?0,?arr.length);}} }

Python 版實(shí)現(xiàn)

def?radixSort(arr):n?=?len(str(max(arr)))??#?記錄最大值的位數(shù)for?k?in?range(n):#n輪排序#?每一輪生成10個(gè)列表bucket_list=[[]?for?i?in?range(10)]#因?yàn)槊恳晃粩?shù)字都是0~9，故建立10個(gè)桶for?i?in?arr:#?按第k位放入到桶中bucket_list[i//(10**k)%10].append(i)#?按當(dāng)前桶的順序重排列表arr=[j?for?i?in?bucket_list?for?j?in?i]return?arr

今天我們的排序算法就介紹到這里，后面我們還會(huì)更加深入的介紹其他數(shù)據(jù)結(jié)構(gòu)和算法，不要錯(cuò)過(guò)哦

往期精彩回顧適合初學(xué)者入門(mén)人工智能的路線及資料下載機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印機(jī)器學(xué)習(xí)在線手冊(cè)深度學(xué)習(xí)筆記專(zhuān)輯《統(tǒng)計(jì)學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專(zhuān)輯 AI基礎(chǔ)下載黃海廣老師《機(jī)器學(xué)習(xí)課程》視頻課黃海廣老師《機(jī)器學(xué)習(xí)課程》711頁(yè)完整版課件

本站qq群955171419，加入微信群請(qǐng)掃碼：

總結(jié)

以上是生活随笔為你收集整理的【算法】动图展示八大常用排序算法，一次看个够！的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。