排序算法之冒泡排序

标签: 排序算法  Java

        排序算法是数据结构与算法中重要的一部分,而冒泡排序又是排序算法中最简单的一种。是我们必须要掌握的知识点,今天我们就来学习一下这种最简单的排序算法--冒泡排序

        冒泡排序顾名思义,就是遍历数组相邻的数字两两比较,如果无序就进行交换,这种交换遍历一次就会将最大得数或最小的数字移动到数组的末尾,就像吐泡泡一样。



下面我们用代码来实现一下:

public static  int[] bubbleSort(int [] arr){
	int len = arr.length-1;
		
	for(int i =len;i>=0;i--){ //外层大循环
			
		Boolean flag = true; //如果数组已经有序进行终止的标识 
			
		for(int j =0;j<i;j++){ //完成一趟冒泡
				
			if(arr[j]>arr[j+1]){ //判断数组中相邻两数字是否有序
					
				int temp = arr[j];
					
				arr[j] = arr[j+1];  //如果无序进行两两交换
					
				arr[j+1] = temp;
					
				flag = false; //如果数组无序,进行了排序flag=false
			}
		}
		if(flag){ //如果flag=true  说明进行了一趟循环 数组没有进行交换已经有序,跳出循环
			break;
		}
			
		}
		
	return arr;
}

        我们看到冒泡排序需要两层for循环,所以他的最坏时间复杂度为O(n2)

        我们在代码中添加了 一个flag标识,如果一趟循环中,一次交换也没有发生,那么说明这组数据已经有序了,我们跳出循环。所以冒泡排序最好情况的时间复杂度为O(n)即只需扫描一遍数组。

        同时,由于冒泡排序在实现过程中只有两两数字大小不一致时才会交换,所以如果两个相等的数字,冒泡排序并不会将二者的位置更改,所以冒泡排序是一个稳定的排序算法。




版权声明:本文为Zhang_hongxin原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Zhang_hongxin/article/details/80977221