---

在很多的資料結構中，排序是程式結構的基礎。

首先，先說明一下，排序是什麼?

在程式中，有許許多多的Data被Load進來。但在這麼多的Data中要如何找到順序的規則?

這時候我們就可以利用排序法來幫我們歸納Data。

排序的簡易介紹：

1.排序Sorting：是指將一群資料，按特定規則調換位置，使資料具有遞增或遞減的順序關係

2.在排序的過程中，資料的移動規則分為直接移動與邏輯移動2種

2.1.直接移動：直接交換儲存資料的位置

2.2..邏輯移動：不會移動資料儲存位置，僅改變指向這些資料的輔助指標的值

其實排序的方法有很多種，在這邊小仇介紹簡易排序法

1.泡沫排序法(Bubble Sort)

泡沫排序法可以說是最簡易的排序法，其排序的策略是由資料的最左邊開始往右比較，

只要左側資料值比右側大，則2筆資料做交換，直到右側資料值(n)為止。這時候右側資

料值為n筆資料中最大值。(此為第一次轉換)。下一次還是從左側資料值開始與右側資料

值做比較，但此次只做到倒數第2筆資料即可。依此類推，完成時已做了(n-1)次的迴圈

排序。[泡沫排序法的時間複雜度為O(N²)，對於資料量大的排序工作，其效率就

比較差了。泡沫排序法最理想的時間複雜度有可能為O(N)，因為在排序過園中，每一筆

資料只需和右側的資料比較即可，所以具有穩定性的優勢。

Example：

假設我們這邊有3筆資料，最後會做n-1次排序，也就是2次。

Data：50  30  25   (Data是小仇隨便設定的)

第1次排序  50 > 30 交換  此時資料為 30 50 25

                   

    50  > 25 交換 此時資料為 30 25 50

第2次排序時資料是帶著 30 25 50 (第1次排序完的結果進入第2次排序)

        此時排序   30 > 25 交換  此時資料為 25 30 50

即完成排序結果。

程式大略寫法

void bubbleSort(int data[], int n)

{

int i,j,t;

for (int i = n-1; i>0; i--)

{

for(int j=0; j < i; j++)

{

if (data[j] > data[j+1]

{

t = data[j];

data[j] = data[j+1];

data[j+1] = t;

}

}

}

}

依照小仇寫的例子來看，n = 3，因為有3筆資料，所以i會最後會執行2次。

    j的值 就是 50 30 25

   而if的迴圈中就在做資料排序交換的動作。

  t = data[j] 此時 t = 50

 data[j+1] = 30 此時就換至 data[j]的陣列位置。

 data[j+1]此時換成t，也就是50，後序以此類推。


2.插入式排序法(Inserting Sort)

將陣列中的元素(Data)，逐一與已排序好的資料作比較，假設有兩個元素先

排好，再將第三個元素插入適當的位置，所以這三個元素仍然是已排序好，

接著再將第四個元素加入，重覆此步驟，直到排序完成為止

Example：

假設我們有5筆資料

Data：35 42 18 91 65

第1次排序時，35 42 插入42，因為已經是排序好的狀態，所以42不做任何變動。

第2次排序時，18 < 35 42，所以將18插入至陣列0的位置，35 42則往陣列右側移動。

第3次排序時，91 > 18 35 42，所以直接插入排序至最後的陣列位置，不做任何變動。

第4次排序時，65 > 18 35 42，但 65 < 90，所以將65插入至陣列3的位置。

最後完成排序時，陣列位置的元素(Data)為 18 35 42 65 91。

程式大略寫法

void insertionSort(int data[], int n)

{

int i;

for (int i = 1; i<n; i++)

{

int v = data[i];

int j = i;

while(j > 0 && data[j－1] > v）

｛

data[j] = data[j-1];

j--;

｝

data[j]  = v;

}

}

其實排序的方法有很多種，而小仇所寫的2種是排序當中最簡易的方式。
其餘的排序方法，有時間小仇也會po文上來。

--
※ 作者: party100046 時間: 2012-03-18 01:51:56