寫好最簡單的冒泡排序

冒泡排序，真的很簡單，不是嘛，如果給你15分鐘，也許你會很快就寫出來一個，真的，我相信你，而且說不定考慮的還是相當周全滴，在此僅以此博客記錄一下，我所認識的冒泡排序。

冒泡排序，為什麼取這個名？

你可以想想池塘裡的氣泡，從最底部向最上部浮起的過程，是不是由小變大的過程中，這是一個物理知識，就不用說了吧，不知道的，回去看看初中科本吧，因此浮到水面的氣泡是不是最大的，這也就是取名冒泡的原因啦，浮到最上面的就是最大的，當然你別認為冒泡只能實現從小到大排序，大與小本身就是一種相對概念~

冒泡排序的思路(從小到大排序)

1:比較相鄰的元素,如果第一個元素比第二個元素小，就將其交換之

2:對每一對相鄰元素都做同樣的工作，從第一對直至最後一對

3:做完第2步，這裡最大的元素已經浮至最上面的位置，去除最後一個元素，重新執行上面的步驟，如果所有相鄰元素的比較過程中均沒有交換發生，排序完成。

冒泡排序的時間復雜度

最好的情況下，是待排序的元素已經處於有序的狀態，這裡只需要n-1次比較就可以了，也不需要進行元素的交換，因此最好時間復雜度為O(n)

最壞的情況下，是待排序的元素處於逆序的狀態，因此每次循環都需要進行n-i-1次比較，根據數學知識(高中的)可以得知總共需要的比較次數是n*(n-1)/2,對於每次的比軟均需要3次移動交換操作，因此總共的移動交換操作數為3n*(n-1)/2.因此總共的時間復雜度為O(n^2)

因此算法的平均時間復雜度為O(n^2)

冒泡排序的空間復雜度

空間復雜度這個很好計算，看一眼就知道了吧，整個程序中就用到了一個變量，用於交換用，因此空間復雜度為O(1),但是不一定呦，下面有程序二將空間復雜度降為0

冒泡排序的穩定性

穩定性，這個也是顯然的，是穩定的，兩個相鄰元素，如果是相等的，就不進行交換，除非是你有意為之~~~

普通的冒泡排序源程序

[

void BubbleSort(int *a ,int N) 
{ 
    bool flag=true; 
    int tmp; 
    for(int i=0;i<N;i++) 
    { 
        for(int j=0;j<N-i;j++) 
        { 
            if(a[j]>a[j+1]) 
            { 
                tmp=a[j]; 
                a[j]=a[j+1]; 
                a[j+1]=tmp; 
                flag=false; 
            } 
        } 
        if(flag) 
            break; 
    } 
    return ; 
} 

void BubbleSort(int *a ,int N)
{
 bool flag=true;
 int tmp;
 for(int i=0;i<N;i++)
 {
  for(int j=0;j<N-i;j++)
  {
   if(a[j]>a[j+1])
   {
    tmp=a[j];
    a[j]=a[j+1];
    a[j+1]=tmp;
    flag=false;
   }
  }
  if(flag)
   break;
 }
 return ;
}

更快的空間復雜度為0的冒泡排序

void BubbleSort(int *a ,int N) 
{ 
    bool flag=true; 
    for(int i=0;i<N;i++) 
    { 
        for(int j=0;j<N-i;j++) 
        { 
            if(a[j]>a[j+1]) 
            { 
                a[j]=a[j]^a[j+1]; 
                a[j+1]=a[j+1]^a[j]; 
                a[j]=a[j+1]^a[j]; 
                flag=false; 
            } 
        } 
        if(flag) 
            break; 
    } 
    return ; 
} 

void BubbleSort(int *a ,int N)
{
 bool flag=true;
 for(int i=0;i<N;i++)
 {
  for(int j=0;j<N-i;j++)
  {
   if(a[j]>a[j+1])
   {
    a[j]=a[j]^a[j+1];
    a[j+1]=a[j+1]^a[j];
    a[j]=a[j+1]^a[j];
    flag=false;
   }
  }
  if(flag)
   break;
 }
 return ;

}上面代碼用到了異或操作，降低算法空間復雜度