圖解3種簡(jiǎn)單排序(選擇，冒泡，直接插入)

本人免費(fèi)整理了Java高級(jí)資料，涵蓋了Java、Redis、MongoDB、MySQL、Zookeeper、Spring Cloud、Dubbo高并發(fā)分布式等教程，一共30G，需要自己領(lǐng)取。
傳送門：https://mp.weixin.qq.com/s/JzddfH-7yNudmkjT0IRL8Q

排序是數(shù)據(jù)處理中十分常見且核心的操作，雖說實(shí)際項(xiàng)目開發(fā)中很小幾率會(huì)需要我們手動(dòng)實(shí)現(xiàn)，畢竟每種語言的類庫中都有n多種關(guān)于排序算法的實(shí)現(xiàn)。但是了解這些精妙的思想對(duì)我們還是大有裨益的。本文簡(jiǎn)單溫習(xí)下最基礎(chǔ)的三類算法：選擇，冒泡，插入。

先定義個(gè)交換數(shù)組元素的函數(shù)，供排序時(shí)調(diào)用

/**?????*?交換數(shù)組元素?????*?@param?arr?????*?@param?a?????*?@param?b?????*/
????public?static?void?swap(int?[]arr,int?a,int?b){
????????arr[a]?=?arr[a]+arr[b];
????????arr[b]?=?arr[a]-arr[b];
????????arr[a]?=?arr[a]-arr[b];
????}

簡(jiǎn)單選擇排序
簡(jiǎn)單選擇排序是最簡(jiǎn)單直觀的一種算法，基本思想為每一趟從待排序的數(shù)據(jù)元素中選擇最?。ɑ蜃畲螅┑囊粋€(gè)元素作為首元素，直到所有元素排完為止，簡(jiǎn)單選擇排序是不穩(wěn)定排序。
在算法實(shí)現(xiàn)時(shí)，每一趟確定最小元素的時(shí)候會(huì)通過不斷地比較交換來使得首位置為當(dāng)前最小，交換是個(gè)比較耗時(shí)的操作。

其實(shí)我們很容易發(fā)現(xiàn)，在還未完全確定當(dāng)前最小元素之前，這些交換都是無意義的。我們可以通過設(shè)置一個(gè)變量min，每一次比較僅存儲(chǔ)較小元素的數(shù)組下標(biāo)，當(dāng)輪循環(huán)結(jié)束之后，那這個(gè)變量存儲(chǔ)的就是當(dāng)前最小元素的下標(biāo)，此時(shí)再執(zhí)行交換操作即可。代碼實(shí)現(xiàn)很簡(jiǎn)單，一起來看下。

代碼實(shí)現(xiàn)

/**?????*?交換數(shù)組元素?????*?@param?arr?????*?@param?a?????*?@param?b?????*/
????public?static?void?swap(int?[]arr,int?a,int?b){
????????arr[a]?=?arr[a]+arr[b];
????????arr[b]?=?arr[a]-arr[b];
????????arr[a]?=?arr[a]-arr[b];
????}

簡(jiǎn)單選擇排序通過上面優(yōu)化之后，無論數(shù)組原始排列如何，比較次數(shù)是不變的；對(duì)于交換操作，在最好情況下也就是數(shù)組完全有序的時(shí)候，無需任何交換移動(dòng)，在最差情況下，也就是數(shù)組倒序的時(shí)候，交換次數(shù)為n-1次。綜合下來，時(shí)間復(fù)雜度為O(n2)

冒泡排序?
冒泡排序的基本思想是，對(duì)相鄰的元素進(jìn)行兩兩比較，順序相反則進(jìn)行交換，這樣，每一趟會(huì)將最小或最大的元素“浮”到頂端，最終達(dá)到完全有序

代碼實(shí)現(xiàn)
在冒泡排序的過程中，如果某一趟執(zhí)行完畢，沒有做任何一次交換操作，比如數(shù)組[5,4,1,2,3]，執(zhí)行了兩次冒泡，也就是兩次外循環(huán)之后，分別將5和4調(diào)整到最終位置[1,2,3,4,5]。此時(shí)，再執(zhí)行第三次循環(huán)后，一次交換都沒有做，這就說明剩下的序列已經(jīng)是有序的，排序操作也就可以完成了，來看下代碼　

/**?????*?冒泡排序?????*?????*?@param?arr?????*/
????public?static?void?bubbleSort(int[]?arr)?{
????????for?(int?i?=?0;?i?<?arr.length?-?1;?i++)?{
????????????boolean?flag?=?true;//設(shè)定一個(gè)標(biāo)記，若為true，則表示此次循環(huán)沒有進(jìn)行交換，也就是待排序列已經(jīng)有序，排序已然完成。????????????for?(int?j?=?0;?j?<?arr.length?-?1?-?i;?j++)?{
????????????????if?(arr[j]?>?arr[j?+?1])?{
????????????????????swap(arr,j,j+1);
????????????????????flag?=?false;
????????????????}
????????????}
????????????if?(flag)?{
????????????????break;
????????????}
????????}
????}

根據(jù)上面這種冒泡實(shí)現(xiàn)，若原數(shù)組本身就是有序的（這是最好情況），僅需n-1次比較就可完成；若是倒序，比較次數(shù)為 n-1+n-2+...+1=n(n-1)/2，交換次數(shù)和比較次數(shù)等值。所以，其時(shí)間復(fù)雜度依然為O(n2）。綜合來看，冒泡排序性能還還是稍差于上面那種選擇排序的。

直接插入排序
直接插入排序基本思想是每一步將一個(gè)待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。

代碼實(shí)現(xiàn)?

/**
?????*?插入排序
?????*
?????*?@param?arr
?????*/
????public?static?void?insertionSort(int[]?arr)?{
????????for?(int?i?=?1;?i?<?arr.length;?i++)?{
????????????int?j?=?i;
????????????while?(j?>?0?&&?arr[j]?<?arr[j?-?1])?{
????????????????swap(arr,j,j-1);
????????????????j--;
????????????}
????????}
????}

簡(jiǎn)單插入排序在最好情況下，需要比較n-1次，無需交換元素，時(shí)間復(fù)雜度為O(n);在最壞情況下，時(shí)間復(fù)雜度依然為O(n2)。但是在數(shù)組元素隨機(jī)排列的情況下，插入排序還是要優(yōu)于上面兩種排序的。

總結(jié)
本文列舉了排序算法中最基本的三種算法（簡(jiǎn)單選擇，冒泡，插入），這三種排序算法的時(shí)間復(fù)雜度均為O(n2)，后續(xù)會(huì)陸續(xù)更新其他更高階一些的排序算法，時(shí)間復(fù)雜度也會(huì)逐步突破O(n2），謝謝支持。