冒泡排序算法

冒泡排序核心思想:两两相邻的元素进行比较。

比如一组数据，{7，2，6，5，0}让其按升序排序。

第一趟：

（1）2，7，6，5，0        12元素比较，7比2大，交换

（2）2，6，7，5，0         23元素比较，7比6大，交换

（3）2，6，5，7，0         34元素比较，7比5大，交换

（4）2，6，5，0，7         45元素比较，7比0大，交换 -五个元素，两两比较，确定最大的元素

第二趟：

（1）2，6，5，0，7        12元素比较，2比6小，不交换

（2）2，5，6，0，7        23元素比较，6比5大，交换

（3）2，5，0，6，7        34元素比较，6比0大，交换 -前四个元素两两比较，确定第二大的元素

第三趟：

（1）2，5，0，6，7        12元素比较，2比5小，不交换

（2）2，0，5，6，7        23元素比较，5比0大，交换-前三个元素两两比较，比两次

第四趟：

（1）0，2，5，6，7        12元素比较，2比0大，交换-剩余两个元素比较

由上述示例可以看出冒泡排序特点：

1.一趟冒泡排序确定一个元素，n个元素，需要比n-1趟

2.每趟比较次数逐渐减少 

冒泡排序按升序——先确定最大元素；按降序——先确定最小元素。

#include<stdio.h>
void bubble_sort(int arr[],int sz)
{
	int i = 0;
	int j = 0;
	for(i = 0;i <sz-1;i++){//sz个元素，共比较sz-1趟, 假设10个元素 
		for(j = 0;j<sz-i-1;j++){// 每一趟内部比较次数 //i=0，第一趟9次 次数=10-0-1 
			if(arr[j]>arr[j+1]){                       //i=1，8次            10-1-1
				int temp = arr[j];                     //i=2，7次            10-2-1
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			} 
		}
	}
	
 } 
int main()
{
	int arr[] = {7,2,6,5,0};//给出一个数组 
	int sz = sizeof(arr)/sizeof(arr[0]);//求数组元素个数 
	bubble_sort(arr,sz);//冒泡排序函数，需要数组，及元素个数，传递这两个参数 
	int i = 0;
	for(i = 0;i<sz;i++){
		printf("%d\n",arr[i]);//打印排好的数组 ,0,2,5,6,7
	}
	return 0;
 } 

 如果第一趟无交换，说明已经有序，无需后续交换。所以上述代码可以优化。

#include<stdio.h>
void bubble_sort(int arr[],int sz)
{
	int i = 0;
	int j = 0;
	for(i = 0;i <sz-1;i++){
		int flag = 1;//假设没有发生交换 
		for(j = 0;j<sz-i-1;j++){
			if(arr[j]>arr[j+1]){
		        flag = 0;//发生交换说明无序        
				int temp = arr[j];                 
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			} 
		}
		if(flag==1){//这一趟无交换，有序，无需排序 
			break;
		} 
	}
	
 } 
int main()
{
	int arr[] = {7,2,6,5,0};
	int sz = sizeof(arr)/sizeof(arr[0]); 
	bubble_sort(arr,sz); 
	int i = 0;
	for(i = 0;i<sz;i++){
		printf("%d ",arr[i]);
	}
	return 0;
 }