排序算法4 - 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

冒泡排序算法的原理如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

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

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

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

演示图：

代码：

本例代码使用的是从后往前冒泡。

#include <stdio.h>

void BubbleSort(int k[], int n)
{
	int i, j;

	for(i=0; i<n-1; i++)
	{
		for(j=n-1; j>i; j--)
		{
			if( k[j-1]>k[j] )
			{
				k[j] ^= k[j-1];
				k[j-1] ^= k[j];
				k[j] ^=k[j-1];
			}
		}
	}
}


int main(void)
{

	int i;
	int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

	BubbleSort(a, 10);

	printf("排序后的结果是：");
	for(i=0; i<10; i++)
	{
		printf("%d", a[i]);
		if(i!=9)
		{
			printf(",");
		}
	}
	printf("\n");
	return 0;
}

冒泡排序优化：

优化原理是对已经有序的序列减少循环次数和大小判断次数。如图：

优化后的代码：

#include <stdio.h>

void BubbleSort(int k[], int n)
{
	int i, j, flag;

	flag = 1; 
	for(i=0; i<n-1 && flag; i++)
	{
		for(j=n-1; j>i; j--)
		{
			flag = 0;
			if( k[j-1]>k[j] )
			{
				k[j] ^= k[j-1];
				k[j-1] ^= k[j];
				k[j] ^=k[j-1];
				flag = 1;
			}
		}
	}
}


int main(void)
{

	int i;
	int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

	BubbleSort(a, 10);

	printf("排序后的结果是：");
	for(i=0; i<10; i++)
	{
		printf("%d", a[i]);
		if(i!=9)
		{
			printf(",");
		}
	}
	printf("\n");
	return 0;
}