[C++知识库]C语言——优化后的冒泡排序法

冒泡排序法是我们接触到的比较经典的算法思想了。

问题描述：我们要把9,7,8,6,5,4,3,2,1,0升序输出。

#include<stdio.h>
void paixu(int arr[] , int sz);
int main()
{
	int i;
	int arr[] = {9,8,7,6,5,4,3,2,1,0};
	int sz = sizeof(arr)/sizeof(arr[0]);  //求出数组的长度

	paixu(arr , sz);                     //传参的时候要把数组的长度：sz传过去，切不可忘记
	
	for(i = 0 ; i < sz ; i++ )
	{
		printf("%d ",arr[i]);
	}

	return 0;
}

void paixu(int arr[] , int sz)
{
	int i = 0;
	for( i = 0 ; i < sz - 1 ; i++ )      //十个数字需要进行九轮比较，以此类推
	{
		int j = 0;
		for( j = 0 ; j < sz -1 - i ; j++)  //在这里，第一个数字需要比较9次，第二个数字需要比较8次，所以这里的第二个循环控制条件写为：j < sz - 1 - i。
			if ( arr[j] > arr[j+1] )    //如果相邻的前一个数字大于后一个数字了，则进行交换
			{
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;   
			}
		}
	}
}

那么如果是这样子的一串数字呢？

{0,1,2,3,4,5,6,7,8,9}

这列要升序排列，但是已经有序了，这个时候老老实实的一个一个比较效率就会很低

那么我们怎么优化呢？

#include<stdio.h>
void paixu(int arr[] , int sz);
int main()
{
	int i;
	int arr[] = {0,1,2,3,4,5,6,7,8,9};
	int sz = sizeof(arr)/sizeof(arr[0]);

	paixu(arr , sz);
	
	for(i = 0 ; i < sz ; i++ )
	{
		printf("%d ",arr[i]);
	}

	return 0;
}

void paixu(int arr[] , int sz)
{
	int i = 0;
	for( i = 0 ; i < sz - 1 ; i++ )
	{

		int ter = 1;         //优化程序加入的步骤//


		int j = 0;
		for( j = 0 ; j < sz -1 - i ; j++)
		{
			if ( arr[j] > arr[j+1] )
			{
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
				ter = 0;
			}


			if(ter == 1)      //优化程序加入的步骤//
			{
				break;
			}

		}
	}
}

这段代码和上面的基本一样，只是为了优化而添加了一些代码（这个优化是针对那些已经有序的数组）

在这里定义了一个ter?= 1，并且在if判断语句中加入了一个ter?= 0，这个意思就是说，当if判断语句符合条件的时候（也就是相邻的前一个元素大于后一个元素），进入if语句，ter被修改为0，不执行下面的if语句（break的那个if语句）；但是如果没有进入if语句?的话，ter就等于1 ，执行下面的if语句，break，跳出外层循环，完成冒泡排序，一定程度上提升了代码的效率。