冒泡排序

冒泡排序的基本思想： 假设一个待排序列长度为n，从后往前（或从前往后）两两比较元素的值，若为正序则不操作，若为逆序（即A[i-1]>A[i]）则交换它们，直到序列比较完，称为一趟“冒泡”，此时将最小的元素交换到待排序列的第一个位置，也是它的最终位置。下一趟排序时，上一趟确定的最小元素不再参与排序，每趟排序都将序列中最小的元素交换到第一个位置，依次类推，最多进行n-1趟冒泡就能把所有元素排好序。
排序完成的判断条件： 使用flag作为标志位，每趟冒泡前初始为false，若发生元素交换则置为true，在一趟冒泡完成后判断flag值，若为true则继续排序，若为false则说明没有发生元素交换，排序完成。
冒泡排序的性能分析：
空间复杂度：仅进行元素交换需要常数个辅助空间，因此空间复杂度为O(1)。
时间复杂度：当待排序列已经有序时，明显进行一趟冒泡后flag值为false，排序完成，直接结束，比较次数为n-1，移动次数为0；当待排序列逆序时，需要进行n-1趟冒泡，第i趟排序需要进行n-i次比较，每次比较必须移动元素3次以交换位置，在这种情况下，

从而最坏情况下的时间复杂度为O(n²)。平均时间复杂度也为O(n²)。
举例说明冒泡过程：
设一个初始序列为A={10，6，9，3，5，2}
第一趟冒泡结果，A={2，10，6，9，3，5} （元素2到达最终位置）
第二趟冒泡结果，A={2，3，10，6，9，5} （元素3到达最终位置）
第三趟冒泡结果，A={2，3，5，10，6，9} （元素5到达最终位置）
第四趟冒泡结果，A={2，3，5，6，10，9} （元素6到达最终位置）
第五趟冒泡结果，A={2，3，5，6，9，10} （元素9到达最终位置）
此时排序完成
传统冒泡排序算法如下：

#include <stdio.h>
void bubblesort(int a[],int length);
void swap(int a[],int i,int j);
int main()
{
   int array[6]={10,6,9,3,5,2}; /*定义一个数组*/
   int i;
   bubblesort(array,6);
   for(i=0;i<6;i++)
   {
       printf("array[%d]=%dn",i,array[i]); /*输出排序后的数组*/
   }
}
void bubblesort(int a[],int n) /*冒泡排序算法*/
{
    if(n==0||n<2) /*序列长度小于2直接返回*/
        return;
    int i,j,flag;
    for(i=0;i<n;i++) /*外层循环比较的次数*/
    {
        flag=0;
        for(j=n-1;j>i;j--) /*内层循环比较的范围*/
        {
            if(a[j-1]>a[j])
            {
                swap(a,j-1,j);
                flag=1;
            }
        }
        if(flag==0)
            return;
    }
}
void swap(int a[],int i,int j) /*交换元素位置*/
{
    int temp;
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}

运行结果如下图示：