一說(shuō)到冒泡排序,學(xué)過(guò)C語(yǔ)言的人都不會(huì)陌生.冒泡排序一個(gè)簡(jiǎn)單易懂的排序方法,使我們很好的掌握了兩層for循環(huán)的用法.
一般的來(lái)說(shuō),對(duì)一個(gè)數(shù)組 int array[5] = [12, 2, 33, 25, 6];進(jìn)行簡(jiǎn)單的排序,大家也都會(huì)想到冒泡排序.就會(huì)迅速的在編譯器上敲下已經(jīng)爛熟于心的冒泡排序代碼:(如下:)
for (int i = 0 ; i < 5 - 1; i++) {
????? for (int j = 0; j < 5- 1 - i; j++) {
????????????? if (array[j] > array[j + 1]) {
????????????????????? array[j] = array[j] ^ array[j + 1];
????????????????????? array[j + 1] = array[j] ^ array[j + 1];
????????????????????? array[j] = array[j] ^ array[j + 1];
???????????? }
?????? }
}
上面的代碼已經(jīng)對(duì)冒泡排序進(jìn)行了實(shí)現(xiàn).另外在交換兩個(gè)變量的時(shí)候,用^(異或)來(lái)交換兩個(gè)變量的值,這種方法逼格很高.(推薦使用)
現(xiàn)在問(wèn)題來(lái)了:假如說(shuō)給你一個(gè)數(shù)組,數(shù)組里面的元素大部分已經(jīng)是有序的,int array[5]={23, 32, 7, 4, 2}; 這樣的話,我用上面的冒泡排序?qū)?shù)組array進(jìn)行降序的話,還是會(huì)進(jìn)行一一比較確定是否交換.那么我們?cè)撊绾胃倪M(jìn)冒泡排序,使它知道后面有序的情況下,就不在繼續(xù)for循環(huán)?
我們?cè)撊绾沃罃?shù)組array后面的是否有序?通過(guò)for循環(huán),我們需要前后兩個(gè)數(shù)一次比較,如果滿足某個(gè)要求(降序或升序)這樣的話,我們才能對(duì)這兩個(gè)數(shù)進(jìn)行交換.如果沒(méi)有進(jìn)行交換,則說(shuō)明這兩個(gè)數(shù)是有序的(這兩個(gè)數(shù)按照降序或者升序排列), 如果循環(huán)到最后依舊沒(méi)有交換過(guò),則說(shuō)明后面的數(shù)都是有序的.
因此,我們需要定義一個(gè)布爾類(lèi)型的變量來(lái)記錄,循環(huán)中相比較的兩個(gè)數(shù)是否進(jìn)行了交換.實(shí)現(xiàn)代碼如下:
BOOL isNeedNext = YES;//定義BOOL值決定是否需要下一趟比較
for(inti =0; i < 5 -1&& isNeedNext; i++) {
??????? //每趟開(kāi)始假定不需要下一趟比較
??????? isNeedNext =NO;
??????? for(intj =0; j < 5 -1- i ; j++) {
? ? ? ? ? ? ? if(array[j] > array[j + 1]) {
???????????????? //如果發(fā)生交換,說(shuō)明還是亂序,需要下一趟
??????????????? isNeedNext =YES;
? ? ? ? ? ? ? array[j] = array[j] ^ array[j + 1];
????????????? array[j + 1] = array[j] ^ array[j + 1];
????????????? array[j] = array[j] ^ array[j + 1];
?????? ? ?? }
????? }
}
