導(dǎo)語(yǔ)
排序算法是筆試面試當(dāng)中經(jīng)常遇到的內(nèi)容壁畸，之前參加的兩個(gè)筆試都遇到了手寫(xiě)排序算法阀趴，可能大家都能寫(xiě)出來(lái)氢架，但是要出眾就要把代碼優(yōu)化一下碌尔，讓人一看到就覺(jué)得你想的不簡(jiǎn)單浇辜。首先從最簡(jiǎn)單的冒泡排序開(kāi)始，相信大家都能默出來(lái)唾戚，由于大部分人寫(xiě)的都一樣柳洋，所以你要更出眾的代碼。
冒泡排序算法的步驟：
1.比較相鄰的元素叹坦。如果第一個(gè)比第二個(gè)大熊镣，就交換他們兩個(gè)。
2.對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)绪囱。最后的元素應(yīng)該會(huì)是最大的數(shù)测蹲。
3.針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)毕箍。
4.持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟弛房，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
首先給出嚴(yán)格按照定義寫(xiě)的代碼：
void bubbleSort(int array[], int length)
{
for (int i = 0; i < length; i++) {
for (int j = 1; j < length - i; j++) {
if (array[j-1] > array[j]) {
swap(array[j-1], array[j]);
}
}
}
}
這里先給出交換函數(shù)而柑，交換函數(shù)有很多種寫(xiě)法文捶，最基本的寫(xiě)法是：
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
據(jù)說(shuō)會(huì)在筆試中考不用中間變量交換兩個(gè)數(shù)，網(wǎng)上有種寫(xiě)法：(其實(shí)這類(lèi)方法還可已通過(guò)加減乘等代換方式實(shí)現(xiàn)媒咳，但都有一定弊端粹排，雖然我們?cè)谄綍r(shí)的編程中不會(huì)這么寫(xiě)，不裝X的話(huà)還是寫(xiě)第一種)
void swap(int &a, int &b) {
a = a ^ b;
b = b ^ a;
a = a ^ b;
}
但這種寫(xiě)法有個(gè)問(wèn)題涩澡，當(dāng)交換同一元素時(shí)顽耳，該元素會(huì)被置零，在選擇排序中會(huì)有bug所以還是建議第一種寫(xiě)法妙同，當(dāng)然你也可以在里面加個(gè)判斷：
void swap(int &a, int &b) {
if (a != b) {
a = a ^ b;
b = b ^ a;
a = a ^ b;
}
}
很明顯上面的經(jīng)典算法有些不足射富，當(dāng)我們需要排序的數(shù)組基本有序時(shí)，上面的代碼還會(huì)做出很多不必要的查找判斷粥帚，降低了代碼的執(zhí)行效率胰耗。下面我們進(jìn)行第一步優(yōu)化，我們先定義一個(gè)標(biāo)志flag芒涡，用來(lái)判斷本次排序中是否發(fā)生交換柴灯，如果沒(méi)有發(fā)生交換，說(shuō)明排序已經(jīng)完成费尽，我們不需要再做不必要的循環(huán)判斷赠群，代碼為：
void bubbleSort(int array[], int length) {
bool flag = true;//判斷是否發(fā)生交換
while (flag) {
flag = false;
for (int j = 1; j < length; j++) {
if (array[j-1] > array[j]) {
swap(array[j-1], array[j]);
flag = true;
}
}
length --;
}
}
對(duì)比下兩種方法的比較大小次數(shù)：
由上圖對(duì)比可見(jiàn)，第二種方法大大減少了對(duì)比的次數(shù)旱幼。
再做進(jìn)一步優(yōu)化查描，如果有數(shù)組前面幾個(gè)是無(wú)序的，而后面的元素都已經(jīng)是有序的柏卤，那我們就可以記錄下無(wú)序的位置叹誉，下次排序判斷時(shí)，只需要從數(shù)組頭部遍歷到該位置就可以了闷旧，這樣可以省去遍歷后面的元素，提高了代碼的執(zhí)行效率钧唐。代碼為：
void bubbleSort(int array[], int length)
{
int flag = length;
while (flag > 0) {
int k = flag;
flag = 0;
for (int j = 1; j < k; j++) {
if (array[j - 1] > array[j]) {
swap(array[j - 1], array[j]);
flag = j;
}
}
}
}
該方法和第二種的區(qū)別就是：先判斷有沒(méi)有交換忙灼，若有交換我也只遍歷無(wú)序的區(qū)域。比較次數(shù)：
很明顯比上面的少了很多次。
最后要說(shuō)一句该园，冒泡排序?qū)懫饋?lái)簡(jiǎn)單酸舍，相對(duì)于其他的排序算法效率比較低下，數(shù)據(jù)規(guī)模不大時(shí)里初，可以使用啃勉。
