交換排序

基本思想：在一個待排序序列中，兩兩比較元素的排序碼，如果不滿足次序要求則進行交換，直到整個排序序列滿足要求。

氣泡排序

思想：對待排序序列從前向後，依次比較相鄰元素的排序碼，若發生逆序，則進行交換。

實現：

#include <stdio.h>

void BubbleSort(int *p, int N)
{
	int i, j;
	int flag; //標誌位，判斷元素是否發生交換 
	int t; //交換時的中間變數
	 
	for(i = 0; i < N-1; i++)
	{
		flag = 0;
		for(j = 0; j < N-1-i; j++)
		{
			if(p[j] > p[j+1]) //>--從小到大;<--從大到小 
			{
				t = p[j];
				p[j] = p[j+1];
				p[j+1] = t;
				flag = 1;
			}
		}
		
		if(!flag) //減少不必要的比較
		    return;
	}
}

int main()
{
	int m, n;
	
	//待排序序列
	int a[7] = {49, 38, 65, 97, 76, 13, 27};
    
    //輸出待排序序列 
    printf("待排序序列：");
    for(m = 0; m < 7; m++)
    {
    	printf("%d ", a[m]);
	}
	printf("\n");
	
    //氣泡排序 
    BubbleSort(a, 7);
    
    //輸出排序後的序列 
    printf("經過氣泡排序後的序列：");
    for(n = 0; n < 7; n++)
    {
    	printf("%d ", a[n]);
	}
	printf("\n");
	
	return 0;
} 

結果：

分析：

• 時間複雜度：O(n^2)
• 空間複雜度：O(1)
• 演算法是否穩定：穩定