iOS之你写出了一个真正的冒泡排序吗？
2019-05-08 本文已影响0人
乐一游
冒泡排序的定义如下：
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”
比如我们有一个数组
NSArray *array = @[@4, @14, @1, @38, @26, @9, @101, @7];
那么我们按照冒泡排序的定义交换应该如下：
| 第一轮循环 | 交换结果 |
|---|---|
| 第一次 | 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 |
至此第一轮交换结束，次轮交换结果已经将最大的值交换到末尾。
那么我们开始第二轮循环
| 第二轮循环 | 交换结果 |
|---|---|
| 第一次 | 1，4，14，26，9，38，7，101 |
| 第二次 | 1，4，14，9，26，38，7，101 |
| 第三次 | 1，4，14，9，26，7，38，101 |
至此第二轮循环完成，接下来依次类推最终我们排序后的数组内容应该是：
[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(@"共执行了%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);
}
代码执行结果如下：
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] 共执行了11次
发现结果是对的，但未按照冒泡定义的顺序执行。在第一次循环完成后101并未到达最末尾。
好接下来重新修改代码：
-(NSArray*)bubbleSort:(NSArray*)array
{
NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
NSInteger execCount = 0;//交换次数
NSInteger forCount = 0;//for循环总共执行了多少次
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(@"交换共执行了%ld次", execCount);
NSLog(@"for循环共执行了%ld次", forCount);
return sortArray;
}
代码执行结果如下：
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] 交换共执行了11次
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] for循环共执行了64次
由此可以看到完全符合了冒泡排序的定义的代码就完成了，但是各位看官有没有可以觉得改进的地方呢？
//在内循环处我们可以将：
for (NSInteger j = 0; j < sortArray.count - 1; j++)
//修改为
for (NSInteger j = 0; j < sortArray.count - 1 - i; j++)
//因为每完成一次内循环，就会将最大的数排到最后，最后的数字已经是经过排序的，无需再次进行排序。
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] 交换共执行了11次
2019-05-08 11:30:46.061 20190507_sort[14933:4310457] for循环共执行了36次
//可以看到for循环执行了36次，比上面的64次大大减少
那我们这个就是完美的了吗，肯定不是，我们可以考虑到如果一次循环根本没有走任何交换，那说明排序已经按照要求成功了，剩下未走完的循环就不需要了。
//我们需要添加一个变量进行控制
-(NSArray*)bubbleSort:(NSArray*)array
{
NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
NSInteger execCount = 0;//交换次数
BOOL bFlag = YES;//是否已经是排序完成
NSInteger forCount = 0;//for循环总共执行了多少次
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(@"交换共执行了%ld次", execCount);
NSLog(@"for循环共执行了%ld次", forCount);
return sortArray;
}
//执行结果如下：
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] 交换共执行了11次
2019-05-08 11:34:16.039 20190507_sort[14963:4312855] for循环共执行了33次
//可以看到，没有添加变量之前是36次，添加了变量是33次，减少了3次
我们继续思考，程序还有没有需要改进的地方，我们程序的健壮性如何？我们考虑调用的时候传进来的是空数组或者数组只有一个数据的情况了吗？
//我们应该在函数的开始去判断数组的状态已经长度
-(NSArray*)bubbleSort:(NSArray*)array
{
//判断数组状态
if (!array || array.count == 1)
{
return array;
}
NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
NSInteger execCount = 0;//交换次数
BOOL bFlag = YES;//是否已经是排序完成
NSInteger forCount = 0;//for循环总共执行了多少次
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(@"交换共执行了%ld次", execCount);
NSLog(@"for循环共执行了%ld次", forCount);
return sortArray;
}
至此，一个相对稳定的冒泡算法程序已经完成了。
在排序算法中，冒泡排序的算法的时间复杂度为O(n²)，这是一个很耗时的算法，那我们为什么还要费劲去实现它呢，其实我们要侧重于它的优化过程，思考在自己的项目中代码能不能进一步的优化，代码是否够健壮？只有不断的执行一个一个PDCA循环，才能保证我们代码的质量。
本人小菜一枚，在这里班门弄斧，抛砖引玉，文中如果有错误的地方请大家指正，共同进步！
