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

冒泡排序核心思想

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

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

举个小例子：对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 )。

C语言实现

voidbubbleSortUsingC(intarr[],intlen){

// 代表走多少趟，最后一趟就不用再走了

for(inti=0;i<len-1;++i){

// 从后往前走，相当于泡从水底冒出来到水面

for(intj=len-1;j>i;--j){

// 如果后面的比前面一个的值还要小，则需要交换

if(arr[j]<arr[j-1]){

swap(arr,j,j-1);

}

}

}

}

voidswap(intarr[],inti,intj){

inttemp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

测试一下：

inta[5]={5,3,8,6,4};

bubbleSortUsingC(a,sizeof(a)/sizeof(int));

for(inti=0;i<sizeof(a)/sizeof(int);++i){

NSLog(@"%d",a[i]);

}

// 打印: 3, 4, 5, 6, 8 初步如期效果

冒泡排序比较简单，相信大家早就熟记在心！当然，我们要由简单到复杂的学习算法，算法是开发的根本，有了它，开发就有了思想，有了思想就能更轻松解决各种各样的问题了！