酷应用

iOS算法总结-冒泡排序

百家作者：iOS开发 2017-10-21 14:48:18

点击上方“iOS开发”，选择“置顶公众号”

关键时刻，第一时间送达！

冒泡排序（Bubble Sort）: 一种交换排序，它的基本思想是：两两比较相邻的关键字，如果反序则交换，直到没有反序的记录为止。

平实写冒泡排序，我都是这么写的：

- (void)logArray {
NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
for (int i = 0; i < arr.count; i++) {
for (int j = i+1; j < arr.count; j++) {
if (arr[i] < arr[j]) {
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
[self logArr:arr];
}
}
//打印数组
- (void)logArr:(NSMutableArray * )array {
NSString * str = @"";
for (NSNumber * value in array) {
str = [str stringByAppendingString:[NSString stringWithFormat:@"%zd ",[value integerValue]]];
}
NSLog(@"%@",str);
}
//打印结果如下
16 1 2 9 7 12 5 3 8 13 10
16 13 1 2 7 9 5 3 8 12 10
16 13 12 1 2 7 5 3 8 9 10
16 13 12 10 1 2 5 3 7 8 9
16 13 12 10 9 1 2 3 5 7 8
16 13 12 10 9 8 1 2 3 5 7
16 13 12 10 9 8 7 1 2 3 5
16 13 12 10 9 8 7 5 1 2 3
16 13 12 10 9 8 7 5 3 1 2
16 13 12 10 9 8 7 5 3 2 1
16 13 12 10 9 8 7 5 3 2 1

查了定义后发现，这不算是标准的冒牌排序算法，因为它不满足“两两比较相邻”的冒泡排序思想，它更应该是最最简单的交换排序而已。它的思路是让每个关键字，都和它后面的一个关键字比较，如果小则交换。

它应该算是最容易写的排序代码了，不过这个简单易懂的代码是有缺陷的，观察后发现，每次排序只能确定一个位置，直到倒数第二次末尾的最小值1才显示到最后，也就是说，这个算法的效率是非常低的。

正宗的冒泡排序算法：

- (void)logArrayFunction {
int count = 0;
int forcount = 0;
NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;

for (int i = 0; i < arr.count; i++) {
forcount++;
for (int j = (int)arr.count-2; j >= i; j--) {
count++;
if (arr[j] < arr[j+1]) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
[self logArr:arr];
}
NSLog(@"循环次数：%d",forcount);
NSLog(@"共%d次比较",count);
}
//打印如下
16 13 1 2 9 7 12 5 3 8 10
16 13 12 1 2 9 7 10 5 3 8
16 13 12 10 1 2 9 7 8 5 3
16 13 12 10 9 1 2 8 7 5 3
16 13 12 10 9 8 1 2 7 5 3
16 13 12 10 9 8 7 1 2 5 3
16 13 12 10 9 8 7 5 1 2 3
16 13 12 10 9 8 7 5 3 1 2
16 13 12 10 9 8 7 5 3 2 1
16 13 12 10 9 8 7 5 3 2 1
16 13 12 10 9 8 7 5 3 2 1
循环次数：11
共55次比较

冒泡排序的优化：

设想如果待排序的序列是{2,1,3,4,5,6,7,8,9}，也就是说，2和1交换后就属于正常的排序结果了，但是之后的大量比较还是大大多余了。为了不再继续后面的循环判断工作，我们需要改进下代码，增加个BOOL变量flag来实现这一算法的改进。

- (void)logArrayFunctionNice {
int count = 0;
int forcount = 0;
BOOL flag = YES;
NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;

for (int i = 0; i < arr.count && flag; i++) {
forcount++;
flag = NO;
for (int j = (int)arr.count-2; j > i; j--) {
count++;
if (arr[j] < arr[j+1]) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
flag = YES;
}
}
[self logArr:arr];
}
NSLog(@"循环次数：%d",forcount);
NSLog(@"共%d次比较",count);
}
//打印
16 13 1 2 9 7 12 5 3 8 10
16 13 12 1 2 9 7 10 5 3 8
16 13 12 10 1 2 9 7 8 5 3
16 13 12 10 9 1 2 8 7 5 3
16 13 12 10 9 8 1 2 7 5 3
16 13 12 10 9 8 7 1 2 5 3
16 13 12 10 9 8 7 5 1 2 3
16 13 12 10 9 8 7 5 3 1 2
16 13 12 10 9 8 7 5 3 2 1
16 13 12 10 9 8 7 5 3 2 1
循环次数：10
共45次比较