冒泡排序：
首先是最熟悉常见的冒泡排序。顾名思义，就像气泡一样，依次将最大(小)值往上浮，直到适当的位置为止。下面看一组无序的数据，使用冒泡排序将其变为有序的。
现有一组无序的数字组成的数组，使用冒泡排序进行排序：
- 37, 33, 24, 4, 58, 35, 40, 98, 76, 82
| 排序前 | 37, 33, 24, 4, 58, 35, 40, 98, 76, 82 |
|---|---|
| 第 1 次排序 | 33, 24, 4, 37, 35, 40, 58, 76, 82, 【98】 |
| 第 2 次排序 | 24, 4, 33, 35, 37, 40, 58, 76, 【82, 98】 |
| 第 3 次排序 | 4, 24, 33, 35, 37, 40, 58, 【76, 82, 98】 |
| 第 4 次排序 | 4, 24, 33, 35, 37, 40, 【58, 76, 82, 98】 |
| 第 5 次排序 | 4, 24, 33, 35, 37, 【40, 58, 76, 82, 98】 |
| 第 6 次排序 | 4, 24, 33, 35, 【37, 40, 58, 76, 82, 98】 |
| 第 7 次排序 | 4, 24, 33, 【35, 37, 40, 58, 76, 82, 98】 |
| 第 8 次排序 | 4, 24, 【 33, 35, 37, 40, 58, 76, 82, 98】 |
| 第 9 次排序 | 4, 【 24, 33, 35, 37, 40, 58, 76, 82, 98】 |
| 排序后 | 4, 24, 33, 35, 37, 40, 58, 76, 82, 98 |
OC代码实现：
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *values = @[@37,@33,@24,@4,@98,@76,@82,@58,@35,@40].mutableCopy;
NSLog(@"排序前： %@", values);
[self bubbleSort:values];
NSLog(@"排序后： %@", values);
}
- (void)bubbleSort:(NSMutableArray *)values {
for (int i=0; i<values.count - 1; i++) {
for (int j=0; j<values.count - i - 1; j++) {
NSNumber *jValue = values[j];
NSNumber *jUpValue = values[j+1];
if(jValue.integerValue > jUpValue.integerValue){
[values exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
NSLog(@"第 %d 次排序： %@", i+1, values);
}
}
从上面列表来看，第一次排序完成最大值98浮出，第二次排序82，98浮出。就像气泡一样一个一个浮出，到最后排序完成。可以看出，冒泡排序的效率很低，平均与最快的时间复杂度都是O(n2)。
其实上面的排序已经使用了右端左移的方法来改进单纯的冒泡排序了。单纯的冒泡排序代码如下：
- (void)lowBubbleSort:(NSMutableArray *)values {
for (int i=0; i<values.count; i++) {
for (int j=i; j<values.count; j++) {
NSNumber *jValue = values[j];
NSNumber *iValue = values[i];
if(iValue.integerValue > jValue.integerValue){
[values exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
NSLog(@"第 %d 次排序： %@", i+1, values);
}
}
再仔细看表格中打印的排序信息，其实在第三次排序结束后，数组中的元素已经是从小到大有序的了，第四次已经没有进行元素的交换了。所以可以对排序算法再稍加优化，使用flag标记元素下标是否进行交替。代码如下：
- (void)fastBubbleSort:(NSMutableArray *)values {
BOOL flag = YES;
for (int i=0; i<values.count - 1 && flag == YES; i++) {
flag = NO;
for (int j=0; j<values.count - i - 1; j++) {
NSNumber *jValue = values[j];
NSNumber *jUpValue = values[j+1];
if(jValue.integerValue > jUpValue.integerValue){
[values exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
flag = YES;
}
}
NSLog(@"第 %d 次排序： %@", i+1, values);
}
}
打印的排序信息如下：
| 排序前 | 37, 33, 24, 4, 58, 35, 40, 98, 76, 82 |
|---|---|
| 第 1 次排序 | 33, 24, 4, 37, 35, 40, 58, 76, 82, 【98】 |
| 第 2 次排序 | 24, 4, 33, 35, 37, 40, 58, 76, 【82, 98】 |
| 第 3 次排序 | 4, 24, 33, 35, 37, 40, 58, 【76, 82, 98】 |
| 第 4 次排序 | 4, 24, 33, 35, 37, 40, 【58, 76, 82, 98】 |
| 排序后 | 4, 24, 33, 35, 37, 40, 58, 76, 82, 98 |
以上就是冒泡排序了，还想对冒泡排序继续优化可以见接下来的更新 Shaker 排序法 - 改良的冒泡排序
选择排序：
将排序对象分为两部分，一个是已排序的，一个是未排序的，在未排序的元素中选取最小(大)的元素放入已排序元素的最后一个。还是将上面那组未排序的数组，使用选择排序进行排序。
| 排序前 | 37,33,24,4,58,35,40,98,76,82 |
|---|---|
| 第 1 次排序 | 【4】,33,24,37,58,35,40,98,76,82 |
| 第 2 次排序 | 【4,24】,33,37,58,35,40,98,76,82 |
| 第 3 次排序 | 【4,24,33】,37,58,35,40,98,76,82 |
| 第 4 次排序 | 【4,24,33,35】,58,37,40,98,76,82 |
| 第 5 次排序 | 【4,24,33,35,37】,58,40,98,76,82 |
| 第 6 次排序 | 【4,24,33,35,37,40】,58,98,76,82 |
| 第 7 次排序 | 【4,24,33,35,37,40,58】,98,76,82 |
| 第 8 次排序 | 【4,24,33,35,37,40,58,76】,98,82 |
| 第 9 次排序 | 【4,24,33,35,37,40,58,76,82】,98 |
| 排序后 | 4,24,33,35,37,40,58,76,82,98 |
OC代码实现
- (void)selectSort:(NSMutableArray *)values {
for (int i=0; i<values.count - 1; i++) {
NSInteger index = i;
for (int j=i; j<values.count; j++) {
NSNumber *indexValue = values[index];
NSNumber *jValue = values[j];
if(indexValue.integerValue > jValue.integerValue){
index = j;
}
}
[values exchangeObjectAtIndex:i withObjectAtIndex:index];
NSLog(@"第 %d 次排序： %@", i+1, values);
}
}
插入排序
插入排序也是将排序对象分为两部分，一般将第一个元素作为一部分，然后将后面的元素依次插入第一部分的合适位置，直到排序完成。排序过程看下面表格：
| 排序前 | 37,33,24,4,58,35,40,98,76,82 |
|---|---|
| 第 1 次排序 | 【33,37】,24,4,58,35,40,98,76,82 |
| 第 2 次排序 | 【24,33,37】,4,58,35,40,98,76,82 |
| 第 3 次排序 | 【4,24,33,37】,58,35,40,98,76,82 |
| 第 4 次排序 | 【4,24,33,37,58】,35,40,98,76,82 |
| 第 5 次排序 | 【4,24,33,35,37,58】,40,98,76,82 |
| 第 6 次排序 | 【4,24,33,35,37,40,58】,98,76,82 |
| 第 7 次排序 | 【4,24,33,35,37,40,58,98】,76,82 |
| 第 8 次排序 | 【4,24,33,35,37,40,58,76,98】,82 |
| 第 9 次排序 | 【4,24,33,35,37,40,58,76,82,98】 |
| 排序后 | 4,24,33,35,37,40,58,76,82,98 |
OC代码实现
- (void)insertSort:(NSMutableArray *)values {
for (int i=1; i < values.count; i++) {
id iValue = values[i];
int j = i-1;
for (j=i-1; j >= 0 && iValue < values[j]; j--) {
[values exchangeObjectAtIndex:j+1 withObjectAtIndex:j];
}
[values replaceObjectAtIndex:j+1 withObject:iValue];
NSLog(@"第 %d 次排序： %@", i, values);
}
}
总结：选择、插入、冒泡排序算法时间复杂度都是O(n2)。是比较容易理解的排序算法，但是效率不高。接下来会持续更新“Shell 排序法 - 改良的插入排序”、 “Shaker 排序法 - 改良的气泡排序”。
demo github地址
网友评论