选择排序
// 选择排序(升序) 标记最小值，循环比较，替换最小值
- (void)selectSort {
NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]];
for (int i=0; i<arr.count; i++) {
NSNumber *minNum = [arr objectAtIndex:i];
NSInteger minIndex = i;
for (int j=i+1; j<arr.count; j++) {
if ([minNum integerValue] > [[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.count; i++) {
for (int j=0; j<arr.count - 1; j++) {
if ([[arr objectAtIndex:j] integerValue] > [[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.count - 1; i++) {
for (int j=0; j<arr.count - i - 1; j++) {
if ([[arr objectAtIndex:j] integerValue] > [[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<arr.count; i++) {
// 取出一个值
NSInteger min = i;
NSInteger temp = [[arr objectAtIndex:i] integerValue];
[arr removeObjectAtIndex:i];
for (int j=i-1; j>=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，时间复杂度是一样的
