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

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

很簡單,假設我們有一個陣列大小為三的陣列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 = (n2-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");
}

arrow
arrow

    archerdevil 發表在 痞客邦 留言(0) 人氣()