交换排序：冒泡排序 （ 相邻比序法 ）(稳定)

冒泡排序是一种简单的交换类排序方法，它是通过相邻的数据元素的交换，逐步将待排序序列变成有序序列的过程。

【 算法思想 】 反复扫描待排序记录序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。
以升序为例：
在第一趟冒泡排序中，从第一个记录开始，扫描整个待排序记录序列，若相邻的两个记录逆序，则交换位置。在扫描的过程中，不断地将相邻两个记录中关键字大的记录向后移动，最后必然将待排序记录序列中的最大关键字记录换到待排序记录序列的末尾，这也是最大关键字记录应在的位置。

然后进行第二趟冒泡排序，对前 n-1 个记录进行同样的操作，其结果是使次大的记录被放在第 n-1 个记录的位置上。

然后进行第三趟冒泡排序，对前 n-2 个记录进行同样的操作，其结果是使第三大的记录被放在第 n-2 个记录的位置上。

如此反复，每一趟冒泡排序都将一个记录排到位，直到剩下一个最小的记录。

若在某一趟冒泡排序过程中，没有发现一个逆序，则可直接结束整个排序过程，所以 冒泡过程最多进行 n-1 趟。

---

C#实现：

冒泡排序版本1：（未考虑，已经有序后，外部循环的中止，外部循环会有多余循环）

public class ChangeSort
{
    /// <summary>
    /// 冒泡排序 版本1：(没有考虑如果已经有序了的情况)
    /// </summary>
    public static void BubbleSort_1(int[] a)
    {
        int len = a.Length;
        int temp = 0;
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < len - 1 - i; j++)
            {
                if (a[j] > a[j + 1])
                {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
                Debug.Log("版本1：内部循环次数");
            }
            Debug.Log("版本1：外部循环次数");
            Utilit.Print(a, i);
        }
    }
}

冒泡排序版本2：考虑的外循环的终止，但内循环次数还可以有更大的减少

public class ChangeSort
{

    /// <summary>
    /// 冒泡排序 版本2：（避免有序后依然进行排序，减少了外循环次数,但没有考虑后方已经有序的情况，例如：[4,3,2,1,0,5,6,7,8,9]）
    /// </summary>
    /// <param name="a"></param>
    public static void BubbleSort_2(int[] a)
    {
        int len = a.Length;
        int temp = 0;

        bool exchang = false; //标志位：是否有逆序相邻数

        for (int i = 0; i < len; i++)
        {
            exchang = false;
            for (int j = 0; j < len-1 - i; j++)
            {
                if (a[j] > a[j + 1])
                {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    exchang = true;
                }
                Debug.Log("版本2：内部循环次数");
            }
            if (!exchang)
            {
                break;
            }
            Debug.Log("版本2：外部循环次数");
            Utilit.Print(a, i);
        }

    }
}

冒泡排序版本3：进一步减少内部循环次数

public class ChangeSort
{

    /// <summary>
    /// 冒泡排序 版本3：（考虑后方已经有序的情况，例如：[4,3,2,1,0,5,6,7,8,9]，减少了内部的循环次数）
    /// </summary>
    /// <param name="a"></param>
    public static void BubbleSort_3(int[] a)
    {
        int len = a.Length;
        int temp = 0;

        int lastExchangIndex = 0;//记录最后发生交换的索引

        int sortBorder = len - 1; //无序数的边界索引

        bool exchang = false; //标志位：是否有逆序相邻数
        for (int i = 0; i < len; i++)
        {
            exchang = false;
            for (int j = 0; j < sortBorder; j++)
            {
                if (a[j] > a[j + 1])
                {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    exchang = true;
                    lastExchangIndex = j;
                }
                Debug.Log("版本3：内部循环次数");
            }
            sortBorder = lastExchangIndex;
            if (!exchang)
            {
                break;
            }
            Debug.Log("版本3：外部循环次数");
            Utilit.Print(a, i);
        }
    }

}

---

测试用例：

---

using UnityEngine;

public class _014_ChangeSort : MonoBehaviour
{

    
    void Start()
    {
        int[] a = Utilit.RandArray(20, 10);//new int[] { 4,3,2,1,0,5,6,7,8,9};

        int[] b = (int[])a.Clone();

        int[] c = (int[])a.Clone();

        Debug.Log("---------------冒泡排序 版本1--------------");
        ChangeSort.BubbleSort_1(a);


        Debug.Log("---------------冒泡排序 版本2--------------");
        ChangeSort.BubbleSort_2(b);

        Debug.Log("---------------冒泡排序 版本3--------------");
        ChangeSort.BubbleSort_3(c);

    }


}

---

测试结果：

img.jpg

---

注：

算法的时间复杂度为 O(n ^2 )，
空间复杂度为 O(1)。

另外，冒泡排序法是一种稳定的排序方法。

image.png