起泡排序

起泡排序属于交换排序的一种，排序过程中小的元素不断“上浮”（交换到数组前面位置），就如同水里的气泡逐步冒出水面一样，故称为“起泡法”或“冒泡法”。

题目描述

给出一组数据，根据由小到大顺序输出。

输入要求：

输入一个整数n（数据长度）
输入n个数据

输出要求：

输出由小到大排序后的数据

样例输入：

10
37 28 46 19 55 28 92 84 63 71

样例输出：

19 28 28 37 46 55 63 71 84 92

基本思想

假设待排序的数据都存放在数组R[n]中，并想象将数组垂直树立，每次将相邻的两个元素比较，把小的元素调到前面，一趟排序后，最大的元素已放到了数组最后（沉底），小的元素向前一个位置（上浮），按此规律进行下去，直到没有反序记录为止。

参考代码（C语言）

#include<stdio.h>
void bubble_sort(int R[],int n); //起泡排序 

int main()
{
	int i,R[100],n;	
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%d",&R[i]);
	bubble_sort(R,n);
	return 0;
} 

void bubble_sort(int R[],int n)
{
	int i,j,t;
	for(i=0;i<n-1;i++)	//一共进行n-1趟循环
		for(j=0;j<n-i;j++)	//每次循环进行n-i次比较
		if(R[j]>R[j+1])		//小的元素调到前面
		{
			t=R[j];
			R[j]=R[j+1];
			R[j+1]=t;
		}
	for(i=0;i<n;i++)
	printf("%d ",R[i]);
}

分析总结

起泡排序的平均算法复杂度为O($n^2$)
因为一直是相邻元素的比较和交换，所以很显然，起泡排序是稳定的。

有的书中起泡排序是从下向上扫描的，这样最小的元素最先置顶，大的元素一步步下沉，总体思路还是差不多的，一般情况下，个人还是喜欢从上向下，小的元素一点点上浮，感觉更有冒泡的意思。当然，对于有些序列采用从上向下和从下向上有很大差异。

对于9 0 1 2 3 4 5 6 7 8
采用从上向下的扫描方式，仅需1趟就可完成排序，而从下向上则需要9趟排序
对于1 2 3 4 5 6 7 8 9 0
采用从下向上的扫描方式，仅需1趟就可完成排序，而从上向下则需要9趟排序

所以起泡排序可以改进，其一，可以改变扫描方向，如同上述两个例子，不同的扫描方向，可以极大提升排序效率；其二，可以记录每趟最后发生交换的位置k，下一趟扫描终止在位置k即可，因为没有发生交换就证明已经有序，所以不必再扫描到位置n-i。

写在最后

代码的表达形式多种多样，重点是理解排序的思想和过程，附上一个网上看到的动画，可以帮助理解排序过程☛链接在此（个人觉得如果有一些基础的看本文上面给的图示去理解最好，更有助于建立编程的思维，视频能相对有些趣味性）
说明： 链接内视频不是本人制作，如侵权则删。当然网上的视频有很多，我只是找了一个相对简单明了的，大家也可自行搜索。

参考资料:《数据结构-用C语言描述》高等教育出版社
     《C程序设计（第四版）》谭浩强著.清华大学出版社

（只是分享个人学习时的想法和理解，如有问题还望大佬指点）