有一个无序数组,用冒泡排序法将其排成有序数组
NSMutableArray * array = [[NSMutableArray alloc]initWithObjects:@"31",@"22",@"51",@"3",@"2",@"1",@"4", nil];
冒泡排序的思想:
第一次比较:
1.将index=0和index=1的值进行比较,
2.如果index=0 > index=1,则互换他俩的位置
3.如果index0 < index=1, 则数组保持不变
4.以此类推,第二次比较的两个值为 index1 和 index2
5.需要比较 array.count-1趟
以下为最简单的冒泡排序代码
#pragma mark 冒泡排序
- (NSMutableArray *)bubbleSortWithArray:(NSMutableArray *)array
{for (int i = 0; i < array.count -1 ; i++){for (int j = 0; j < array.count -1 -i; j++){if ([array[j] intValue] > [array[j+1] intValue]){//互换位置[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];}}}return array;
}
但是还可以再优化:如果一个数组排到第2趟就已经有序,则不需要再排下去(增加时间复杂度)
不需要排下去的一句就是 不需要互换位置,我们可以设定一个值来检测是否需要换位置,如果不需要再换,则可以跳出循环:
#pragma mark 冒泡排序
- (NSMutableArray *)bubbleSortWithArray:(NSMutableArray *)array
{for (int i = 0; i < array.count -1; i ++){//默认不需要换位置BOOL isChange = NO;for (int j = 0; j < array.count - 1 -i; j ++){if ([array[j] intValue] > [array[j +1 ] intValue]){//需要换位置isChange = YES;[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];}}//循环完一趟,如果不需要换位置,则说明这个数组已经是有序的if (isChange == NO){break;}}return array;
}