冒泡排序

冒泡排序算法的基本思想是：

　　假设待排表长为n，从后往前两两比较相邻元素的值，若为逆序，则交换他们，知道序列比较完。我们称它为一趟冒泡排序，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟的结果把序列中的最小元素放到了序列的最终位置上，……，这样最多n-1趟冒泡就能把所有元素排序好。

代码如下：

 1 void BubbleSort(ElemType A[],int n)
 2 {
 3     int i,j;
 4     bool flag;//记录是否有交换
 5     ElemType temp;//临时元素
 6     for(i=0;i<n-1;i++)
 7     {
 8         flag=false;//初始化
 9         for(j=n-1;j>i;--j)
10         {
11             if(A[j].key<A[j-1].key)//判断
12             {
13                 temp = A[j];
14                 A[j]=A[j-1];
15                 A[j-1]=temp;
16 
17                 flag=true;
18             }
19         }//一趟冒泡结束
20         if(flag==false)//在上一趟冒泡中没有交换发生，说明整个序列已经有序
21             return;
22     }
23 }

代码分析：

插图

如图，每一趟冒泡排序结束后，i向下移动一位，而j回溯到n-1;继续下一趟的冒泡，每次序列的规模减小1。最多，当j==i时候，退出，然而，为了不必要的比较，当某一趟冒泡排序后发现没有交换，则说明序列已经有序。

性能分析：

1、空间复杂度O(1)，用到一个辅助空间进行交换。

2、时间复杂度，最坏的情况O(n^2)，即逆序的时候;最好的情况O(n)，顺序的时候。

稳定性：稳定