[排序算法一]冒泡排序

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

冒泡排序的特点

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

基本做法（从小到大）

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

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

以上内容，除了代码全部来自网络，盗图请谅解，因为做这么个图是在太难了

通过代码，我们发现，冒泡算法的运行次数其实应该是 (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]，使用第二版的代码：

第一次循环结束，数组结果为 [0,1,2,3,4,5]，很神奇有没有，我们不仅把最小的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++)
    {
        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;
            }
            else
            {
                // 没有发生数据交换，说明数据已经是排列好的，这时可以跳出循环了
                continueFlag = false;
            }
        }
    }

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

下面是运行结果：

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