冒泡排序

冒泡排序(Bubble Sort)

冒泡排序是一种极其简单的排序算法，也是我所学的第一个排序算法。它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下：

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。冒泡排序的代码如下：

//单向冒泡排序（升序）
void BubbleSort1(int* arr,int value)
{
	int i = 0;
	int j = 0;
	for (i=0;i<value;i++)
	{
      int flag = 0;   //定义flag用来判断是否原来就是按照顺序排列的 
		for (j=value-1;j>=i;j--)
		{
			if (arr[j]<arr[j-1])
			{
				int tmp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = tmp;
				flag = 1;
			}

		}
		if(flag == 0)
			break;
	}
	
}


//指针实现单向冒泡排序(降序)
void BubbleSort2(int *arr,int sz)
{
	int *start = arr;
	int *end = arr+sz-1;
	int *cur = NULL;
	assert(arr!=NULL);
	while (start<end)
	{
		cur = start;
		while (cur<end)
		{
			if (*cur<*cur+1)
			{
				int tmp = *cur;
				*cur = *cur+1;
				*(cur+1) = tmp;
			}
			cur++;
		}
		end--;
	}

}

//双向冒泡排序
void Swap( int *num_a, int *num_b )  
{  
	int temp = *num_b;  
	*num_b = *num_a;  
	*num_a = temp;  
}

void BubbleSort3(int array[], int n)  
{  
	int low, high, flag, i;  
	low = 0;  
	high = n - 1;  
	while(low < high)  
	{  
		flag=0;  
		for(i=low; i<high; i++)  //正向冒泡  
		{  
			if(array[i] > array[i+1]) //找到剩下中最大的  
			{  
				Swap(&array[i], &array[i+1]);  
				flag = 1;    //标志， 有数据交换  
			}  
		}  
		if( !flag )  
			break;  
		high--;  
		for( i=high; i>low; i-- ) //反向冒泡  
		{  
			if(array[i] < array[i-1])   //找到剩下中最小的  
				Swap(&array[i], &array[i-1]);  
		}  
		low++;  
	}  
}  

下面我们测试一下：

int main()
{
	int arr[] = {1,2,3,4,5,6,7,8,9};
	int i = 0;
	int sz = sizeof(arr)/sizeof(arr[0]);
	
	printf("单向升序排序：\n");
	BubbleSort1(arr,sz);
	for (i=0;i<sz;i++)
	{
		printf("%d  ",arr[i]);
	}
	printf("\n");

	printf("单向降序排序：\n");
	BubbleSort2(arr,sz);
	for (i=0;i<sz;i++)
	{
		printf("%d  ",arr[i]);
	}
	printf("\n");

	printf("双向升序排序：\n");
	BubbleSort3(arr,sz);
	for (i=0;i<sz;i++)
	{
		printf("%d  ",arr[i]);
	}
		printf("\n");
	return 0;
}

 输出结果：