冒泡排序(BubbleSort)是刚刚接触编程的时候就开始接触的第一个排序算法
最基础实现方式
- (void)sort
{
NSInteger count = self.sortArray.count;
for (NSInteger end = count - 1; end >= 0; end--) {
for (NSInteger begain = 1; begain <= end; begain++) {
if ([self compareObjcet:self.sortArray[begain] anotherObject:self.sortArray[begain - 1]] == YES) {
[self swapObjectWithIndex:begain anotherIndex:begain - 1];
}
}
}
}
两层for循环简单粗暴，但是很明显是可以优化的。
优化点--当队列提前变得有序时，提前结束循环
Q:那么如何确定已经提前有序了呢？
A:只需要内部循环下来一次交换都没有发生过，就说明此序列已经有序，就可以提前结束了。即在交换中有一个标识即可。
- (void)sort
{
NSInteger count = self.sortArray.count;
for (NSInteger end = count - 1; end >= 0; end--) {
BOOL isSorted = YES;
for (NSInteger begain = 1; begain <= end; begain++) {
if ([self compareObjcet:self.sortArray[begain] anotherObject:self.sortArray[begain - 1]] == YES) {
[self swapObjectWithIndex:begain anotherIndex:begain - 1];
isSorted = NO;
}
}
if (isSorted) {
NSLog(@"end = %ld", end);
break;
}
}
}
既然整体数列会提前有序，那么当数列部分有序时，冒泡排序还傻傻的以步长1，不断的进行循环。
优化点--当队列部分有序时，记录部分有序的位置，也就是偶尔迈大步子。
Q:那么如何确定下次迈多大步呢呢？
A:只需要记录最后一次交换的位置，那么此处下标减1即为下次迈步到的位置。
- (void)sort
{
NSInteger count = self.sortArray.count;
NSInteger sortedIndex; // 记录最后一次交换的位置，即最后一次交换后边的数据肯定是有序的了。下次可以直接把步子迈到这里
for (NSInteger end = count - 1; end > 0; end = sortedIndex - 1) {
sortedIndex = 1;
for (NSInteger begain = 1; begain <= end; begain++) {
if ([self compareObjcet:self.sortArray[begain] anotherObject:self.sortArray[begain - 1]] == YES) {
[self swapObjectWithIndex:begain anotherIndex:begain - 1];
sortedIndex = begain;
}
}
}
}
