面试宝典 | 冒泡排序详解
冒泡排序在面试里面被考得不多，因为冒泡排序的性能并不好，平均时间复杂度是O(n²)，实际应用并不多；其次，冒泡排序逻辑简单，如果人人都会的话，对于面试官来说就没有太多考试的必要，不能体现区分度。
但是我们还是需要了解其算法原理，只有清楚其原理、特性，才能知道每个算法的优势、劣势。万一面试官就是考这么简单的题目，而你没有答上来，岂不是很懊恼。赶快一起学习吧！
冒泡排序（Bubble Sort）要重复地走访过待排序的数列，一次比较两个元素，如果他们的大小顺序错误就把他们交换过来，直到排序完成。
以将数组按从小到大排序举例说明。冒泡排序有两种比较方法，一种是从前向后比较，一种是从后向前比较。以从前向后排序举例。
初始序列：
4 5 2 1
第一趟：
4 5 2 1 → 4 5 2 1 （4 < 5，不交换）
4 5 2 1 → 4 2 5 1 （5 > 2，交换）
4 2 5 1 → 4 2 1 5 （5 > 1，交换）
第一趟排序结束后，数字5被放到最终位置上。
第二趟：
4 2 1 5 → 2 4 1 5 （4 > 2，交换）
2 4 1 5 → 2 1 4 5 （4 > 1，交换）
第二趟排序结束后，数字4被放到最终位置上。
第三趟：
2 1 4 5 → 1 2 4 5 （2 > 1，交换）
第三趟排序结束后，数字2被放到最终位置上，数组变为有序，排序结束。
void bubbleSort(int A[],int n){for(int i=0; i<n-1; i++){ // 共进行n-1趟冒泡for(int j=0; j<n-i-1; j++){ //从前向后比较if(A[j]>A[j+1]){int tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;} // if} // for} // for} // BubbleSort
def bubbleSort(arr):for i in range(1, len(arr)):for j in range(0, len(arr) - i):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr
func bubbleSort(arr []int) []int {length := len(arr)for i := 0; i < length; i++ {for j := 0; j < length-1-i; j++ {if arr[j] > arr[j+1] {arr[j], arr[j+1] = arr[j+1], arr[j]}}}return arr}
function bubbleSort(arr) {var len = arr.length;for (var i = 0; i < len - 1; i++) {for (var j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j+1]) {var temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;}}}return arr;}
PS：其他语言的代码实现非辣条妹擅长领域，就不班门弄斧了，建议大家去搜其他博客。
最好的情况，数组初始状态就是排序后的最终状态，时间复杂度为O(n)；最坏情况，数组初始状态是逆序，时间复杂度为O(n²)；平均情况时间复杂度为O(n²)。
是的。
冒泡排序属于比较类排序中的交换类排序，交换类排序中还有一个快速排序，面试中考得更多，下期即将推送。