簡介
冒泡算法是一種基礎(chǔ)的排序算法，這種算法會(huì)重復(fù)的比較數(shù)組中相鄰的兩個(gè)元素。如果一個(gè)元素比另一個(gè)元素大（小），那么就交換這兩個(gè)元素的位置。重復(fù)這一比較直至最后一個(gè)元素。這一比較會(huì)重復(fù)n-1趟，每一趟比較n-j次，j是已經(jīng)排序好的元素個(gè)數(shù)。每一趟比較都能找出未排序元素中最大或者最小的那個(gè)數(shù)字。這就如同水泡從水底逐個(gè)飄到水面一樣。冒泡排序是一種時(shí)間復(fù)雜度較高，效率較低的排序方法。其空間復(fù)雜度是O(n)。
1, 最差時(shí)間復(fù)雜度 O(n^2)
2, 平均時(shí)間復(fù)雜度 O(n^2)
實(shí)現(xiàn)思路
1，每一趟比較都比較數(shù)組中兩個(gè)相鄰元素的大小
2，如果i元素小于i-1元素，就調(diào)換兩個(gè)元素的位置
3，重復(fù)n-1趟的比較
Objective-C示例：
+(void)bubbleSort:(NSMutableArray *)list{ if (list.count <= 1) { return; } int i, y; BOOL bFinish = YES; //是否發(fā)生數(shù)據(jù)交換 for (i = 1; i<= [list count] && bFinish; i++) { bFinish = NO; //每次遍歷時(shí)，重置標(biāo)志 //從最后一位開始，依次跟前一位相比，如果較小，則交換位置 //當(dāng)一次遍歷沒有任何數(shù)據(jù)交換時(shí)，則說明已經(jīng)排序完成(bFinish=YES)，則不再進(jìn)行循環(huán) for (y = (int)[list count]-1; y>=i; y--) { if ([[list objectAtIndex:y] intValue] < [[list objectAtIndex:y-1] intValue]) { //交換位置// NSLog(@"%d<->%d",[[array objectAtIndex:y-1] intValue],[[array objectAtIndex:y] intValue]); [list exchangeObjectAtIndex:y-1 withObjectAtIndex:y]; bFinish = YES; //發(fā)生數(shù)據(jù)交換，則繼續(xù)進(jìn)行下一次遍歷，直到未發(fā)生數(shù)據(jù)交換或者循環(huán)完成為止// NSLog(@"%@",[array componentsJoinedByString:@" "]); } } }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
