spy 发表于 2015-3-27 16:51:31

Bubble排序算法的优化

#include <stdio.h>
#include <string.h>

#define n 10

void unoptimized_BubbleSort(int a[]);
void BubbleSort(int a[]);
void optimized_BubbleSort(int a[]);
void two_dir_BubberSort(int a[]);

int main()
{
        int a, b = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
//        int a, b = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};
//        int a, b = {0, 1, 2, 3, 4, 9, 6, 7, 8, 5};
//        int a, b = {9, 0, 1, 2, 3, 4, 5, 6, 7, 8};
//        int a, b = {12, 18, 42, 44, 45, 67, 94, 10};
//        int a, b = {94, 10, 12, 18, 42, 44, 45, 67};
//        int a, b = {44, 45, 67, 94, 10};
//        int a, b = {44, 10, 45, 67, 94};
//        int a, b = {8, 7, 6, 5, 4};

        memcpy(a, b, n*sizeof(int));
        unoptimized_BubbleSort(a);

        memcpy(a, b, n*sizeof(int));
        BubbleSort(a);

        memcpy(a, b, n*sizeof(int));
        optimized_BubbleSort(a);

        memcpy(a, b, n*sizeof(int));
        two_dir_BubberSort(a);

        putchar('\n');

        return 0;
}

//未优化的单向冒泡排序算法
void unoptimized_BubbleSort(int a[])
{
        int i, j, temp, count1 = 0, count2 = 0, count3 = 0;

        printf("排序前: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        //轻的气泡上浮
        for ( i = 0; i < n - 1; i++ )
        {
                count1++;

                for ( j = n - 1; j > i; j-- )//由下往上扫描
                {
                        count2++;

                        if ( a < a )
                        {
                                count3++;
                                temp = a;
                                a = a;
                                a = temp;
                        }
                }
        }

/*
        //重的气泡下沉
        for ( i = n-1; i >= 1; i-- )
        {
                count1++;
                for ( j = 0; j < i ; j++ )//由上往下扫描
                {
                        count2++;
                        if ( a > a )
                        {
                                count3++;
                                temp = a;
                                a = a;
                                a = temp;
                        }
                }
        }
*/

        printf("\n排序后: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        printf("\nunoptimized_BubbleSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}

//由下往上扫描的冒泡排序算法
void BubbleSort(int a[])
{
        int i, j, temp, count1 = 0, count2 = 0, count3 = 0, exchange;

        printf("\n排序前: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        for ( i = 0; i < n - 1; i++ )
        {
                count1++;
                exchange = 0;//本趟排序开始前, 交换标志置为0

                for ( j = n - 1; j > i; j-- )//由下往上扫描
                {
                        count2++;

                        if ( a < a )
                        {
                                count3++;
                                temp = a;
                                a = a;
                                a = temp;
                                exchange = 1;//发生了交换, 故将交换标志置为1
                        }
                }

                if ( !exchange )//本趟排序未发生交换, 提前终止算法
                {
                        count1--;
                        break;
                }
        }

        printf("\n排序后: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        printf("\nBubbleSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}

//优化后的单向冒泡排序
void optimized_BubbleSort(int a[])
{
        //采用lastExchange来记录每趟扫描中进行交换的最后一个元素位置,
        //并以lastExchange作为下一趟排序循环终止的控制值

        int i = 0, j, temp, exchange = 1, lastExchange, count1 = 0, count2 = 0, count3 = 0;

        printf("\n排序前: \n");
        for ( j = 0; j < n; j++ )
        {
                printf("%d ", a);
        }

        while ( i < n-1 )
        {
                count1++;
                exchange = 0;
                lastExchange = n - 1;

                for ( j = n-1; j > i; j-- )//由下往上扫描
                {
                        count2++;

                        if ( a < a )
                        {
                                count3++;
                                temp = a;
                                a = a;
                                a = temp;
                                exchange = 1;
                                lastExchange = j;
                        }
                }
                if ( !exchange )
                {
                        count1--;
                }
                i = lastExchange;//将i置为最后交换的位置
        }

        printf("\n排序后: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        printf("\noptimized_BubbleSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}

/*void two_dir_BubberSort(int a[])
{
        int i, j, k, temp, count1 = 0, count2 = 0, count3 = 0, exchange;

        printf("\n排序前: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        i = 0;
        j = n - 1;
        exchange = 1;

        while ( ( i < j ) && exchange )
        {
                count1++;
                k = i++;
                exchange = 0;

                while ( k < j )
                {
                        count2++;
                        if ( a > a )
                        {
                                count3++;
                                temp = a;
                                a = a;
                                a = temp;
                                exchange = 1;
                        }
                        k++;
                }

                if ( exchange )
                {
                        k = --j;
                        while ( k >= i )
                        {
                                count2++;
                                if ( a < a )
                                {
                                        count3++;
                                        temp = a;
                                        a = a;
                                        a = temp;
                                        exchange = 1;
                                }
                                k--;
                        }
                }
                if ( !exchange )
                {
                        count1--;
                }
        }

        printf("\n排序后: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        printf("\ntwo_dir_BubberSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}*/


//双向冒泡排序算法, 在排序过程中交替改变扫描方向
void two_dir_BubberSort(int a[])
{
        int i, k, temp, count1 = 0, count2 = 0, count3 = 0;
        int exchange = 1, lastExchange, lastExchange1 = 0, lastExchange2 = n-1;

        printf("\n排序前: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        while ( exchange )
        {
                count1++;
                k = lastExchange1;
                exchange = 0;

                while ( k < lastExchange2 )//由上往下扫描
                {
                        count2++;

                        if ( a > a )
                        {
                                count3++;
                                temp = a;
                                a = a;
                                a = temp;
                                exchange = 1;
                                lastExchange = k;
                        }

                        k++;
                }

                if ( exchange )
                {
                        lastExchange2 = lastExchange;
                        k = lastExchange2;

                        while ( k > lastExchange1 )//由下往上扫描
                        {
                                count2++;

                                if ( a < a )
                                {
                                        count3++;
                                        temp = a;
                                        a = a;
                                        a = temp;
                                        exchange = 1;
                                        lastExchange = k;
                                }

                                k--;
                        }

                        lastExchange1 = lastExchange;
                }
                else
                {
                        count1--;
                }
        }

        printf("\n排序后: \n");
        for ( i = 0; i < n; i++ )
        {
                printf("%d ", a);
        }

        printf("\ntwo_dir_BubberSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}

逆战时代 发表于 2015-6-5 15:53:07

看看。。。。。。

溯月0503 发表于 2015-6-5 16:56:59

顶一个
页: [1]
查看完整版本: Bubble排序算法的优化