【大话数据结构C语言】64 冒泡排序

冒泡排序的要点

两两注意是相邻的两个元素的意思

如果有n个元素需要比较n-1次，每一轮减少1次比较

既然叫冒泡排序，那就是从下往上两两比较，所以看上去就跟泡泡往上冒一样。

 

冒泡排序是最简单的一种排序，基本思想就是两两比较相邻的关键字，如果反序则交换，直到没有反序为止

 

冒泡排序的一般思路：

#include 

void BubbleSort(int k[], int n)
{
	int i, j, temp, count1=0, count2=0;
	
	for( i=0; i < n-1; i++ )
	{
		for( j=i+1; j < n; j++ )
		{
			count1++;
			if( k[i] > k[j] )
			{
				count2++;
				temp = k[j];
				k[j] = k[i];
				k[i] = temp;
			}
		}
	}
	printf("总共进行了%d次比较，进行了%d次移动！", count1, count2);
}

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

	BubbleSort(a, 10);

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

	return 0;
}

 

 

上述代码严格意义来说不算是标准的冒泡排序算法，因为不满足“两两比较相邻关键字”的思想

更应该是最最简单的交换排序而已，这种排序是比较低效的

 

下边是正宗的冒泡排序：

#include 

void BubbleSort(int k[], int n)
{
	int i, j, temp, count1=0, count2=0;
	
	for( i=0; i < n-1; i++ )
	{
		for( j=n-1; j > i; j-- )
		{
			count1++;
			if( k[j-1] > k[j] )
			{
				count2++;
				temp = k[j-1];
				k[j-1] = k[j];
				k[j] = temp;
			}
		}
	}

	printf("总共进行了%d次比较，进行了%d次移动！", count1, count2);
}

int main()
{
	int i, 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]);
	}
	printf("\n\n");

	return 0;
}

 

 

这样的算法是否还可以优化呢？

答案是可以的，可以在代码中增加一个flag标记算法，当知道数据没有任何数据交换的时候，说明此时序列已经有序，不需要在继续后边的循环判断工作

#include 

void BubbleSort(int k[], int n)
{
	int i, j, temp, count1=0, count2=0, flag;
	
	flag = 1;
	for( i=0; i < n-1 && flag; i++ )
	{
		for( j=n-1; j > i; j-- )
		{
			count1++;
			flag = 0;
			if( k[j-1] > k[j] )
			{
				count2++;
				temp = k[j-1];
				k[j-1] = k[j];
				k[j] = temp;
				flag = 1;
			}
		}
	}

	printf("总共进行了%d次比较，进行了%d次移动！", count1, count2);
}

int main()
{
	int i, 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]);
	}
	printf("\n\n");

	return 0;
}