冒泡排序及其优化算法（C#）

算法的稳定性：

通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。
即假定原数组2个相同的元素a[i]和a[j]，在排序前a[i]在a[j]的前面，那么在排序之后，a[i]仍然在a[j]的前面。

定义：

所谓冒泡排序，即是对于一个给定长度为n的无序数组，由初始位置开始， 比较数组相邻两个元素，如果是逆序排列的，就交换它们的位置， 重复多次之后，最大数就“沉”到了最下面的位置。第二次再从初始位置开始，将第二大的元素沉到倒数第二个位置。这样一直做n-1次，整个数组就是有序的了。

复杂度

在第一轮操作结束之后，第二轮的操作无需比较最后一位，因为最后一位已经是最大的元素了。所以对于一个长度为n的数组，整个算法消耗的时间为： (n-1)+(n-2)+…+1=n(n-1)/2， 即时间复杂度为O(n^2)。同时，显而易见，整个算法只消耗一份数组的空间，所以空间复杂度为O(1)。

稳定性

稳定排序

总结

冒泡排序的优缺点总结：
优点：
空间复杂度T=O(1)
稳定排序
在排序过程中，整个数组趋向稳定
对于已经有序的数组，排序效率高
缺点：

效率低，时间复杂度T=O(n^2)，上面提及的优化手段很容易失效（最小值在数组末尾）交换次数多，交换效率低（每次交换只减少一组逆序对）不能并发执行

    /// <summary>
    /// 基础冒泡排序
    /// </summary>
    /// <param name="array">排序数组</param>
    void Bubble(int[] array)
    {
        //外层循环，最后只剩下一个数字未排序，自然有序，无需再进行排序
        for (int i = 0; i < array.Length - 1; i++)
        {
            //内层循环，已经沉底的最大数不记入内
            for (int j = 0; j < array.Length - 1 - i; j++)
            {
                if (array[j] > array[j + 1])
                {
                    Swap(array, j, j + 1);
                }
            }
        }
    }
    void Swap(int[] arr, int index1, int index2)
    {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

优化--添加标志位

1.可能存在在某一次排序完成之后，整个数组已经有序
2.此时不需要继续遍历，进行一定的改良，从而它的性能，但并不会减弱算法本身的时间复杂度
3.设置标志位，如果不再有数据交换，则跳出循环

    /// <summary>
    /// 优化排序算法--添加标志位
    /// </summary>
    /// <param name="array">排序数组</param>
    void BubbleOptimize1(int[] array)
    {
        //外层循环，最后只剩下一个数字未排序，自然有序，无需再进行排序
        for (int i = 0; i < array.Length - 1; i++)
        {
            //设置内循环数据标志
            bool hasSwaped = false;
            //内层循环，已经沉底的最大数不记入内
            for (int j = 0; j < array.Length - 1 - i; j++)
            {
                if (array[j] > array[j + 1])
                {
                    Swap(array, j, j + 1);
                    hasSwaped = true;
                }
            }
            //内层循环结束后没发生数据变化则证明已经有序，直接退出
            if (!hasSwaped) break;
        }
    }

优化二

1.其实在某次排序完成后，下次要排的也是有序的，所以记录已经有序的位置
2.下次遍历不需在进行排

    /// <summary>
    /// 优化排序算法--记录最后一次交换的位置，再次遍历，只需要到这里即可
    /// </summary>
    /// <param name="array">排序数组</param>
    void BubbleOptimize2(int[] array)
    {
        int lastSwapPos = array.Length - 1;
        int lastSwapPosTemp = array.Length - 1;
        for (int i = 0; i < array.Length - 1; i++)
        {
            lastSwapPos = lastSwapPosTemp;
            // 因为大数一定是不断下沉的，所以只要最大数不在遍历的终点上，最后一次一定会执行交换、
            // 换言之，若是最后一次交换未执行，而是在倒数第二次处执行了交换，一定可以保证倒数第二个数是次大数
            // 因此可以将倒数第三个数作为下一次交换的终点
            // 依次类推，可以保证[lastSwapPos,array.length-1-i]是有序的，且其中任意一个数都比前面的数字大
            //内层循环，可以由j < array.Length - 1 - i转为lastSwapPos
            for (int j = 0; j < lastSwapPos; j++)
            {
                if (array[j] > array[j + 1])
                {
                    Swap(array, j, j + 1);
                    lastSwapPosTemp = j;
                }
            }
            //一次都未交换，直接退出
            if (lastSwapPosTemp == lastSwapPos) break;
        }
    }