转载

冒泡排序

序言

本篇一起来学习冒泡排序的算法，它可是面试中经常会问到的哦，而且挺常使用的。今天跟大家一起来回忆回忆大学那些年所学过的冒泡排序算法。

本篇将会使用C语言、ObjC和Swift分别来实现冒泡排序，并通过ObjC来举一个模型类冒泡排序的小例子，希望对大家在开发中应用算法有所帮助。

冒泡排序核心思想

算法最讲究的就是算法的思想，只要将算法思想想明白了，就可以通过伪代码来写出算法，那么再使用对应的语言来实现就可以了。

冒泡排序的核心思想就是通过与相邻元素的比较和交换，把小的数交换到最前面。因为这个过程类似于水泡向上升一样，因此被命名为冒泡排序。

举个小例子：对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.这样一次冒泡就完了，把最小的数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(n ^2)。

伪代码

  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 [])arraylen:(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}; [selfbubbleSort:alen:sizeof(a) / sizeof(int)]; for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {     NSLog(@"%d", a[i]); }

Swift版

  funcbubbleSort(vararr: [Int]) ->[Int] {   // 走多少趟   forvar i = 0; i < arr.count - 1; ++i {          // 从后往前     forvar j = arr.count - 1; j > i; --j {              // 后者 < 前者 ？ 交换 ： 不交换       if arr[j] < arr[j - 1] {         lettemp = arr[j]                  arr[j] = arr[j - 1]         arr[j - 1] = temp       }     }   }      return arr }

测试使用：

  // 由于swift中数组也是结构体，是值类型，因此需要接收返回值才能得到排序后的数组 vararr = [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 = [arrayobjectAtIndex:j];       HYBTestModel *modelj_1 = [arrayobjectAtIndex:j - 1];              // 前者 < 后者 ？ 交换 ： 不交换       if ([modelj.uidcompare:modelj_1.uidoptions:NSCaseInsensitiveSearch] == NSOrderedAscending) {         [arrayexchangeObjectAtIndex:jwithObjectAtIndex:j - 1];       }     }   } }

测试：

  NSMutableArray *array = [[NSMutableArray alloc]init]; for (NSUInteger i = 0; i < 10; ++i) {   HYBTestModel *model = [[HYBTestModel alloc]init];   model.title = [NSStringstringWithFormat:@"标哥的技术博客：%ld", 10 - (i + 1)];   model.uid = [NSStringstringWithFormat:@"%ld", 10 - (i + 1)];      [arrayaddObject:model]; }   [selfbubbleSort: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

说明排序正常的~

最后

坚持看到这里，还不能掌握冒泡排序吗？不会的，我相信你一定可以吸收的！算法才是开发的根本，有了它，开发就有了思想，有了思想就能更轻松解决各种各样的问题了！

关注我

关注	账号	备注
标哥博客iOS交流群一	324400294（满）	群一若已满，请申请群二
标哥博客iOS交流群二	494669518（满）	群二若已满，请申请群三
标哥博客iOS交流群三	461252383（满）	群三若已满，请申请群四
标哥博客iOS交流群四	250351140	群四若已满，会有提示信息
关注微信公众号	iOSDevShares	关注微信公众号，会定期地推送好文章
关注新浪微博账号	标哥的技术博客	关注微博，每次发布文章都会分享到新浪微博
关注标哥的GitHub	CoderJackyHuang	这里有很多的Demo和开源组件
关于我	进一步了解标哥	如果觉得文章对您很有帮助，可捐助我！