冒泡排序的定義如下：
它重復(fù)地走訪過要排序的元素列取劫，依次比較兩個相鄰的元素，如果他們的順序（如從大到小研侣、首字母從A到Z）錯誤就把他們交換過來谱邪。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成庶诡。
這個算法的名字由來是因?yàn)樵酱蟮脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列）惦银，就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”
比如我們有一個數(shù)組
NSArray *array = @[@4, @14, @1, @38, @26, @9, @101, @7];
那么我們按照冒泡排序的定義交換應(yīng)該如下：
| 第一輪循環(huán) | 交換結(jié)果 |
|---|---|
| 第一次 | 4，1扯俱，14书蚪，38，26迅栅，9殊校，101，7 |
| 第二次 | 4读存，1为流，14，26让簿，38敬察，9，101拜英，7 |
| 第三次 | 4静汤，1，14居凶，26，9藤抡，38侠碧，101，7 |
| 第四次 | 4缠黍，1弄兜，14，26瓷式，9替饿，38，101贸典，7 |
| 第五次 | 4视卢，1，14廊驼，26据过，9，38妒挎，7绳锅，101 |
至此第一輪交換結(jié)束，次輪交換結(jié)果已經(jīng)將最大的值交換到末尾酝掩。
那么我們開始第二輪循環(huán)
| 第二輪循環(huán) | 交換結(jié)果 |
|---|---|
| 第一次 | 1鳞芙，4，14，26原朝，9闯割，38，7竿拆，101 |
| 第二次 | 1宙拉，4，14丙笋，9谢澈，26，38御板，7锥忿，101 |
| 第三次 | 1，4怠肋，14敬鬓，9，26笙各，7钉答，38，101 |
至此第二輪循環(huán)完成杈抢，接下來依次類推最終我們排序后的數(shù)組內(nèi)容應(yīng)該是：
[1,4,7,9,14,26,38,101];
理論部分演示完畢数尿。
接下來就是代碼部分：
頭腦里面還有了思路之后，我上來就寫了以下代碼：
-(NSArray*)bubbleSort:(NSArray*)array
{
NSInteger execCount = 0;
NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
for (NSInteger i = 0; i < sortArray.count; i++)
{
for (NSInteger j = i + 1; j < sortArray.count; j++)
{
if ([sortArray[i] integerValue] > [sortArray[j] integerValue])
{
[sortArray exchangeObjectAtIndex:i withObjectAtIndex:j];
[self displayArray:sortArray];
execCount++;
}
}
}
NSLog(@"共執(zhí)行了%ld次", execCount);
return sortArray;
}
-(void)displayArray:(NSArray*)array
{
NSMutableString *displayString = [NSMutableString stringWithString:@"["];
for (NSInteger i = 0; i < array.count; i++)
{
i == array.count - 1 ? [displayString appendString:[NSString stringWithFormat:@"%ld", (long)[array[i] integerValue]]] :[displayString appendString:[NSString stringWithFormat:@"%ld%@", (long)[array[i] integerValue], @","]];
}
[displayString appendString:@"]"];
NSLog(@"%@", displayString);
}
代碼執(zhí)行結(jié)果如下：
2019-05-08 01:00:11.814 20190507_sort[14548:4259814] [1,14,4,38,26,9,101,7]
2019-05-08 01:00:11.815 20190507_sort[14548:4259814] [1,4,14,38,26,9,101,7]
2019-05-08 01:00:11.815 20190507_sort[14548:4259814] [1,4,9,38,26,14,101,7]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,38,26,14,101,9]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,26,38,14,101,9]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,14,38,26,101,9]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,9,38,26,101,14]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,9,26,38,101,14]
2019-05-08 01:00:11.817 20190507_sort[14548:4259814] [1,4,7,9,14,38,101,26]
2019-05-08 01:00:11.817 20190507_sort[14548:4259814] [1,4,7,9,14,26,101,38]
2019-05-08 01:00:11.817 20190507_sort[14548:4259814] [1,4,7,9,14,26,38,101]
2019-05-08 01:00:11.817 20190507_sort[14548:4259814] 共執(zhí)行了11次
發(fā)現(xiàn)結(jié)果是對的惶楼，但未按照冒泡定義的順序執(zhí)行右蹦。在第一次循環(huán)完成后101并未到達(dá)最末尾。
好接下來重新修改代碼：
-(NSArray*)bubbleSort:(NSArray*)array
{
NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
NSInteger execCount = 0;//交換次數(shù)
NSInteger forCount = 0;//for循環(huán)總共執(zhí)行了多少次
for (NSInteger i = 0; i < sortArray.count; i++)
{
forCount++;
for (NSInteger j = 0; j < sortArray.count - 1; j++)
{
forCount++;
if ([sortArray[j] integerValue] > [sortArray[j + 1] integerValue])
{
[sortArray exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
execCount++;
[self displayArray:sortArray];
}
}
}
NSLog(@"交換共執(zhí)行了%ld次", execCount);
NSLog(@"for循環(huán)共執(zhí)行了%ld次", forCount);
return sortArray;
}
代碼執(zhí)行結(jié)果如下：
2019-05-08 11:29:36.501 20190507_sort[14910:4308910] [4,1,14,38,26,9,101,7]
2019-05-08 11:29:36.502 20190507_sort[14910:4308910] [4,1,14,26,38,9,101,7]
2019-05-08 11:29:36.502 20190507_sort[14910:4308910] [4,1,14,26,9,38,101,7]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [4,1,14,26,9,38,7,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,14,26,9,38,7,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,14,9,26,38,7,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,14,9,26,7,38,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,9,14,26,7,38,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,9,14,7,26,38,101]
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] [1,4,9,7,14,26,38,101]
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] [1,4,7,9,14,26,38,101]
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] 交換共執(zhí)行了11次
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] for循環(huán)共執(zhí)行了64次
由此可以看到完全符合了冒泡排序的定義的代碼就完成了歼捐，但是各位看官有沒有可以覺得改進(jìn)的地方呢何陆？
//在內(nèi)循環(huán)處我們可以將：
for (NSInteger j = 0; j < sortArray.count - 1; j++)
//修改為
for (NSInteger j = 0; j < sortArray.count - 1 - i; j++)
//因?yàn)槊客瓿梢淮蝺?nèi)循環(huán)，就會將最大的數(shù)排到最后豹储，最后的數(shù)字已經(jīng)是經(jīng)過排序的贷盲，無需再次進(jìn)行排序。
2019-05-08 11:30:46.058 20190507_sort[14933:4310457] [4,1,14,38,26,9,101,7]
2019-05-08 11:30:46.059 20190507_sort[14933:4310457] [4,1,14,26,38,9,101,7]
2019-05-08 11:30:46.059 20190507_sort[14933:4310457] [4,1,14,26,9,38,101,7]
2019-05-08 11:30:46.059 20190507_sort[14933:4310457] [4,1,14,26,9,38,7,101]
2019-05-08 11:30:46.059 20190507_sort[14933:4310457] [1,4,14,26,9,38,7,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,14,9,26,38,7,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,14,9,26,7,38,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,9,14,26,7,38,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,9,14,7,26,38,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,9,7,14,26,38,101]
2019-05-08 11:30:46.061 20190507_sort[14933:4310457] [1,4,7,9,14,26,38,101]
2019-05-08 11:30:46.061 20190507_sort[14933:4310457] 交換共執(zhí)行了11次
2019-05-08 11:30:46.061 20190507_sort[14933:4310457] for循環(huán)共執(zhí)行了36次
//可以看到for循環(huán)執(zhí)行了36次颂翼，比上面的64次大大減少
那我們這個就是完美的了嗎晃洒，肯定不是，我們可以考慮到如果一次循環(huán)根本沒有走任何交換朦乏，那說明排序已經(jīng)按照要求成功了球及，剩下未走完的循環(huán)就不需要了。
//我們需要添加一個變量進(jìn)行控制
-(NSArray*)bubbleSort:(NSArray*)array
{
NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
NSInteger execCount = 0;//交換次數(shù)
BOOL bFlag = YES;//是否已經(jīng)是排序完成
NSInteger forCount = 0;//for循環(huán)總共執(zhí)行了多少次
for (NSInteger i = 0; i < sortArray.count && bFlag; i++)
{
bFlag = NO;
forCount++;
for (NSInteger j = 0; j < sortArray.count - 1 - i; j++)
{
forCount++;
if ([sortArray[j] integerValue] > [sortArray[j + 1] integerValue])
{
[sortArray exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
execCount++;
bFlag = YES;
[self displayArray:sortArray];
}
}
}
NSLog(@"交換共執(zhí)行了%ld次", execCount);
NSLog(@"for循環(huán)共執(zhí)行了%ld次", forCount);
return sortArray;
}
//執(zhí)行結(jié)果如下：
2019-05-08 11:34:16.036 20190507_sort[14963:4312855] [4,1,14,38,26,9,101,7]
2019-05-08 11:34:16.037 20190507_sort[14963:4312855] [4,1,14,26,38,9,101,7]
2019-05-08 11:34:16.037 20190507_sort[14963:4312855] [4,1,14,26,9,38,101,7]
2019-05-08 11:34:16.037 20190507_sort[14963:4312855] [4,1,14,26,9,38,7,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,14,26,9,38,7,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,14,9,26,38,7,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,14,9,26,7,38,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,9,14,26,7,38,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,9,14,7,26,38,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,9,7,14,26,38,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,7,9,14,26,38,101]
2019-05-08 11:34:16.039 20190507_sort[14963:4312855] 交換共執(zhí)行了11次
2019-05-08 11:34:16.039 20190507_sort[14963:4312855] for循環(huán)共執(zhí)行了33次
//可以看到呻疹，沒有添加變量之前是36次吃引，添加了變量是33次，減少了3次
我們繼續(xù)思考，程序還有沒有需要改進(jìn)的地方镊尺，我們程序的健壯性如何朦佩？我們考慮調(diào)用的時候傳進(jìn)來的是空數(shù)組或者數(shù)組只有一個數(shù)據(jù)的情況了嗎？
//我們應(yīng)該在函數(shù)的開始去判斷數(shù)組的狀態(tài)已經(jīng)長度
-(NSArray*)bubbleSort:(NSArray*)array
{
//判斷數(shù)組狀態(tài)
if (!array || array.count == 1)
{
return array;
}
NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
NSInteger execCount = 0;//交換次數(shù)
BOOL bFlag = YES;//是否已經(jīng)是排序完成
NSInteger forCount = 0;//for循環(huán)總共執(zhí)行了多少次
for (NSInteger i = 0; i < sortArray.count && bFlag; i++)
{
bFlag = NO;
forCount++;
for (NSInteger j = 0; j < sortArray.count - 1 - i; j++)
{
forCount++;
if ([sortArray[j] integerValue] > [sortArray[j + 1] integerValue])
{
[sortArray exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
execCount++;
bFlag = YES;
[self displayArray:sortArray];
}
}
}
NSLog(@"交換共執(zhí)行了%ld次", execCount);
NSLog(@"for循環(huán)共執(zhí)行了%ld次", forCount);
return sortArray;
}
至此庐氮，一個相對穩(wěn)定的冒泡算法程序已經(jīng)完成了语稠。
在排序算法中，冒泡排序的算法的時間復(fù)雜度為O(n2)弄砍，這是一個很耗時的算法仙畦，那我們?yōu)槭裁催€要費(fèi)勁去實(shí)現(xiàn)它呢，其實(shí)我們要側(cè)重于它的優(yōu)化過程音婶，思考在自己的項目中代碼能不能進(jìn)一步的優(yōu)化慨畸，代碼是否夠健壯？只有不斷的執(zhí)行一個一個PDCA循環(huán)衣式，才能保證我們代碼的質(zhì)量寸士。
本人小菜一枚，在這里班門弄斧碴卧，拋磚引玉弱卡，文中如果有錯誤的地方請大家指正，共同進(jìn)步螟深！
