??冒泡排序(BubbleSort)是剛剛接觸編程的時(shí)候就開始接觸的第一個(gè)排序算法

最基礎(chǔ)實(shí)現(xiàn)方式

- (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循環(huán)簡(jiǎn)單粗暴，但是很明顯是可以優(yōu)化的。

優(yōu)化點(diǎn)--當(dāng)隊(duì)列提前變得有序時(shí)，提前結(jié)束循環(huán)

Q:那么如何確定已經(jīng)提前有序了呢？
A:只需要內(nèi)部循環(huán)下來(lái)一次交換都沒有發(fā)生過(guò)，就說(shuō)明此序列已經(jīng)有序，就可以提前結(jié)束了。即在交換中有一個(gè)標(biāo)識(shí)即可。

- (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;
        }
    }
}

既然整體數(shù)列會(huì)提前有序，那么當(dāng)數(shù)列部分有序時(shí)，冒泡排序還傻傻的以步長(zhǎng)1，不斷的進(jìn)行循環(huán)。

優(yōu)化點(diǎn)--當(dāng)隊(duì)列部分有序時(shí)，記錄部分有序的位置，也就是偶爾邁大步子。

Q:那么如何確定下次邁多大步呢呢？
A:只需要記錄最后一次交換的位置，那么此處下標(biāo)減1即為下次邁步到的位置。

- (void)sort
{
    NSInteger count = self.sortArray.count;
    
    NSInteger sortedIndex; // 記錄最后一次交換的位置，即最后一次交換后邊的數(shù)據(jù)肯定是有序的了。下次可以直接把步子邁到這里
    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;
            }
        }
    }
}

總結(jié)：以上為冒泡排序算法相關(guān)的全部?jī)?nèi)容，其中比較與交換操作為了應(yīng)對(duì)所有類型做了方法封裝。