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