冒泡排序算法

冒泡排序的实现

/**
	功能：数组排序（无序数组-----有序数组）
	排序算法很多，冒泡排序，选择排序，插入排序，是三种最基本最简单的排序算法，效率最低
	技能：冒泡排序
	
	冒泡排序的算法
	 *  1.整个数列分成两部分：前面是无序数列，后面是有序数列
	 *  2.初始状态下，整个数列都是无序的，有序数列是空
	 *  3.如果一个数列有n个元素，则至多需要n-1趟循环才能保证数列有序
	 *  4.每一趟循环可以让无序数列中最大数排到最后，（也就是说有序数列的元素个数增加1）
	 *  5.每一趟循环都从数列的第一个元素开始进行比较，依次比较相邻的两个元素，比较到无序数列的末尾即可（而不是数列的末尾）
	 *  6.如果前一个大于后一个，交换

*/
public class TestBubbleSort{
	public static void main(String [] args){
		//定义一个无序数组
		int [] scoreArr = {75,87,56,45,89,100,76,34,89,97};	
		
		//排序前输出
		System.out.println("排序前");
		for(int score :scoreArr){
			System.out.print(score+"\t");
		}
		//排序
		//大循环：n个元素排序，则至多需要n-1趟循环
		for(int i=0;i<scoreArr.length-1;i++){
			//小循环：每一趟循环都从数列的前两个元素开始进行比较，比较到数组的最后
			for(int j=0;j<scoreArr.length-1;j++){
				//如果前一个大于后一个
				if(scoreArr[j] > scoreArr[j+1]){
					//交换
					int temp;
					temp = scoreArr[j];
					scoreArr[j] = scoreArr[j+1];
					scoreArr[j+1] = temp;
				}
			}
		}
		//排序后输出
		System.out.println("排序后");
		for(int score :scoreArr){
			System.out.print(score+"\t");
		}
	}
}

冒泡排序的分析：
    空间效率：仅使用一个辅存单元。
    时间效率：假设待排序的元素个数为 n，则总共要进行 n-1 趟排序，对 j 个元素的子序
列进行一趟起泡排序需要进行 j-1 次关键字比较。由此，起泡排序的总比较次数为
 
因此，起泡排序的时间复杂度为Ο(n2 )。
稳定性：稳定