【背景】
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
【源码运行环境】
操作系统：Windows 10
编译环境：Dev C++(基于C99标准)
【基本思想】
两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止
【动态图解】
【源码实现】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | /**方法名：swap*作用：交换数组两个位置的元素 *参数：待查找数组 array; 起始位置 i ; 结束位置 j; *返回值：void*Author: WellLee*最后一次修改时间：2018年12月6日 22:18:55 */void swap(int array[], int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp;}/**方法名：BubbleSort *作用：冒泡排序粗暴版 *参数：待查找数组 array; 数组长度length; *返回值：void*Author: WellLee*最后一次修改时间：2018年12月6日 22:18:55 */void BubbleSort(int array[], int length){ int i,j; for(i = 1; i < length; i++) { for(j = length - 1 ; j >= i; j--) { if(array[j] > array[j+1]){ swap(array,j,j+1); } } } }/**方法名：BubbleSort_2*作用：冒泡排序优化版 *参数：待查找数组 array; 数组长度length; *返回值：void*Author: WellLee*最后一次修改时间：2018年12月6日 22:18:55 */void BubbleSort_2(int array[],int length){ int i,j; int flag = 1; for(i = 1; i < length && flag == 1; i++) { flag = 0; for(j = length -1; j >= i; j--) { if(array[j] > array[j+1]) { swap(array,j,j+1); flag = 1; } } }} |
【分析】
冒泡排序最好的情况就是表本身有序，那么根据改进版的代码此时的比较次数为( n – 1) 次比较，没有数据交换，时间复杂度为O(n)；当最坏的情况，即待排序表逆序，此时需要比较
【参考文献】
-
《大话数据结构》.程杰.清华大学出版社