`
greenwen
  • 浏览: 216032 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

冒泡排序算法分析

阅读更多
基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

在一般情况下,人们写出的冒泡排序算法是下面这种,但这种并不是正宗的冒泡排序
	public int[] bubbleSort1(int[] bubbleSortArray){
	int temp = 0;
	
	for(int i = 0; i < bubbleSortArray.length-1; i++){
		for(int j = 0; j < i; j++){
			if(bubbleSortArray[j] < bubbleSortArray[i]){
				temp = bubbleSortArray[j];
				bubbleSortArray[j] = bubbleSortArray[i];
				bubbleSortArray[i] = temp;
			}
		}
	}
	
	return bubbleSortArray;
}


以下才是正确的冒泡排序:
// BubbleSort
public int[] bubbleSort2(int[] bubbleSortArray){
	int temp = 0;
	
	for(int i = 0; i<bubbleSortArray.length-1; i++){
		for(int j = 0; j < bubbleSortArray.length-1-i; j++){
			if(bubbleSortArray[j] > bubbleSortArray[j+1]){
				temp = bubbleSortArray[j];
				bubbleSortArray[j] = bubbleSortArray[j+1];
				bubbleSortArray[j+1] = temp;
			}
		}
	}
	
	return bubbleSortArray;
}


上面的冒泡排序还有优化的空间,在内层循环已经有序时,无需再循环下去了
public int[] bubbleSort3(int[] bubbleSortArray){
	int temp = 0;
	boolean needNextPass = true;  
	for(int i = 0; i<bubbleSortArray.length-1 && needNextPass; i++){
		needNextPass = false;
		for(int j = 0; j < bubbleSortArray.length-1-i; j++){
			if(bubbleSortArray[j] > bubbleSortArray[j+1]){
				temp = bubbleSortArray[j];
				bubbleSortArray[j] = bubbleSortArray[j+1];
				bubbleSortArray[j+1] = temp;
				needNextPass = true;
			}
		}
	}
	
	return bubbleSortArray;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics