论坛 › 全国大学生数学建模竞赛(CUMCM) › 关于冒泡算法的那些事儿

杨利霞 发表于 2020-5-5 14:19

关于冒泡算法的那些事儿

关于冒泡算法的那些事儿排序算法的复杂度



关于冒泡算法你了解多少：
首先我们规定数据如下
5 8 6 3 9 1 1 7

在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
vector nums;
//或
vector& nums;
，则这样写：
if nums.size() == 0:
return false
方法二：
如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums)
然后判断数组为空：
if nums_length == 0:
return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

解决了上述问题以后，最原始的冒泡排序如下

#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
                {
                        if (a > a)
                        {
                                temp = a;
                                a = a;
                                a = temp;
                        }
                }
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
        int a = { 5,8,6,3,9,1,1,7 };
        int b = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
                {
                        if (a > a)
                        {
                                temp = a;
                                a = a;
                                a = temp;
                                flag=0;
                        }
                }
                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
        int a = { 5,8,6,3,9,1,1,7 };
        int b = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a > a)
                        {
                                temp = a;
                                a = a;
                                a = temp;
                                flag=0;
                last_exchange=j;
                        }
                }
                Bubble_Sort_border=last_exchange;
                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
        int a = { 3,4,2,1,5,6,7,8 };
        int b = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}


到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做

鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下


#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a > a)
                        {
                                temp = a;
                                a = a;
                                a = temp;
                                flag=0;               
                        }
                }
                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a < a)
                        {
                                temp = a;
                                a = a;
                                a = temp;
                                flag=0;               
                        }
                }
                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
        int a = { 3,4,2,1,5,6,7,8 };
        int b = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}


以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524

查看完整版本: 关于冒泡算法的那些事儿