[C]資料排序

當有一群數字資料要排列大小時，到底該怎麼做呢?

再這邊介紹兩種方法，氣泡排序法和插入排序法。

以下都介紹昇幕排序，若要做降幕排序只要更改一下比較條件即可，至於改法就請各為自行思考囉。

一、氣泡排序法

I.規則

1.將相鄰的兩筆資料比較大小，如果第一個資料比第二個資料小就交換(結果會是昇幕排序，由小到大)
2.針對每一個組合都比對，持續運作到結束後，第一個數字會是最小，最後一個數字最大。

II.寫法

以下利用function的方式寫

void bubble_sort(int data[],int size)
{
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(data[j]>data[i])
			{
				int temp=data[j];
				data[j]=data[i];
				data[i]=temp;
			}
		}
	}
}

III.實例

二、插入排序法

I.規則

1.從第二項開始取出
2.和前N-1項比較，如果比該項小，就把該項項後移一個位子
3.直到取出的項大於，當前比較的項，就停止
4.把取出的項插入
5.取下一項，重複2~5步驟
這樣講或許大家有聽沒有懂，這邊借一張wikipedia的圖片，讓大家了解實際運作規則

II.寫法

以下利用function的方式寫

void insertion_sort(int data_array[],int size)
{
	int temp;
	for(int i=1;i<size;i++)
	{
		temp=data_array[i];
		int j=i-1;
		while(j>=0 && data_array[j] > temp) // j>=0的條件是為了避免array的index為負值
		{
			data_array[j+1]=data_array[j];
			j--;
		}
		data_array[j+1]=temp;
	}
}

III.實例 

 temp相當於上面那張圖紅色框框所圈的數字

三、比較 

1. 氣泡排序法和插入排序法在完全散亂的資料上執行的時間是一樣的(因為行為都是做逐項比較)。
2. 插入排序法所需要的交換次數通常少於氣泡排序法。
3. 上面的例子，氣泡排列法交換6次，插入排列法交換5次