[開心IT面試題] 冒泡排序

1、基本思想

將數組劃分為有序區和無序區，不斷通過交換將較大元素移至無序區尾。若在某一趟排序中未發生交換事件時，或無序區已全部排序完時，則排序完畢。

2、最優情況

（待排序數組是正序）只用比較一次就行了。復雜度O(n)。

3、最差情況

（待排序數組是逆序）要比較n^2次才行，復雜度O(n^2)。

4、冒泡排序屬於穩定的排序。最壞時間復雜度O(n^2)，空間復雜度O(1)。

5、代碼

將elem[]數組按遞增進行冒泡排序

void BubbleSort(int *elem, int elemLen)
{
    if(elem == NULL || elemLen == 0)
    {
        return;
    }
    bool isExchange = false;//標記是否有交換數據操作
    int tempElem = 0;//交換元素時，需要用到的臨時中間變量
    for(int i = 0; i < elemLen; i++)
    {
        isExchange = false;//每趟排序前交換標記為假
        for(int j = 1; j < elemLen-i; j++)
        {
            //比較兩元素，將較大元素交換到後面
            if(elem[j-1] > elem[j])
            {
                tempElem = elem[j-1];
                elem[j-1] = elem[j];
                elem[j] = tempElem;
                isExchange = true;//已有交換操作，交換標記為真
            }
        }
        if(!isExchange)
        {
            break;
        }
    }
}