算法的穩(wěn)定性：

通俗地講就是能保證排序前2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同。
即假定原數(shù)組2個(gè)相同的元素a[i]和a[j]，在排序前a[i]在a[j]的前面，那么在排序之后，a[i]仍然在a[j]的前面。

定義：

所謂冒泡排序，即是對(duì)于一個(gè)給定長度為n的無序數(shù)組，由初始位置開始， 比較數(shù)組相鄰兩個(gè)元素，如果是逆序排列的，就交換它們的位置， 重復(fù)多次之后，最大數(shù)就“沉”到了最下面的位置。第二次再從初始位置開始，將第二大的元素沉到倒數(shù)第二個(gè)位置。這樣一直做n-1次，整個(gè)數(shù)組就是有序的了。

復(fù)雜度

在第一輪操作結(jié)束之后，第二輪的操作無需比較最后一位，因?yàn)樽詈笠晃灰呀?jīng)是最大的元素了。所以對(duì)于一個(gè)長度為n的數(shù)組，整個(gè)算法消耗的時(shí)間為： (n-1)+(n-2)+…+1=n(n-1)/2， 即時(shí)間復(fù)雜度為O(n^2)。同時(shí)，顯而易見，整個(gè)算法只消耗一份數(shù)組的空間，所以空間復(fù)雜度為O(1)。

穩(wěn)定性

穩(wěn)定排序

總結(jié)

冒泡排序的優(yōu)缺點(diǎn)總結(jié)：
優(yōu)點(diǎn)：
空間復(fù)雜度T=O(1)
穩(wěn)定排序
在排序過程中，整個(gè)數(shù)組趨向穩(wěn)定
對(duì)于已經(jīng)有序的數(shù)組，排序效率高
缺點(diǎn)：

效率低，時(shí)間復(fù)雜度T=O(n^2)，上面提及的優(yōu)化手段很容易失效（最小值在數(shù)組末尾）交換次數(shù)多，交換效率低（每次交換只減少一組逆序?qū)Γ┎荒懿l(fā)執(zhí)行

    /// <summary>
    /// 基礎(chǔ)冒泡排序
    /// </summary>
    /// <param name="array">排序數(shù)組</param>
    void Bubble(int[] array)
    {
        //外層循環(huán)，最后只剩下一個(gè)數(shù)字未排序，自然有序，無需再進(jìn)行排序
        for (int i = 0; i < array.Length - 1; i++)
        {
            //內(nèi)層循環(huán)，已經(jīng)沉底的最大數(shù)不記入內(nè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;
    }

優(yōu)化--添加標(biāo)志位

1.可能存在在某一次排序完成之后，整個(gè)數(shù)組已經(jīng)有序
2.此時(shí)不需要繼續(xù)遍歷，進(jìn)行一定的改良，從而它的性能，但并不會(huì)減弱算法本身的時(shí)間復(fù)雜度
3.設(shè)置標(biāo)志位，如果不再有數(shù)據(jù)交換，則跳出循環(huán)

    /// <summary>
    /// 優(yōu)化排序算法--添加標(biāo)志位
    /// </summary>
    /// <param name="array">排序數(shù)組</param>
    void BubbleOptimize1(int[] array)
    {
        //外層循環(huán)，最后只剩下一個(gè)數(shù)字未排序，自然有序，無需再進(jìn)行排序
        for (int i = 0; i < array.Length - 1; i++)
        {
            //設(shè)置內(nèi)循環(huán)數(shù)據(jù)標(biāo)志
            bool hasSwaped = false;
            //內(nèi)層循環(huán)，已經(jīng)沉底的最大數(shù)不記入內(nèi)
            for (int j = 0; j < array.Length - 1 - i; j++)
            {
                if (array[j] > array[j + 1])
                {
                    Swap(array, j, j + 1);
                    hasSwaped = true;
                }
            }
            //內(nèi)層循環(huán)結(jié)束后沒發(fā)生數(shù)據(jù)變化則證明已經(jīng)有序，直接退出
            if (!hasSwaped) break;
        }
    }

優(yōu)化二

1.其實(shí)在某次排序完成后，下次要排的也是有序的，所以記錄已經(jīng)有序的位置
2.下次遍歷不需在進(jìn)行排

    /// <summary>
    /// 優(yōu)化排序算法--記錄最后一次交換的位置，再次遍歷，只需要到這里即可
    /// </summary>
    /// <param name="array">排序數(shù)組</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;
            // 因?yàn)榇髷?shù)一定是不斷下沉的，所以只要最大數(shù)不在遍歷的終點(diǎn)上，最后一次一定會(huì)執(zhí)行交換、
            // 換言之，若是最后一次交換未執(zhí)行，而是在倒數(shù)第二次處執(zhí)行了交換，一定可以保證倒數(shù)第二個(gè)數(shù)是次大數(shù)
            // 因此可以將倒數(shù)第三個(gè)數(shù)作為下一次交換的終點(diǎn)
            // 依次類推，可以保證[lastSwapPos,array.length-1-i]是有序的，且其中任意一個(gè)數(shù)都比前面的數(shù)字大
            //內(nèi)層循環(huán)，可以由j < array.Length - 1 - i轉(zhuǎn)為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;
        }
    }