[排序算法一]冒泡排序

2019/04/10 10:10
阅读数 8

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

冒泡排序的特点

  • 时间复杂度:最坏情况O(n^2),最好情况O(n)
  • 排序方式:In-place,不需要额外内存

基本做法(从小到大)

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

avatar

public void Sort1(int[] num)
{
    Console.WriteLine("方法1:");

    var count1 = 0;
    var count2 = 0;

    for (var i = 0; i < num.Length - 1; i++)
    {
        for (var j = i + 1; j < num.Length; j++)
        {
            count1++;
            if (num[i] <= num[j]) continue;

            count2++;
            var temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }

    Console.WriteLine($"结果:{string.Join(",", num)};循环次数:{count1};数据交换次数:{count2}");
}

<b color=red>以上内容,除了代码全部来自网络,盗图请谅解,因为做这么个图是在太难了</b>

通过代码,我们发现,冒泡算法的运行次数其实应该是 (n-1)+(n-2)+(n-3)+...,等于 n(n-1)/2 次,所以得出结论,冒泡算的时间复杂度是O(n^2)

但是,上面介绍不是说有最好的情况下(数据本身就是从小到大排列)时间复杂度是 O(n)吗?

其实,上面的图片介绍和实际算法都存在一些问题,是有可以优化的地方的。

从文字角度上说,既然叫冒泡算法,我们想想水里气泡的形态,一般都是从底部升起到水面,所以,为了更符合实际情况,我们的比较工作应该从数组的尾部开始,把最小(从小到大)的元素慢慢移动到数组的最前的位置。

所以这里先修改一版代码,把比较的顺序倒过来,不是把最大的往后移,而是把最小的往前移

public void Sort2(int[] numbers)
{
    Console.WriteLine("方法2:标准冒泡算法排序");

    var count1 = 0;
    var count2 = 0;

    for (var i = 0; i < numbers.Length; i++)
    {
        for (var j = numbers.Length - 1; j > i; j--)
        {
            count1++;
            if (numbers[j] >= numbers[j - 1]) continue;

            count2++;
            var temp = numbers[j - 1];
            numbers[j-1] = numbers[j];
            numbers[j] = temp;
        }
    }

    Console.WriteLine($"结果:{string.Join(",", numbers)};循环次数:{count1};数据交换次数:{count2}");
}

运行一下,我们会发现,调整后的代码循环的次数和效率跟第一版一模一样,肯定的啊,因为中心思路没变,只是把冒泡的方向倒换了一下而已。

下面,我们考虑这样一个数组:[1,0,2,3,5,4],使用第二版的代码:

第一次循环结束,数组结果为 [<b>0</b>,1,2,3,<b>4</b>,<b>5</b>],很神奇有没有,我们不仅把最小的0冒泡到第一位,顺带的最后两个元素也进行了排序。然后目测一下,数组已经是正序排列了,也就是说这是我们应该可以返回了有木有?

这也就是为什么要从尾部往前冒泡的原因。好了,可以优化的点出现了,接下来,请看第三版代码

public void Sort3(int[] numbers)
{
    Console.WriteLine("方法2:优化版冒泡算法排序");

    var count1 = 0;
    var count2 = 0;

    // 剩下的数据是否需要继续排序标志
    // 因为冒泡排序是从后端两两交换,所以在某种时间点上,后端数据可能已经是排列好的数据
    // 如1,0,2,3,4这种情况,第一次循环后,把0交换到最前,结果为0,1,2,3,4
    // 继续循环1,2,3,4,如果没有进行数据交换操作,说明已经是排序好的,就没必要继续了,直接跳出即可
    var continueFlag = true;

    for (var i = 0; i < numbers.Length && continueFlag; i++)
    {
        // 没有发生数据交换,说明数据已经是排列好的,这时可以跳出循环了
        continueFlag = false;

        for (var j = numbers.Length - 1; j > i; j--)
        {
            count1++;

            if (numbers[j] < numbers[j - 1])
            {
                count2++;
                var temp = numbers[j - 1];
                numbers[j - 1] = numbers[j];
                numbers[j] = temp;

                // 一旦发生数据交换的操作,说明后面的数据并没有排列好,这时需要继续循环
                continueFlag = true;
            }
        }
    }

    Console.WriteLine($"结果:{string.Join(",", numbers)};循环次数:{count1};数据交换次数:{count2}");
}

下面,来进行一个测试:

var bubble = new BubbleSortSample();
var numbers = new int[] {3, 1, 2, 4, 6, 9, 5};
bubble.Sort1(numbers);

Console.WriteLine();

numbers = new int[] { 3, 1, 2, 4, 6, 9, 5 };
bubble.Sort2(numbers);

Console.WriteLine();

numbers = new int[] { 3, 1, 2, 4, 6, 9, 5 };
// 第一次 1,3,2,4,5,6,9,发生了交换,循环了6次
// 第二次 1,2,3,4,5,6,9,发生了交换,循环了5次
// 第三次 检查了一圈,循环了4次,没有发生交换,跳出
bubble.Sort3(numbers);

冒泡排序是一种比较基础而且大家比较熟悉的算法,以前总是知其然而没有深究过,网上很多例子也是如第一版代码一样简单实现演示一下了事,却不知原来这么基础的算法也有这么多的门道在其中,所以说学海无涯...省略一万五千字鸡汤

原文出处:https://www.cnblogs.com/diwu0510/p/12332037.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部