冒泡排序---内附步骤 - C语言论坛

/* 2017年3月13日 16:22:38 冒泡排序经典排序算法 - 冒泡排序Bubble sort原理如下。 */ #include<stdio.h> void sort(int * a, int len) { int i, j; int t; for(i=0; i<len-1; ++i) { for(j=0; j<len-1-i; ++j) { if(a[j]>a[j+1]) { t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } } } int main(void) { int i; int a[6]={6, 9, 7, -8, 3, 0}; sort (a, 6); for(i=0; i<6; ++i) printf("%2d",a[i]); printf("\n"); return 0; } /* -------------- 输出结果为： -8 0 3 6 7 9 Press any key to continue -------------- */ /* --------------------- 简单原理如下：原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换, 这样一趟过去后,最大或最小的数字被交换到了最后一位, 然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子例子为从小到大排序, 原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 | 第一趟排序(外循环) 第一次两两比较6 > 2交换(内循环) 交换前状态| 6 | 2 | 4 | 1 | 5 | 9 | 交换后状态| 2 | 6 | 4 | 1 | 5 | 9 | 第二次两两比较,6 > 4交换交换前状态| 2 | 6 | 4 | 1 | 5 | 9 | 交换后状态| 2 | 4 | 6 | 1 | 5 | 9 | 第三次两两比较,6 > 1交换交换前状态| 2 | 4 | 6 | 1 | 5 | 9 | 交换后状态| 2 | 4 | 1 | 6 | 5 | 9 | 第四次两两比较,6 > 5交换交换前状态| 2 | 4 | 1 | 6 | 5 | 9 | 交换后状态| 2 | 4 | 1 | 5 | 6 | 9 | 第五次两两比较,6 < 9不交换交换前状态| 2 | 4 | 1 | 5 | 6 | 9 | 交换后状态| 2 | 4 | 1 | 5 | 6 | 9 | 第二趟排序(外循环) 第一次两两比较2 < 4不交换交换前状态| 2 | 4 | 1 | 5 | 6 | 9 | 交换后状态| 2 | 4 | 1 | 5 | 6 | 9 | 第二次两两比较,4 > 1交换交换前状态| 2 | 4 | 1 | 5 | 6 | 9 | 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 | 第三次两两比较,4 < 5不交换交换前状态| 2 | 1 | 4 | 5 | 6 | 9 | 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 | 第四次两两比较,5 < 6不交换交换前状态| 2 | 1 | 4 | 5 | 6 | 9 | 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 | 第三趟排序(外循环) 第一次两两比较2 > 1交换交换后状态| 2 | 1 | 4 | 5 | 6 | 9 | 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 第二次两两比较,2 < 4不交换交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 第三次两两比较,4 < 5不交换交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 第四趟排序(外循环)无交换第五趟排序(外循环)无交换排序完毕,输出最终结果1 2 4 5 6 9 --------------------- */

第 2 楼

得分:20

j的值直接为i + 1不就得了，只有进入内循环为j赋值的一次计算。

程序代码：

void sort(int * a, int len)
{
    int i,j;
    int t;

    for( i = 0; i < len; ++i )
        for( j = i + 1; j < len; ++j )
            if( a[ i ] > a[ j ] )
            {
                t = a[ i ];
                a[ i ] = a[ j ];
                a[ j ] = t;
            }
}

你的内循环每次循环都需要2次运算，如果涉及到交换的话，那就是4次运算，所以你的算法并不高效，而且在可读性上也远不及上面的代码。

我对你的代码稍作修改，打印两个次数，一个是内循环次数，一个是内循环中的计算次数。

图片附件: 游客没有浏览图片的权限，请登录或注册

程序代码：

#include<stdio.h>
void sort(int * a, int len)
{
    int i, j;
    int t;
    int x;
    int y;

    for(i=0, x = 0, y = 0; i<len-1; ++i)
    {
        for(j=0; j<len-1-i; ++j,++x)
        {
            y += 2;
            if(a[j]>a[j+1])
            {
                y += 2;
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }
    printf("内循环次数：%d\n",x);
    printf("内循环计算次数:%d\n",y);
}


int main(void)

{
    int i;
    int a[6]={6, 9, 7, -8, 3, 0};
    sort (a, 6);
    for(i=0; i<6; ++i)
        printf("%2d",a[i]);
    printf("\n");
    return 0;
}

以下代码生成1W个随机数，测试两种排序所用的时间，每种算法执行10次。
先给出结果，你的代码是算法2.

图片附件: 游客没有浏览图片的权限，请登录或注册

下面是生成10W个随机数进行排序所花费的时间：

图片附件: 游客没有浏览图片的权限，请登录或注册

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*void sort(int * a, int len)//冒泡排序算法1
{
    int i,j;
    int t;

    for( i = 0; i < len; ++i)
        for( j = i + 1; j < len; ++j )
            if( a[ i ] > a[ j ] )
            {
                t = a[ i ];
                a[ i ] = a[ j ];
                a[ j ] = t;
            }
}
*/

void sort(int * a, int len)//冒泡排序算法2
{
        int i, j;
        int t;
    
        for(i=0; i<len-1; ++i)
        for(j=0; j<len-1-i; ++j)
                if(a[j]>a[j+1])
                {
                    t = a[j];
                    a[j] = a[j+1];
                    a[j+1] = t;
                }
}



int main(void)
{
        int i;
    int j;
        int a[10000];
        clock_t time1;

    for( j = 0; j < 10; ++j )
    {
            time1 = clock();
            srand((unsigned int)time(NULL));
            sort (a, 10000);
            for(i=0; i<10000; ++i)
                a[i] = rand() % 10000;
        
            sort (a, 10000);
            printf("算法2（第%d次）：%.2lf\n",j,(double)(clock() - time1)/CLOCKS_PER_SEC);
    }
    return 0;
}

[此贴子已经被作者于2017-5-7 23:12编辑过]

09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。