冒泡排序2

从上一篇的博文中，我们可以看到，对于第四遍遍历的时候，已经排序完成，没有发生任何交换，这对于算法来说，是可以避免的。可以优化的。今天我们来详细说一下，如何来优化。

优化冒泡排序

我们是否可以设想，在执行下一边排序的时候，我们先判断一下，上一遍排序是否发生交换，如果发生交换，就继续执行下一遍的遍历，如果没有发生交换，我们就可以认为，这个无序数组已经排序完成，这个时候我们就可以结束程序了。

代码实现

void BubbleSort(int* pDataArray, int iDataNum)  
{  
   BOOL flag = FALSE;//记录是否存在交换  
   for (int i = 0; i < iDataNum - 1; i++)//走iDataNum-1趟  
    {  
        flag = FALSE;  
         for (int j = 0; j < iDataNum - i - 1; j++)  
         if (pDataArray[j] > pDataArray[j + 1])  
          {  
             flag = TRUE;  
             DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
           }  
  
       if (!flag)//上一趟比较中不存在交换，则退出排序  
       break;  
      }  
}

冒泡排序的时间复杂度为O(N^2)