交換排序—冒泡排序（Bubble Sort）

基本思想：

最簡單的排序，也是最耗時間的排序

在要排序的一組數中，對目前還未排好序的範圍内的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較後發現它們的排序與排序要求相反時，就将它們互換。

冒泡排序的示例：

算法的實作：

void bubbleSort(int a[], int n){
	for(int i =0 ; i< n-1; ++i) {
		for(int j = 0; j < n-i-1; ++j) {
			if(a[j] > a[j+1])
			{
				int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
			}
		}
	}
}      

冒泡排序算法的改進

對冒泡排序常見的改進方法是加入一标志性變量exchange，用于标志某一趟排序過程中是否有資料交換，如果進行某一趟排序時并沒有進行資料交換，則說明資料已經按要求排列好，可立即結束排序，避免不必要的比較過程。本文再提供以下兩種改進算法：

1．設定一标志性變量pos,用于記錄每趟排序中最後一次進行交換的位置。由于pos位置之後的記錄均已交換到位,故在進行下一趟排序時隻要掃描到pos位置即可。

改進後算法如下:

void Bubble_1 ( int r[], int n) {
	int i= n -1;  //初始時,最後位置保持不變
	while ( i> 0) { 
		int pos= 0; //每趟開始時,無記錄交換
		for (int j= 0; j< i; j++)
			if (r[j]> r[j+1]) {
				pos= j; //記錄交換的位置 
				int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		i= pos; //為下一趟排序作準備
	 } 
}  
      

2．傳統冒泡排序中每一趟排序操作隻能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 進而使排序趟數幾乎減少了一半。

改進後的算法實作為:

void Bubble_2 ( int r[], int n){
	int low = 0; 
	int high= n -1; //設定變量的初始值
	int tmp,j;
	while (low < high) {
		for (j= low; j< high; ++j) //正向冒泡,找到最大者
			if (r[j]> r[j+1]) {
				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		--high;					//修改high值, 前移一位
		for ( j=high; j>low; --j) //反向冒泡,找到最小者
			if (r[j]<r[j-1]) {
				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
			}
		++low;					//修改low值,後移一位
	} 
}