C语言——冒泡排序(分析详解)

冒泡排序

文章目录

• 冒泡排序
• • 排序算法的介绍
  • 排序的分类
  • • (1)内部排序：
    • (2)外部排序法：
  • 【重点】冒泡排序
  • • 1.基本介绍
    • 2.冒泡排序应用实例
    • 3.分析冒泡的过程+代码

排序算法的介绍

排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。

排序的分类

(1)内部排序：

指将需要处理的所有数据都加载到**内部存储器(内存)**中进行排序。

(2)外部排序法：

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

【重点】冒泡排序

1.基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐 向上冒。

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

2.冒泡排序应用实例

将五个无序的数：{3, 9, -1, 10, -2}，使用冒泡排序法将其排成一个从小到大的有序数列。

3.分析冒泡的过程+代码

代码实现：

#include <stdio.h>
int main(){
	
	int arr[] = {3,9,-1,10,-2};
	
	//第一轮排序
	
	int j;
	int t;//临时变量
	for(j=0;j<4;j++){
		
		//如果前面的数大于的后面的数，就交换
		if(arr[j]>arr[j+1]){
			t = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = t;
		}
	}
	//输出看看第一轮的排序后的情况
	for(j=0;j<5;j++){
		printf(" %d",arr[j]);	
	}
	printf("\n");
	//第二轮排序
	for(j=0;j<3;j++){
		
		//如果前面的数大于的后面的数，就交换
		if(arr[j]>arr[j+1]){
			t = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = t;
		}
	}
	//输出看看第二轮的排序后的情况
	for(j=0;j<5;j++){
		printf(" %d",arr[j]);	
	}
	printf("\n");
	
	//第三轮排序
	for(j=0;j<2;j++){
		
		//如果前面的数大于的后面的数，就交换
		if(arr[j]>arr[j+1]){
			t = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = t;
		}
	}
	//输出看看第三轮的排序后的情况
	for(j=0;j<5;j++){
		printf(" %d",arr[j]);	
	}
	
	printf("\n");
	//第四轮排序
	for(j=0;j<1;j++){
		
		//如果前面的数大于的后面的数，就交换
		if(arr[j]>arr[j+1]){
			t = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = t;
		}
	}
	//输出看看第四轮的排序后的情况
	for(j=0;j<5;j++){
		printf(" %d",arr[j]);	
	}
	return 0;
}

因为每轮排序几乎一样，因此我们可以使用for循环来处理，进行精简代码，同时定义一下数组大小的变量，arrLen,让代码更灵活

#include <stdio.h>
int main(){
	
	int arr[] = {3,9,-1,10,-2};
	
	//因为每轮排序几乎一样，因此，我们可以使用for循环处理
	
	//第一轮排序
	
	int j,i;
	int t;//临时变量
	int arrLen = sizeof(arr) / sizeof(int); // 5 数组大小
	for(i=0;i<arrLen-1;i++){
		for(j=0;j<arrLen-1-i;j++){		
		//如果前面的数大于的后面的数，就交换
		if(arr[j]>arr[j+1]){
			t = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = t;
			}
		}
		//输出看看第一轮的排序后的情况
		for(j=0;j<arrLen;j++){
			printf(" %d",arr[j]);	
		}
		printf("\n");	
	}
	return 0;
}

因为每次重复写代码太过麻烦，可以将上述代码封装成冒泡排序的函数：

#include <stdio.h>
//冒泡排序的函数
void bubbleSort(int arr[],	int arrLen){
	
	int j,i;
	int t;//临时变量	
		//因为每轮排序几乎一样，因此，我们可以使用for循环处理
	for(i=0;i<arrLen-1;i++){
		for(j=0;j<arrLen-1-i;j++){		
		//如果前面的数大于的后面的数，就交换
		if(arr[j]>arr[j+1]){
			t = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = t;
			}
		}	
	}
}

int main(){
	
	int j;
	int arr[] = {3,9,-1,10,-2};
	int arrLen = sizeof(arr) / sizeof(int); // 5 数组大小
	bubbleSort(arr,arrLen);//数组默认是地址传递 (指针)
	printf("\n排序后(函数)\n");
		for(j=0;j<arrLen;j++){
			printf(" %d",arr[j]);	
		}

	return 0;
}