簡(jiǎn)單選擇排序：記下最大值的序號(hào)骏全，然后把數(shù)組最后一個(gè) ? ? ?跟記下的序號(hào) ? 交換
冒泡排序：從左到右苍柏，相鄰兩個(gè)依次交換
直接插入排序：前邊兩個(gè)先排序
? ? ? ? ? ? ? ? ? ? ? ? ? ? 前邊三個(gè)排序
? ? ? ? ? ? ? ? ? ? ? ? ? ? 前邊四個(gè)排序
排序是數(shù)據(jù)處理中十分常見(jiàn)且核心的操作，雖說(shuō)實(shí)際項(xiàng)目開(kāi)發(fā)中很小幾率會(huì)需要我們手動(dòng)實(shí)現(xiàn)姜贡，畢竟每種語(yǔ)言的類庫(kù)中都有n多種關(guān)于排序算法的實(shí)現(xiàn)试吁。但是了解這些精妙的思想對(duì)我們還是大有裨益的。本文簡(jiǎn)單溫習(xí)下最基礎(chǔ)的三類算法：選擇鲁豪，冒泡潘悼，插入。
先定義個(gè)交換數(shù)組元素的函數(shù)爬橡，供排序時(shí)調(diào)用
/**? ? * 交換數(shù)組元素
? ? * @param arr
? ? * @param a
? ? * @param b
? ? */publicstaticvoidswap(int[]arr,inta,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ì)通過(guò)不斷地比較交換來(lái)使得首位置為當(dāng)前最小缕陕，交換是個(gè)比較耗時(shí)的操作。其實(shí)我們很容易發(fā)現(xiàn)疙挺，在還未完全確定當(dāng)前最小元素之前扛邑，這些交換都是無(wú)意義的。我們可以通過(guò)設(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)單跨琳，一起來(lái)看下。
代碼實(shí)現(xiàn)
/**? ? * 簡(jiǎn)單選擇排序
? ? *
? ? * @param arr
? ? */publicstaticvoidselectSort(int[] arr) {
? ? ? ? for(inti = 0; i < arr.length - 1; i++) {
? ? ? ? ? ? intmin = i;//每一趟循環(huán)比較時(shí)桐罕，min用于存放較小元素的數(shù)組下標(biāo)脉让，這樣當(dāng)前批次比較完畢最終存放的就是此趟內(nèi)最小的元素的下標(biāo)，避免每次遇到較小元素都要進(jìn)行交換功炮。for(intj = i + 1; j < arr.length; j++) {
? ? ? ? ? ? ? ? if(arr[j] < arr[min]) {
? ? ? ? ? ? ? ? ? ? min = j;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? //進(jìn)行交換溅潜，如果min發(fā)生變化，則進(jìn)行交換if(min != i) {
? ? ? ? ? ? ? ? swap(arr,min,i);
? ? ? ? ? ? }
? ? ? ? }
? ? }
簡(jiǎn)單選擇排序通過(guò)上面優(yōu)化之后死宣，無(wú)論數(shù)組原始排列如何伟恶，比較次數(shù)是不變的；對(duì)于交換操作毅该，在最好情況下也就是數(shù)組完全有序的時(shí)候，無(wú)需任何交換移動(dòng)潦牛，在最差情況下眶掌，也就是數(shù)組倒序的時(shí)候，交換次數(shù)為n-1次巴碗。綜合下來(lái)朴爬，時(shí)間復(fù)雜度為O(n2)
冒泡排序?
冒泡排序的基本思想是，對(duì)相鄰的元素進(jìn)行兩兩比較橡淆，順序相反則進(jìn)行交換召噩，這樣，每一趟會(huì)將最小或最大的元素“浮”到頂端逸爵，最終達(dá)到完全有序
代碼實(shí)現(xiàn)
在冒泡排序的過(guò)程中具滴，如果某一趟執(zhí)行完畢，沒(méi)有做任何一次交換操作师倔，比如數(shù)組[5,4,1,2,3]构韵，執(zhí)行了兩次冒泡，也就是兩次外循環(huán)之后趋艘，分別將5和4調(diào)整到最終位置[1,2,3,4,5]疲恢。此時(shí)，再執(zhí)行第三次循環(huán)后瓷胧，一次交換都沒(méi)有做显拳，這就說(shuō)明剩下的序列已經(jīng)是有序的，排序操作也就可以完成了搓萧，來(lái)看下代碼
/**? ? * 冒泡排序
? ? *
? ? * @param arr
? ? */publicstaticvoidbubbleSort(int[] arr) {
? ? ? ? for(inti = 0; i < arr.length - 1; i++) {
? ? ? ? ? ? booleanflag =true;//設(shè)定一個(gè)標(biāo)記杂数，若為true遇八，則表示此次循環(huán)沒(méi)有進(jìn)行交換，也就是待排序列已經(jīng)有序耍休，排序已然完成刃永。for(intj = 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）燃少。綜合來(lái)看束亏，冒泡排序性能還還是稍差于上面那種選擇排序的。
直接插入排序
直接插入排序基本思想是每一步將一個(gè)待排序的記錄阵具，插入到前面已經(jīng)排好序的有序序列中去碍遍，直到插完所有元素為止。
代碼實(shí)現(xiàn)?
/**? ? * 插入排序
? ? *
? ? * @param arr
? ? */publicstaticvoidinsertionSort(int[] arr) {
? ? ? ? for(inti = 1; i < arr.length; i++) {
? ? ? ? ? ? intj = i;
? ? ? ? ? ? while(j > 0 && arr[j] < arr[j - 1]) {
? ? ? ? ? ? ? ? swap(arr,j,j-1);
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? }
? ? ? ? }
? ? }
簡(jiǎn)單插入排序在最好情況下阳液，需要比較n-1次怕敬，無(wú)需交換元素，時(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）仁期，謝謝支持桑驱。
