冒泡算法的改进

冒泡排序算法的思想：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这样最大的元素会沉入最底部。
3. 紧接着下一次对除最后一个元素重复上面的步骤，一直按照不超过元素数的次数进行重复，直到没有任何一对数字需要比较。 先看一下基础冒泡算法：

   int BubbleSort(MergeType* L)
   {
   	int i, j;
   	for (i = 0; i <= L->len-1; i++)
   	{ 	
   		for (j = 0; j < L->len-1-i; j++)
   		{
   			if (L->elem[j+1] < L->elem[j])
   			{
   				SWAP(L->elem[j+1], L->elem[j] );	
   			}
   		}	
   	}
   
   	return 0;
   }

   
   这里的MergeType类型如下：

   typedef struct _SQLIST{
       int* elem;
       int len;   //实际长度
       int size;  //分配空间
   }SqList, *pSqList;
   
   typedef _SQLIST MergeType;

   核心思想是每次选出最大的数沉入底部，直至没有数据可比较。
   

   首先看到其不足之一：就是频繁交换元素。如何避免，可以存放在一个合适的位置，精简算法一：

   
   

   int BubbleSortEx(MergeType* L)
   {
   	int i = 0, j = 0;
   	int max, temp;
   	for (i = 0; i <= L->len-1; i++)
   	{ 	
   		temp = L->elem[0];
   		max = 0;
   		for (j = 1; j < L->len-i; j++)
   		{			
   			if (L->elem[j] > temp)
   			{
   				temp = L->elem[j];
   				max = j;
   			}
   		}
   		//printf("%d:%d \n", max, temp);
   		swap(L->elem[L->len-1-i], L->elem[max] );			
   	}
   
   	return 0;
   }

   
   看到这里每次仍然需要频繁的进行赋值操作，当然只是微不足道的，但是赋值也会增加cpu执行的时间，所以精简二:

   int BubbleSortEx(MergeType* L)
   {
   	int i, j , max;
   	for (int i = 0; i <= L->len-1; i++)
   	{ 	
   		max = 0;
   		for (j = 1; j < L->len-i; j++)
   		{			
   			if (L->elem[j] > L->elem[max])
   			{
   				max = j;
   			}
   		}
   		printf("%d:%d \n", max, L->elem[max]);
   
   		swap(L->elem[L->len-1-i], L->elem[max] );			
   	}
   
   	return 0;
   }

   这里的两个swap是不一样的，当然也可以使用一样的，看如下具体的实现：

   #define SWAP(a, b) \
   {                 \
   	int temp = (a); \
   	(a) = (b);        \
   	(b) = temp;     \
   }

   inline void swap(int& a, int& b)
   {
   	int temp = a;
   	a = b;
   	b = temp ;
   }

   第一个是采用宏替换，当然主要是增加预处理的时间，主要是用宏会出现意想不到的错误

   第二个是函数，这里使用了引用，可以减少指针使用的形参变量副本的创建，但是这里使用了inline，所以还是替换