冒泡排序及优化——C语言实现

依次比较相邻的数据，将小数据放在前，大数据放在后；即第一趟先比较第1个和第2个数，大数在后，小数在前，再比较第2个数与第3个数，大数在后，小数在前，以此类推则将最大的数"滚动"到最后一个位置；第二趟则将次大的数滚动到倒数第二个位置......第n-1(n为无序数据的个数)趟即能完成排序。
 

#include 

void bubble_sort(int arr[],int sz)
{
    int i = 0,j=0,tmp=0;

    for (i = 0; i < sz-1; i++)//确定趟数
    {
        for(j=0; j arr[j + 1])
            {
                //交换
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }

    }

}

int main()
{
    int arr[]= {1,4,2,8,6,3,9,5,7,5};
    int i = 0;
    int ret = sizeof(arr)/sizeof(arr[0]);

    bubble_sort(arr,ret);
    for(i=0; i 
运行结果 
1234556789
Process returned 0 (0x0)   execution time : 0.012 s
Press any key to continue.
 
  
 冒泡算法的外层控制比较的趟数，如果有n个数字进行排序，那么需要比较n-1趟；内部循环进行比较。但是，在某些情况下，我们进行一定次数的排序后，发现已经有序了，则不必进行剩余的比较，跳出循环即可。
 
所以可以对代码进行一定的优化：
 
优化 
#include 

void bubble_sort(int arr[],int sz)
{
    int i = 0,j=0,tmp=0;
    for (i = 0; i < sz-1; i++)//确定趟数
    {
        int flag=1;//代码优化，置1

        for(j=0; j arr[j + 1])
            {
                //交换
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
                flag=0;//如果发生了交换就对flag置0
            }
        }
        if(flag==1)
        {
            break;//如果falg还是1，说明没有发生交换，此时已经有序，所以直接跳出循环
        }

    }

}

int main()
{
    int arr[]= {1,4,2,8,6,3,9,5,7,5};
    int i = 0;
    int ret = sizeof(arr)/sizeof(arr[0]);

    bubble_sort(arr,ret);
    for(i=0; i