C# 实现冒泡排序

假设现有一数组，如下

基本排序代码如下

static void Main(string[] args)
{
    int[] myarray = new int[] { 6, 5, 8, 7, 1, 2, 3, 5 };//替换代码
    BaseSort(myarray, 0, 7);//替换代码
    
    for(int i = 0; i < myarray.Length; i++)
    {
        Console.Write(myarray[i] + " ");
    }
    Console.ReadLine();
}
public static void BaseSort(int[] array, int start, int end)
{
    for(int i = start; i < end; i++)
    {
        if(array[i] > array[i + 1])
        {
            int temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }
}

1. 将替换代码换成下列代码，并输出数组

int[] myarray = new int[] { 6, 5, 8, 7, 1, 2, 3, 5 };
BaseSort(myarray, 0, 7);

2. 将替换代码换成下列代码，并输出数组

int[] myarray = new int[] { 5, 6, 7, 1, 2, 3, 5, 8 };
BaseSort(myarray, 0, 6);

3. 将替换代码换成下列代码，并输出数组

int[] myarray = new int[] { 5, 6, 1, 2, 3, 5, 7, 8 };
BaseSort(myarray, 0, 5);

4. 将替换代码换成下列代码，并输出数组

int[] myarray = new int[] { 5, 1, 2, 3, 5, 6, 7, 8 };
BaseSort(myarray, 0, 4);

5. 将替换代码换成下列代码，并输出数组

int[] myarray = new int[] { 1, 2, 3, 5, 5, 6, 7, 8 };
BaseSort(myarray, 0, 3);

6. 将替换代码换成下列代码，并输出数组

int[] myarray = new int[] { 1, 2, 3, 5, 5, 6, 7, 8 };
BaseSort(myarray, 0, 2);

7. 将替换代码换成下列代码，并输出数组

int[] myarray = new int[] { 1, 2, 3, 5, 5, 6, 7, 8 };
BaseSort(myarray, 0, 1);

至此，数组的值按从小到大进行排列。

1. 冒泡算法每一次排序，会将最大(最小)的值排出去。总共需要排出最大值(最小值) array.Length - 1 次。
2. 第一次冒泡，会比较 array.Length - 1 次。
3. 第二次冒泡，会比较 array - Length - 1 - 1 次。
4. 第三次冒泡，会比较 array - Length - 1 - 2 次。

代码如下

static void Main(string[] args)
{
    int[] myarray = new int[] { 6, 5, 8, 7, 1, 2, 3, 5 };
    BubbleSort(myarray);

    for (int i = 0; i < myarray.Length; i++)
    {
        Console.Write(myarray[i] + " ");
    }
    Console.ReadLine();
}

//冒泡排序
public static void BubbleSort(int[] array)
{
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = 0; j < array.Length - 1 - i; j++)
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

加哨兵的冒泡排序算法：数组中没有交换的时候，说明已经排序完成。

public static void BubbleSort(int[] array)
{
    bool isNoChange = true;
    for (int i = 0; i < array.Length; i++, isNoChange = true)
    {
        for (int j = 0; j < array.Length - 1 - i; j++)
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isNoChange = false;
            }
        }

        if(isNoChange)
        {
            break;
        }
    }
}

对于优化后的哨兵冒泡排序算法而言

• 最优时间复杂度：数组已经排序完成，只需要一次【for】循环 (即 n - 1 次) 进行大小的比较。
• 最差时间复杂度：数组倒序排序，一共比较1 + 2 + 3 + … + (n - 1)次，利用等差数列求和公式得((n - 1) * n) / 2 次
• 平均时间复杂度：(不知道怎么计算，求大佬在评论区解答…)
• 空间复杂度：需要借助 temp 变量用来交换数组中的两个值。
• 稳定性：经过冒泡排序之后，后面相同的数(如：5) 不会因为此次排序而导致顺序在前面。

因为作者精力有限，文章中难免出现一些错漏，敬请广大专家和网友批评、指正。