冒泡排序核心思想
算法最讲究的就是算法的思想，只要将算法思想想明白了，就可以通过伪代码来写出算法，那么再使用对应的语言来实现就可以了。
冒泡排序的核心思想就是通过与相邻元素的比较和交换，把小的数交换到最前面。因为这个过程类似于水泡向上升一样，因此被命名为冒泡排序。
举个小例子：对5,3,8,6,4这个无序序列进行冒泡排序。
首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6.这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。
其过程大概是这样的：
第一趟：
5, 3, 8, 6, 4 （开始）
5, 3, 8, 4, 6 （6和4交换）
5, 3, 4, 8, 6 （8和4交换）
5, 3, 4, 8, 6 （3和4不用交换）
3, 5, 4, 8, 6 （5和3交换）
第二趟：
3, 5, 4, 6, 8 （8和6交换）
3, 5, 4, 6, 8 （4和6不用交换）
3, 4, 5, 6, 8 （5和4交换）
3, 4, 5, 6, 8 （3和4不用交换）
这里只需要两趟就可以排序完成了。
时间复杂度
从算法思想可知，冒泡排序需要两个循环来控制遍历，也就是需要n * n趟才能判断、交换完成。
冒泡排序的时间复杂度为O ( n2 )。
伪代码
void bubbleSort(int a[], int len) {
for i = 0; i < len - 1; ++i {
for j = len - 1; j > i; --j {
if a[j] < a[j - 1] {
swap(a, j, j - 1);
}
}
}
}
void swap(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
C语言版
void bubbleSortUsingC(int arr[], int len) {
// 代表走多少趟，最后一趟就不用再走了
for (int i = 0; i < len - 1; ++i) {
// 从后往前走，相当于泡从水底冒出来到水面
for (int j = len - 1; j > i; --j) {
// 如果后面的比前面一个的值还要小，则需要交换
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
}
}
}
}
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
测试一下：
int a[5] = {5,3,8,6,4};
bubbleSortUsingC(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
NSLog(@"%d", a[i]);
}
// 打印: 3, 4, 5, 6, 8 初步如期效果
ObjC版
- (void)bubbleSort:(int [])array len:(size_t)len {
for (size_t i = 0; i < len - 1; ++i) {
for (size_t j = len - 1; j > i; --j) {
if (array[j] < array[j - 1]) {
// 交换
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
}
测试使用：
int a[5] = {5,3,8,6,4};
[self bubbleSort:a len:sizeof(a) / sizeof(int)];
for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
NSLog(@"%d", a[i]);
}
Swift版
func bubbleSort(var arr: [Int]) ->[Int] {
// 走多少趟
for var i = 0; i < arr.count - 1; ++i {
// 从后往前
for var j = arr.count - 1; j > i; --j {
// 后者 < 前者 ？ 交换 ： 不交换
if arr[j] < arr[j - 1] {
let temp = arr[j]
arr[j] = arr[j - 1]
arr[j - 1] = temp
}
}
}
return arr
}
测试使用：
// 由于swift中数组也是结构体，是值类型，因此需要接收返回值才能得到排序后的数组
var arr = [5, 3, 8, 6, 4]
arr = bubbleSort(arr)
print(arr)
尝试给Model排序
- (void)bubbleSort:(NSMutableArray *)array {
for (NSUInteger i = 0; i < array.count - 1; ++i) {
for (NSUInteger j = array.count - 1; j > i; --j) {
HYBTestModel *modelj = [array objectAtIndex:j];
HYBTestModel *modelj_1 = [array objectAtIndex:j - 1];
// 前者 < 后者 ？ 交换 ： 不交换
if ([modelj.uid compare:modelj_1.uid options:NSCaseInsensitiveSearch] == NSOrderedAscending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j - 1];
}
}
}
}
测试：
NSMutableArray *array = [[NSMutableArray alloc] init];
for (NSUInteger i = 0; i < 10; ++i) {
HYBTestModel *model = [[HYBTestModel alloc] init];
model.title = [NSString stringWithFormat:@"标哥的技术博客：%ld", 10 - (i + 1)];
model.uid = [NSString stringWithFormat:@"%ld", 10 - (i + 1)];
[array addObject:model];
}
[self bubbleSort:array];
for (HYBTestModel *model in array) {
NSLog(@"%@ %@", model.uid, model.title);
}
// 打印:
2016-03-10 22:57:37.524 DataAgorithmDemos[96148:3779265] 0 标哥的技术博客：0
2016-03-10 22:57:37.526 DataAgorithmDemos[96148:3779265] 1 标哥的技术博客：1
2016-03-10 22:57:37.526 DataAgorithmDemos[96148:3779265] 2 标哥的技术博客：2
2016-03-10 22:57:37.526 DataAgorithmDemos[96148:3779265] 3 标哥的技术博客：3
2016-03-10 22:57:37.582 DataAgorithmDemos[96148:3779265] 4 标哥的技术博客：4
2016-03-10 22:57:37.588 DataAgorithmDemos[96148:3779265] 5 标哥的技术博客：5
2016-03-10 22:57:37.589 DataAgorithmDemos[96148:3779265] 6 标哥的技术博客：6
2016-03-10 22:57:37.593 DataAgorithmDemos[96148:3779265] 7 标哥的技术博客：7
2016-03-10 22:57:37.594 DataAgorithmDemos[96148:3779265] 8 标哥的技术博客：8
2016-03-10 22:57:37.596 DataAgorithmDemos[96148:3779265] 9 标哥的技术博客：9
说明排序正常的~