Bubble排序算法的优化

spy

#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[n], b[n] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
//        int a[n], b[n] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};
//        int a[n], b[n] = {0, 1, 2, 3, 4, 9, 6, 7, 8, 5};
//        int a[n], b[n] = {9, 0, 1, 2, 3, 4, 5, 6, 7, 8};
//        int a[n], b[n] = {12, 18, 42, 44, 45, 67, 94, 10};
//        int a[n], b[n] = {94, 10, 12, 18, 42, 44, 45, 67};
//        int a[n], b[n] = {44, 45, 67, 94, 10};
//        int a[n], b[n] = {44, 10, 45, 67, 94};
//        int a[n], b[n] = {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[i]);
        }

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

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

                        if ( a[j] < a[j-1] )
                        {
                                count3++;
                                temp = a[j];
                                a[j] = a[j-1];
                                a[j-1] = temp;
                        }
                }
        }

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

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

        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[i]);
        }

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

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

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

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

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

        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[j]);
        }

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

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

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

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

        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]);
        }

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

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

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

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

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

        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[i]);
        }

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

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

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

                        k++;
                }

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

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

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

                                k--;
                        }

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

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

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

逆战时代

看看。。。。。。

溯月0503

顶一个