手撕排序算法在IT開發(fā)類職位校招中出現(xiàn)的頻率非常的高。

普通小公司一般讓你寫一個簡單排序，具體是什么排序也不關(guān)心，能寫出一個就行；一二線大公司考查的一般是高級排序，而且會隨機(jī)指定。

我們選擇了最常見的兩種冒泡排序算法進(jìn)行講解，一種是普通冒泡排序，另一種是冒泡的高級算法——快速排序。

大家按照自己校招的目標(biāo)層次可能認(rèn)領(lǐng)。

在開始之前，先解答一類同學(xué)的問題：這個問題有什么難的？對數(shù)組排序，一句代碼就搞定

Arrays.sort()；

這就是沒理解這道題考察的意圖，不是考察你java API的使用，而是看看你的思維和代碼編程能力。

開發(fā)工程師的主要工作就是處理各種邏輯。

比如給你一個真實的工作需求，讓你把一個數(shù)據(jù)作排序，但是相同的數(shù)只保留兩個，或者給一個字符串按第個字母進(jìn)行排序。

只會使用API或者粘貼復(fù)制是遠(yuǎn)遠(yuǎn)不夠的，

而排序算法是邏輯最直接的，最好表達(dá)，也是行數(shù)較少的思維考查，所以筆試面試?yán)镆娒娴拇螖?shù)就比較多。? ?? ?

?01-冒泡排序

冒泡是最簡單的一種排序，但是一定要理解“冒泡”的含義。
有時候讓面試者寫一個冒泡排序，但是他給的卻是選擇排序。冒泡排序有如下幾個要點

1. 冒泡是數(shù)據(jù)a相鄰的兩個數(shù)進(jìn)行比較，比如前面的數(shù)比后面的數(shù)大，那么就發(fā)生交換。

if(a[j]?>?a[j?+1]){????

????int?temp?=?a[j?+1];?????

????a[j+1]?=?a[j]????

????a[j]?=?temp;

}

2.?第一輪從第1個數(shù)開始兩兩比較，一輪下來，最大的數(shù)冒泡到了數(shù)組最后，但是前面的數(shù)還是無序的（正常情況下）

for(int?j?=?0?;?j?<?a.size-1?;?j?++){????

//1中的代碼

}

3.?然后對每輪進(jìn)行一次冒泡，輪數(shù)是固定的，是數(shù)組長度-1，得到外循環(huán)

for(int i = 0; i< a.size -1 ; 1++)

4.因為每輪最后一位數(shù)是確定的，不需要再參與下一次的排序，所以內(nèi)循環(huán)的后長度不斷縮小,修改2

for(int?i?=?0;?i<?a.size?-1?;?1++){????

? for(int?j?=0?;?j?<?a.size?-?i-1?;?j++?){??????

? ? //1中的代碼??

? }

}

5. 冒泡排序還可以加一種優(yōu)化思路，如果一輪冒泡，沒有發(fā)生一次交換，即對于數(shù)組中任意相鄰的兩個數(shù)，前面的數(shù)都小于等于后面的數(shù)。

實際上已經(jīng)排序完成。

?? ??02-快速排序

快速排序是冒泡的改進(jìn)高級排序，數(shù)據(jù)結(jié)構(gòu)里常見的高級排序時間復(fù)雜度都是O(N*logN)。

很多同學(xué)不理解這個時間復(fù)雜度，簡單來說，就是每輪比較都把數(shù)組分為兩部分，就是每輪時間都減半，那么n輪就是log級別的。

快速排序要點如下：（如果不理解，可以去官網(wǎng)看視頻講解）

1.?快速排序就是每輪把數(shù)組分為兩部分（長度不一定相等），然后兩邊再不斷分割，最后變成長度為1的全部有序單元

這個時候還完全不理解快速排序的思想，就可以實現(xiàn)下列代碼

void?quickSort(int[]?s,?int?l,?int?r){??

? ?if?(l?<?r)?{????

? ? ? int?i?=?patition(s,?l,?r);//patition是具體的排序過程

? ? ? quickSort(s, l, i - 1); // 遞歸調(diào)用 ? ?

? ? ? quickSort(s, i + 1, r);??

? ?}

}

2. 每次排序就是找到一個基準(zhǔn)點，一般采用數(shù)組的第一個數(shù)，然后按照一定規(guī)則冒泡，最后找到它的位置。

在它左邊的數(shù)比它小，在它右邊的數(shù)比它大。返回的是基準(zhǔn)數(shù)最后的位置，用于1中的數(shù)組遞歸切分。

這個時候也是還不知道具體的分割方法，但是不影響寫出以下代碼。

int?patition(int[]?s,?int?l,?int?r)?{ ?

? ?int i = l, j = r; ?int x = s[l]; //s[l]即s[i]就是第一個坑??

? ?while?(i?<?j)??{????

? ? ? ?//具體的單輪冒泡過程，現(xiàn)在還不知道 ?

? ?} ?//退出時，i等于j。將x填到這個坑中。??

? ?s[i]?=?x;???

? ?return?i;

}

3.?每輪把當(dāng)前數(shù)組分為左小右大的過程，是快排的難點和精髓。重點是找到每個數(shù)放置的位置。

因為基準(zhǔn)數(shù)是第1個數(shù)，如果簡單的從前往后移動，比基數(shù)小還好處理，直接不動，但是當(dāng)前數(shù)比基準(zhǔn)數(shù)大，這個數(shù)放在哪個位置，就很難解決，因為基準(zhǔn)還要往右走。

所以簡單從前往后不實用。

數(shù)據(jù)結(jié)構(gòu)教材上使用的方法，俗稱“挖坑法”。

設(shè)置基準(zhǔn)數(shù)x=a[0]后，a[0]就空出來了，因為左小，也就是要找到一個比基準(zhǔn)數(shù)小的數(shù)放到這個空出的坑里。

從后往前j找比基準(zhǔn)數(shù)小的，放到左邊的這個坑里

while(i < j && s[j] >= x) ????

? j--;

if(i?<?j)?{????

? s[i]?=?s[j];?//將s[j]填到s[i]中，s[j]就形成了一個新的坑????

? i++;

}

這時候j的位置，也是右邊出現(xiàn)了一個空的坑，需要找一個比基準(zhǔn)數(shù)大的數(shù)填它（右大）。
那就從前i往后找比基準(zhǔn)數(shù)大的數(shù)，放到右側(cè)j的位置

while(i < j && s[i] < x) ? ?
??i++; ?

if(i?<?j)?{ ? ? ?

? s[j] = s[i]; //將s[i]填到s[j]中，s[i]就形成了一個新的坑??????

? j--;

}

反復(fù)填坑，直到i = j，這時候就說明基準(zhǔn)數(shù)的前面都小于當(dāng)前數(shù)，右邊都大于。

4. 把3中的邏輯放到2中的具體邏輯部分，代碼就完成了。
?? ?