算法一冒泡排序

柔情只为你懂 2022-05-12 04:34 183阅读 0赞

# 何为冒泡？ #

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

# 算法原理： #

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

# 时间复杂度： #

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 ![b3b7d0a20cf431ad4f379a864936acaf2fdd98ac.jpg][] 和记录移动次数![48540923dd54564e27333d86b1de9c82d1584f3f.jpg][] 均达到最小值：![78310a55b319ebc4b8a3a8268026cffc1f1716b1.jpg][] , ![b21c8701a18b87d6007472a0050828381f30fd5f.jpg][] ,所以，冒泡排序最好的[时间复杂度][Link 1]为 ![b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg][] 。若初始文件是反序的，需要进行 ![8b82b9014a90f60364df45f83b12b31bb051ed26.jpg][] 趟排序。每趟排序要进行![503d269759ee3d6d1214597441166d224e4adebb.jpg][] 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

![838ba61ea8d3fd1f846a7b85324e251f95ca5f2a.jpg][]

![7af40ad162d9f2d36fa2fd50abec8a136227ccda.jpg][]

冒泡排序的最坏时间复杂度为

![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][] ，综上，因此冒泡排序总的平均时间复杂度为 ![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][]

好了，基本就是这么回事。下面不多说，直接上代码。

c++版：

#include <iostream>
    using namespace std;
    template<typename T>
    //整数或浮点数皆可使用
    void bubble_sort(T arr[], int len)
    {
        int i, j;  T temp;
        for (i = 0; i < len - 1; i++)
            for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
    }
    int main()
    {
        int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        bubble_sort(arr, len);
        for (int i = 0; i < len; i++)
            cout << arr[i] << ' ';
     
        cout << endl;
     
        float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
        len = (int) sizeof(arrf) / sizeof(*arrf);
        bubble_sort(arrf, len);
        for (int i = 0; i < len; i++)
            cout << arrf[i] << ' ';
     
        return 0;
    }

[b3b7d0a20cf431ad4f379a864936acaf2fdd98ac.jpg]: https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D12/sign=5e6ca6622c738bd4c021b633a08bb91b/b3b7d0a20cf431ad4f379a864936acaf2fdd98ac.jpg
[48540923dd54564e27333d86b1de9c82d1584f3f.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D16/sign=c765e07cd5ca7bcb797bc329bf09e8ac/48540923dd54564e27333d86b1de9c82d1584f3f.jpg
[78310a55b319ebc4b8a3a8268026cffc1f1716b1.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D84/sign=c4f5a2db0b23dd542573aa6cd0090824/78310a55b319ebc4b8a3a8268026cffc1f1716b1.jpg
[b21c8701a18b87d6007472a0050828381f30fd5f.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D66/sign=1745c99097cad1c8d4bbff217e3e11cd/b21c8701a18b87d6007472a0050828381f30fd5f.jpg
[Link 1]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D33/sign=feddd1e257fbb2fb302b5e114e4a94f7/b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg
[8b82b9014a90f60364df45f83b12b31bb051ed26.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D32/sign=411c7ed7d309b3deefbfe26acdbf0492/8b82b9014a90f60364df45f83b12b31bb051ed26.jpg
[503d269759ee3d6d1214597441166d224e4adebb.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D30/sign=3af139940cf41bd5de53eef450da752f/503d269759ee3d6d1214597441166d224e4adebb.jpg
[838ba61ea8d3fd1f846a7b85324e251f95ca5f2a.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D171/sign=f38fc3a1bb389b503cffe455b434e5f1/838ba61ea8d3fd1f846a7b85324e251f95ca5f2a.jpg
[7af40ad162d9f2d36fa2fd50abec8a136227ccda.jpg]: https://gss0.bdstatic.com/94o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D186/sign=41bfe6dab119ebc4c4787291b427cf79/7af40ad162d9f2d36fa2fd50abec8a136227ccda.jpg
[e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D40/sign=17b28fa860d0f703e2b294dc09fa9d5c/e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg