排序算法一：冒泡排序

最简单，最常用的排序方法之一。冒泡排序是稳定的，相同的值的相对位置在排序后没有改变。时间复杂度O（n^2）。
冒泡排序的代码及其改进版：

/*****************************************************
     File name:1bubble.c

 Author: Tang Zhiqian

  Date:2017-08-07 17:07
*****************************************************/

#include <stdio.h>

#define MAX 10

typedef int ElemenType;
typedef ElemenType ARR[MAX];    //给数组另起名字
int len = sizeof(ARR)/sizeof(ElemenType);    //数组长度

void swap(ElemenType arr[],int i,int j);    //交换函数
void print(ARR arr);    //打印
void bubble1(ARR arr);    //未改进的冒泡排序
void bubble2(ARR arr);    //改进后的冒泡排序

int main()
{
    ARR arr1 = {9,0,1,2,3,4,5,6,7,8};
    ARR arr2 = {9,0,1,2,3,4,5,6,7,8};

    printf("\n未改进的冒泡排序：\n");
    bubble1(arr1);

    printf("\n");

    printf("改进后的冒泡排序：\n");
    bubble2(arr2);


    return 0;
}

void bubble1(ARR arr)
{
    int i,j;

    for (i = 0; i < len - 1; i++)
    {
        for (j = 0; j < len - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr,j,j+1);
            }
        }
        print(arr);
    }
}

void bubble2(ARR arr)
{
    int i,j;
    int flag = 1;

    for (i = 0; i < len - 1; i++)
    {
        flag = 0;
        for (j = 0; j < len - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])    
            {
                flag = 1;     //进入这个判断，flag = 1；
                swap(arr,j,j+1);
            }
        } 
        if (flag == 0)    //如果flag等于零，说明上一次循环没有交换位置，说明排序已经完成，则break
        {
            break;
        }
        print(arr);
    }
}


void  print(ARR arr)
{
    int i;
    for (i = 0; i < len; i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
}

void swap(ElemenType arr[],int i,int j)
{
    ElemenType temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

程序运行结果：

在这里我们看到，未改进的bubble1排序，输出了9行排好序的数，而改进过的bubble2只输出了一行。未排序前的数字顺序为{9，0，1，2，3，4，5，6，7，8}，观察发现，其实经过一轮冒泡之后，这个数组就已经排好序了，但是程序不知道是否排好序，所以会一直循环完。 但是在bubble2中我添加了一个flag，进入第一个for循环就让flag=0，第二级for循环中if判断下flag= 1，假设二级for循环一圈后都没有进入到if里面，则flag = 0，说明这时候数组已经排好序了，因为它一轮比较之后都没有进入if里面执行swap函数。这样下来电脑就少执行了很多次 比较 的过程。