Archer, who doesn't know how to shoot...

泡泡排序玩過之後，為什麼會有本篇「之二」誕生？

很簡單，因為這一次要玩的，是降低運算次數。為什麼要降低運算次數？

很簡單，假設我們有一個陣列大小為三的陣列arr[3]={A, B, C}

如果不降低次數的話，使用兩個迴圈，總次數為:(n-1)(n-1) = 2*2 = 4次 //不要忘記統統從零開始

for(int i= 0; i<n-1; i++ )
    for (int j= 0; j<n-1; i++ )

上面這個迴圈的結果如下： 

1.  B, A, C // i=0, j=0, 如果 [j+1] 比 [j] 大則 [j] 與 [j+1] 交換
2.  B, C, A // i=0, j=1, 如果 [j+1] 比 [j] 大則 [j] 與 [j+1] 交換
3.  C, B, A // i=1, j=0, 如果 [j+1] 比 [j] 大則 [j] 與 [j+1] 交換
4.  C, B, A // i=1, j=1, 如果 [j+1] 比 [j] 大則 [j] 與 [j+1] 交換

總共四次。但其中第四次根本白做的。

當陣列元素很少的時候，這樣可能還好，但如果陣列元素數量總共10個呢？8＊8 總共要做64次。如果100個元素呢?那就是99的平方次...。

那應該怎麼降低次數？

根據上面的例子可以發現，當一個數被送到底端之後，他就確定了位置，之後不管經過幾次交換，確定位置的數都不會繼續變動。比如說A，當A被換到最後面去之後，A就開始養老了。接下來三次根本完全兩耳不聞窗外事，所以這時候我們就應該把他排除在判斷之外。

for(int i= 0; i<n-1; i++ )
    for (int j= 0; j<n-1-i; i++ )

這樣有效嗎？當然有效。一樣的例子去跑這個迴圈，會變成

1.  B, A, C // i=0, j=0, 如果 [j+1] 比 [j] 大則 [j] 與 [j+1] 交換，此時j 迴圈的邊界條件為n-1-i=3-1-0=2
2.  B, C, A // i=0, j=1, 如果 [j+1] 比 [j] 大則 [j] 與 [j+1] 交換，此時j 迴圈的邊界條件為n-1-i=3-1-0=2，滿足，重回 i 迴圈
3.  C, B, A // i=1, j=0, 如果 [j+1] 比 [j] 大則 [j] 與 [j+1] 交換，此時j 迴圈的邊界條件為n-1-i=3-1-1=1，滿足，跳出

這樣就結束了。

實際上的運算次數應該是Σ_i=1→nΣ_j=i→n1 ＝ (n²-n)/2，以上面的例子來說就是4次。如果把上面的元素數量改成10個，那就是45次，而如果不刪減已排序元素的話，最多就要做到81次....，相差可多了。

以下就是實例：

#include <iostream>
using namespace std;

const int size = 20;

void sort(int arr[size], int n)
{
    int flag, temp;
    for (int i=0;i<n;i++)
    {
        for (int j=0; j<n-1-i;j=j+1)
        {
            if(arr[j]>arr[j+1])
            {
                temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        cout<<"\n";
    }
}

void main()
{
int array[size] = {211,500,45,12,15,11,30,28,47, 50, 9,8,7,6,5,4,3,2,1,0};
sort(array, size);
for (int i=0; i<size;i++)
{
cout<<array[i]<<"\t";
}
system("pause");
}