冒泡排序

算法思路

• 升序排列:
  • 從左到右(或右到左)比較相鄰的元素,如果目前元素比下一個元素大(或者小),就交換他們兩個。

  • 對下一對相鄰元素做同樣的工作,從開始第一對到結尾的最後一對,本輪排序完成後得到無序部分中的最大元

    素,此時這個最大元素和之前的已經排序的部分,組成新的有序部分

  • 針對所有的無序元素重複以上的步驟,直到某一輪沒有發生元素交換則說明排序完成
• 降序排列:
  • 從左到右(或右到左)比較相鄰的元素,如果目前元素比下一個元素小(或者大),就交換他們兩個。

  例:使冒泡法升序排列8,1,6,3,2,4

  從左到右進行排序:

  第一輪:

  

  第二輪:

  

  第三輪:

  

  第四輪:

  

  本輪中沒有發生元素交換,就表示剩下的元素都是有序的,是以所有元素已經都是有序的了。

代碼實作

bool BubbleSort(int * pUnSortAry, int nArySize)
{
  if (pUnSortAry == nullptr || nArySize <= 0)
  {
    return false;
  }

  bool bFlag = false;
  for (int iIndex = 0; iIndex < nArySize; iIndex++)
  {
    for (int jIndex = 0; jIndex < nArySize - iIndex -1; jIndex++)
    {
      if (pUnSortAry[jIndex] > pUnSortAry[jIndex + 1])
      {
        int nTemp = pUnSortAry[jIndex];
        pUnSortAry[jIndex] = pUnSortAry[jIndex + 1];
        pUnSortAry[jIndex + 1] = nTemp;
        bFlag = true;
      }
    }

    if (!bFlag)
    {
      break; //如果記憶體for循環中一次交換也沒有發生,則說明所有元素已經有序
    }
  }
  return true;
}
      

測試代碼:

void PrintData(int*pAry, int nSize)
{
  for (int jIndex = 0; jIndex < nSize; jIndex++)
  {
    printf("%d ", pAry[jIndex]);
  }
  printf("\r\n");
}

int main()
{
  srand(time(NULL));

  int nArry[20] = { 0 };

  for (int jIndex = 0; jIndex < 10; jIndex++)
  {
    for (int iIndex = 0; iIndex < sizeof(nArry) / sizeof(nArry[0]); iIndex++)
    {
      nArry[iIndex] = rand() % 150;
    }
    printf("排序前:");
    PrintData(nArry, sizeof(nArry) / sizeof(nArry[0]));
    BubbleSort(nArry, sizeof(nArry) / sizeof(nArry[0]));
    printf("排序後:");
    PrintData(nArry, sizeof(nArry) / sizeof(nArry[0]));
  }
}
      

測試結果:

時間複雜度分析

核心部分代碼如下,假設待排序元素有n個

//執n次
for (int iIndex = 0; iIndex < nArySize; iIndex++)  
{   
    //執行1+2+.....+n次
    for (int jIndex = 0; jIndex < nArySize - iIndex -1; jIndex++)
    {
      //執行1+2+.....+(n-1)次
      if (pUnSortAry[jIndex] > pUnSortAry[jIndex + 1])
      {
          //執行(1/n)*(1+2+3...+n-1)
          int nTemp = pUnSortAry[jIndex];
          pUnSortAry[jIndex] = pUnSortAry[jIndex + 1];
          pUnSortAry[jIndex + 1] = nTemp;
          bFlag = true;
      }
    }

    //執行n次
    if (!bFlag)
    {
      //執行一次
        break; //如果記憶體for循環中一次交換也沒有發生,則說明所有元素已經有序
    }
}
      

平均時間複雜度為:T(n) =n+n+(1+2....+n) + (1+2....+(n-1)) + (1/n)(1+2+3...+n-1))

= 2n + 2(1+2...+n) - n + (1/n)*(1+2+3...+n-1 + n) -1

= n + n(1+n) + (1/2n)*n(1+n) -1

= n^2 + (5n)/2 -1/2

= O(n^2)

當元素已經是有序的情況下時間複雜度為T(n)=O(n)

穩定性

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元

素之間。是以，如果兩個元素相等，則不會進行交換如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩

交換把兩個相鄰起來，這時候也不會交換，是以相同元素的前後順序并沒有改變，是以冒泡排序是一種穩定排

序算法。