Introduction
The bubble algorithm is a basic sorting algorithm that repeatedly compares two adjacent elements in the array. If one element is larger (small) than the other element, then the positions of the two elements are exchanged. Repeat this comparison until the last element. This comparison will be repeated n-1 times, and each time is compared n-j times, j is the number of elements that have been sorted. Each comparison can find the largest or smallest number in the unsorted element. It's like bubbles floating from the bottom of the water to the surface. Bubble sorting is a sorting method with high time complexity and low efficiency. Its space complexity is O(n).
1, Worst time complexity O(n^2)
2, Average time complexity O(n^2)
Implementation ideas
1. Each comparison compares the sizes of two adjacent elements in the array.
2. If the i element is less than the i-1 element, change the position of the two elements.
3. Comparison of repeated n-1 trips
Objective-C example:
+(void)bubbleSort:(NSMutableArray *)list{
if ( <= 1) {
return;
}
int i, y;
BOOL bFinish = YES; //Whether data exchange occurs for (i = 1; i<= [list count] && bFinish; i++) {
bFinish = NO; //Reset the flag every time you traverse //From the last digit, compared with the previous digit in turn, if it is smaller, then swap positions //When there is no data exchange in one traversal, it means that the sorting has been completed (bFinish=YES), and no looping will be performed. for (y = (int)[list count]-1; y>=i; y--) {
if ([[list objectAtIndex:y] intValue] < [[list objectAtIndex:y-1] intValue]) {
//Switch location// NSLog(@"%d<->%d",[[array objectAtIndex:y-1] intValue],[[array objectAtIndex:y] intValue]);
[list exchangeObjectAtIndex:y-1 withObjectAtIndex:y];
bFinish = YES; // Data exchange occurs, continue the next traversal until no data exchange occurs or the loop is completed
// NSLog(@"%@",[array componentsJoinedByString:@" "]);
}
}
}
}