C语言冒泡排序算法

冒泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止

void buble_sort(int arr[],int len)
{
	for (int k = 0; k < len - 1; k++)	//趟数，因为数组元素是10个，所以比较9趟
	{
		for (int i = 0; i < (len - 1)-k; i++)	//每趟过后交换的次数少一次
		{
			if (arr[i] > arr[i+1])
			{
				//交换
				int temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
			}
		}
	}
 }
 int main()
 {
     int arr[] = {9,8,7,6,5,4,3,2,1};
     int len = sizeof(arr)/sizeof(arr[0]);
     buble_sort(arr,len);
     for(int i = 0; i < len; i++)
     {
         printf("%d ",arr[i]);	//1 2 3 4 5 6 7 8 9
     }
 	return 0;
 }

冒泡排序优化

如果数组本身有序，使用冒泡算法的话，就要比较 len -1趟，显然当数组元素过多的时候效率是很低的，那有没有优化的可能呢，答案是有的。

优化方法：在第一趟比较的时候设置一个flag标志，初始值为1，如果发生元素交换时，flag就置0，说明数组不是本身有序，当一趟比较完后，再判断flag的值，如果仍然为1，则说明没有发生元素交换，数组本身有序，就退出循环，不用进行剩下的比较

void buble_sort(int arr[],int len)
{
	for (int k = 0; k < len - 1; k++)	//趟数，len -1趟
	{
		int flag = 1;		//设置flag标志，并初始化为1
		for (int i = 0; i < (len - 1) - k; i++)	//每趟过后交换的次数少一次
		{
			if (arr[i] > arr[i+1])
			{
				//交换
				int temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
				flag = 0;	//有元素进行了交换，falg置0
			}
		}		
		if (flag == 1)		//当进行一次比较后falg没有置0，说明没有交换，数组本身有序
		{
			break;			//退出循环，不用进行剩下的比较趟数
		}
	}
 }
 int main()
 {
     int arr[] = {9,8,7,6,5,4,3,2,1};
     int len = sizeof(arr)/sizeof(arr[0]);
     buble_sort(arr,len);
     for(int i = 0; i < len; i++)
     {
         printf("%d ",arr[i]);	//1
     }
 	return 0;
 }

冒泡排序的执行时间取决于排序的趟数，最好的情况下，待排序记录序列为正序，算法只执行一趟，进行了n-1次比较，不需要移动记录，时间复杂度为O(n)；最坏的情况下，待排序记录序列为反序，时间复杂度为O(n²)；平均情况下，冒泡排序的时间复杂度与最坏情况同数量级