冒泡排序法

in 算法与数据结构 with 2 comment

** 大一的时候学了c语言,我当时就接触到了冒泡排序, 现在重新学习一下数据结构与算法的知识点, 冒泡排序发是排序算法中比较基础的算法之一。 **

冒泡排序

之所以称之为冒泡排序,形象一点解释就是和煮开水滚的时候冒的气泡一样,直接进入主题 定义一个 int[] arr = {12,6,2,1}

1. 想要排序好这个数据,无非就是数组间数字做交换
2. 第一个循环,这里我们也称之为躺数,既排序好需要多少躺
3. 第二个循环为每一躺需要比较的次数, 从0位开始(i = 0),前一位与后一位比较,如果i > i + 1(或者 i < i + 1),那么就进行交换

冒泡排序实现

模拟一下每一躺循环的过程

int[] arr   =  {12,6,2,1};
int  temp;  //临时变量,用作交换 
//第0位与第1位进行比较(这里指数组的下标)
if (arr[0] > arr[1]){    
	temp = arr[0];
	arr[0] = arr[1];
	arr[1] = temp;
}
//arr = {6,12,2,1}


//第1位与第2位进行比较
if (arr[1] > arr[2]){  
	temp = arr[1];
	arr[1] = arr[2];
	arr[2] = temp;
}
// arr = {6,2,12,1}

//第2位与第3位进行比较,
if (arr[2] > arr[3]){
	temp = arr[2];
	arr[2] = arr[3];
	arr[3] = temp;
}
//arr = {6,2,1,12}

经过第一趟的循环和比较,最大数字已经跑到最后一位了(第1趟,比较3次得到) 继续第二趟...这时候数组是从 arr = {6,2,1,12} 开始。

//第0位与第1位进行比较(这里指数组的下标)   第1次比较
if (arr[0] > arr[1]){    
	temp = arr[0];
	arr[0] = arr[1];
	arr[1] = temp;
}
//arr = {2,6,1,12}

//第1位与第2位进行比较   第2次比较
if (arr[1] > arr[2]){  
	temp = arr[1];
	arr[1] = arr[2];
	arr[2] = temp;
}
//arr = {2,1,6,12}

/**
		//第2位与第3位进行比较  第3次比较
		if (arr[2] > arr[3]){
			temp = arr[2];
			arr[2] = arr[3];
			arr[3] = temp;
		}
		//arr = {2,1,6,12}
*/

经过第二趟的循环和比较,第二大数字已经跑到倒数第二位置了(可以看到第2趟,比较2次得到,第3次是完全不需要的) 继续第三趟...这时候数组是从 arr = {2,1,6,12} 开始。

//第0位与第1位进行比较(这里指数组的下标)   第1次比较
if (arr[0] > arr[1]){    
	temp = arr[0];
	arr[0] = arr[1];
	arr[1] = temp;
}
//arr = {1,2,6,12}

这里比较的第2、第3次省略不写 如果是以循环的方式写,那么想要省略,就涉及到优化问题,后面会讲到

经过第三趟已经得到了排序好数组 第三趟,比较了1次

总结一下规律

  1. 循环长度为4的组数,需要的躺数为 arr.length - 1;
  2. 在每一躺过程中,比较的次数是 每走一趟就少一次,即可以表示为 arr.length - i -1(i从数组下标0开始)

for循环实现

public int[] BubbleSort(int[] arr){
	int temp;
	
	//循环躺数
	for (int i = 0; i < arr.length - 1; i++){
	
	//循环比较的次数
		for(int j = 0; j < arr.length - i - 1; j++){
		
			if(arr[j] > arr[j+1]){
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
			
		}
	}
	System.out.println(Arrays.toString(arr));
	return arr;
}

冒泡排序优化

前面说了优化问题,例如定义一个数组 int[] arr = {5,4,7,11} 最后一趟的时候,只需要比较一次就能够完成排序,但是循环是一直下去的 很简单,在比较完后设置它已经交换过,然后跳出循环即可

public int[] BubbleSortOpt(int[] arr){
	int temp;
	
	//循环躺数
	for (int i = 0; i < arr.length - 1; i++){
	
	boolean  isChange = false;
	
	//循环比较的次数
		for(int j = 0; j < arr.length - i - 1; j++){
		
				if(arr[j] > arr[j+1]){
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;

					//设置已经交换状态
					isChange = true;
				}

			}
		
			//如果没有交换说明已经交换完成,跳出这一趟
			if(!isChange){
				break;
			}
		
	}
	System.out.println(Arrays.toString(arr));
	return arr;
}

不一定是最好的实现方式,有错误请指出,不胜感激! 冒泡排序:ShutDown...

1评论
  • Aquan

    |´・ω・)ノ