选择排序、冒泡排序、插入排序选择排序、冒泡排序、插入排

选择排序

// 选择排序(升序) 标记最小值，循环比较，替换最小值 - (void)selectSort { NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]]; for (int i=0; i [[arr objectAtIndex:j] integerValue]) { minNum = [arr objectAtIndex:j]; minIndex = j; } } // 替换最小值 [arr replaceObjectAtIndex:minIndex withObject:[arr objectAtIndex:i]]; [arr replaceObjectAtIndex:i withObject:minNum]; } NSLog(@"arr = %@",arr); }

冒泡排序

// 冒泡排序(升序) 相邻2个值进行比较，把最大值移到后面，循环比较 // 原理 - (void)bubblingSort { NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]]; for (int i=0; i [[arr objectAtIndex:j+1] integerValue]) { NSNumber *temp = [arr objectAtIndex:j]; [arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:j+1]]; [arr replaceObjectAtIndex:j+1 withObject:temp]; NSLog(@"%@",arr); } } } NSLog(@"arr = %@",arr); }

如果一个元素比另一个元素大（小），那么就交换这两个元素的位置。重复这一比较直至最后一个元素。这一比较会重复n-1趟，每一趟比较n-j次，j是已经排序好的元素个数。每一趟比较都能找出未排序元素中最大或者最小的那个数字。这就如同水泡从水底逐个飘到水面一样。冒泡排序是一种时间复杂度较高，效率较低的排序方法。

// 最优的冒泡排序 - (void)bubblingSort { NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]]; for (int i=0; i [[arr objectAtIndex:j+1] integerValue]) { NSNumber *temp = [arr objectAtIndex:j]; [arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:j+1]]; [arr replaceObjectAtIndex:j+1 withObject:temp]; NSLog(@"%@",arr); } } } NSLog(@"arr = %@",arr); }

插入排序步骤：

认为第一个是排好的，从下一个位置开始取值
和前面的数值进行比较，找出所取值应该插入的位置
插入
这时取值位置以前的顺序是排好的，重复循环即可

// 插入排序(升序) - (void)insetSort { NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]]; for (int i=1; i=0; j--) { if (temp < [[arr objectAtIndex:j] integerValue]) { min = j; } } // 找出i前面的插入位置 [arr insertObject:[NSNumber numberWithInteger:temp] atIndex:min]; } NSLog(@"%@",arr); }

总结：
【选择排序、冒泡排序、插入排序】选择排序、冒泡排序、插入排序比较次数都是：1+2+3+...+(n-1) = n*n/2，时间复杂度是一样的