算法---3.冒泡排序

1. 冒泡排序
由小到大排序的过程
第一趟相当于找到最小值并放在首位，
    第1个数与剩下的n-1个数比较，若有比第1个数小的就交换，让第1个数始终存本趟最小的数
第二趟相当于找到次小值，并放在第2的位置上
      第2个数与剩下的n-2个数比较，若有比第2个数小的就交换，让第2个数始终存本趟最小的数
以此类推
1.2 代码

#include <stdio.h>
#include <stdlib.h>
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
#define SWAP(x,y) (x=(x)+(y),y=(x)-(y),x=(x)-(y))

int dump_arry(int* arr, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        //printf("%d=%d ", i, arr[i]);
        printf("%d  ", arr[i]);
    }
    printf("\n");
    return 0;
}
//由小到大进行排序
int bubble_sort(int* arr, int len)
{
    int i, j;
    for(i=0; i<len; i++)
    {
        dbmsg("i=%d",i);
        for(j=i+1; j<len; j++)
        {
            if(arr[j] < arr[i])         //arr[i]存放最小的数，如果后面的数比arr[i]还小
                SWAP(arr[j], arr[i]);   //则交换，让arr[i]始终存放这一趟中最小的数
        }
        dump_arry(arr, len);
    }
}

int main ( int argc, char *argv[] )
{
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int len = sizeof(arr)/sizeof(int);
    dbmsg("len=%d", len);
    dbmsg("before bubble:");
    dump_arry(arr, len);

    bubble_sort(arr, len);    //由小到大进行排序

    dbmsg("after bubble:");
    dump_arry(arr, len);
    return EXIT_SUCCESS;
}

1.3 运行结果

bubble.c:main[38]: len=10
bubble.c:main[39]: before bubble:
49  38  65  97  76  13  27  49  55  4
bubble.c:bubble_sort[23]: i=0
4  49  65  97  76  38  27  49  55  13            -->第1趟把最小值4放在了最前面，同时n-1的数也有变化
bubble.c:bubble_sort[23]: i=1
4  13 65  97  76  49  38  49  55  27            -->第2趟把次小值133放在了本趟的是前面，同时n-2的数也有变化
bubble.c:bubble_sort[23]: i=2
4  13  27  97  76  65  49  49  55  38
bubble.c:bubble_sort[23]: i=3
4  13  27  38  97  76  65  49  55  49
bubble.c:bubble_sort[23]: i=4
4  13  27  38  49  97  76  65  55  49
bubble.c:bubble_sort[23]: i=5
4  13  27  38  49  49  97  76  65  55
bubble.c:bubble_sort[23]: i=6
4  13  27  38  49  49  55  97  76  65
bubble.c:bubble_sort[23]: i=7
4  13  27  38  49  49  55  65  97  76
bubble.c:bubble_sort[23]: i=8
4  13  27  38  49  49  55  65  76  97
bubble.c:bubble_sort[23]: i=9
4  13  27  38  49  49  55  65  76  97
bubble.c:main[42]: after bubble:
4  13  27  38  49  49  55  65  76  97

1.4 性能
O(n2)
1.5 代码打包
bubble.rar  (下载后改名为bubble.tar.gz)

---

2.1 改进
上述算法有一个问题:如果是己排序好的数据，还要一个个的比较
所以为了避免这样，加了一个标志位，当检测到己排好序之后就直接跳出循环
如果这趟没有数据交换说明己排序好

2.2 代码
代码插入不了，格式很难看
#include
#include
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
#define SWAP(x,y) (x=(x)+(y),y=(x)-(y),x=(x)-(y))


int dump_arry(int* arr, int len)
{
    int i;
    for(i=0; i     {
        //printf("%d=%d ", i, arr[i]);
        printf("%d  ", arr[i]);
    }
    printf("\n");
    return 0;
}


int bubble_sort(int* arr, int len)
{
    int i, j;
    int flag;
    for(i=0; i     {
        flag = 1;
        dbmsg("arr[%d]=%d",i, arr[i]);
        for(j=i+1; j         {
            if(arr[j] < arr[i])
            {
                flag = 0;
                SWAP(arr[j], arr[i]);
            }
            dbmsg("arr[%d]=%d",i, arr[i]);
        }
        dump_arry(arr, len);
        if(1 == flag)
            break;
    }
}


int main ( int argc, char *argv[] )
{
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int arr[] = {4, 13, 27, 38, 49, 49, 55, 65, 76, 97};
    int len = sizeof(arr)/sizeof(int);
    dbmsg("len=%d", len);
    dbmsg("before bubble:");
    dump_arry(arr, len);
    bubble_sort(arr, len);
    dbmsg("after bubble:");
    dump_arry(arr, len);
    return EXIT_SUCCESS;
}
代码插入不了，格式很难看


2.3 代码打包
bubble2.rar(下载后改名为bubble2.tar.gz)