Java教程

冒泡排序(不是很详细)

本文主要是介绍冒泡排序(不是很详细),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、冒泡排序



1.1 冒泡排序基础【必会知识】

  冒泡排序是比较基础的排序算法之一,其思想是相邻的元素两两比较,较大的数下沉,较小的数冒起来,这样一趟比较下来,最大(小)值就会排列在一端。整个过程如同气泡冒起,因此被称作冒泡排序。
  冒泡排序的步骤是比较固定的:

1>比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2>每趟从第一对相邻元素开始,对每一对相邻元素作同样的工作,直到最后一对。
3>针对所有的元素重复以上的步骤,除了已排序过的元素(每趟排序后的最后一个元素),直到没有任何一对数字需要比较。

此处引用网上一张比较经典的gif来展示冒泡排序的整个过程:

  冒泡排序的常规实现代码如下:

	public static void bubbleSort(int[] arr) {
		/*判断数组为空或为一个元素的情况,即边界检查*/
		if (arr == null || arr.length < 2) {
			return;
		}
		
		/*规定每次两两比较的末尾元素的位置,最多为数组的最后一个位置*/
		for (int end = arr.length - 1; end > 0; end--) {
			/*从第一个元素开始,两两进行比较,如果前面的元素大于后面的
			  元素,就交换,最终的结果就是最大的数在最后面
			*/
			for (int i = 0; i < end; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

1.2 冒泡排序优化

  上个章节介绍了冒泡排序的常规实现,但是这种最简单的排序是存在着不必要的比较动作的。稍微修改上述代码,就可以查看每次比较后的结果:

        int[ ] array=new int[ ]{5,2,3,9,4};
        /*外循环为排序趟数,array.length个数进行array.length-1趟 */
        for(int i=0;i<array.length-1;i++){
        	/*内循环为每趟比较的次数,第i趟比较array.length-i次 */
            for(int j=0;j<array.length-1-i;j++){
            	 /*相邻元素比较,若满足条件则交换(升序为左大于右,降序反之) */
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
                /*查看每趟比较后的数组元素*/
                System.out.println("第 "+(i+1)+" 趟,第 "+(j+1)+" 次比较后的结果:");
                for(int k=0;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
        }

该代码的输出结果为:

第 1 趟,第 1 次比较后的结果:
2 5 3 9 4
第 1 趟,第 2 次比较后的结果:
2 3 5 9 4
第 1 趟,第 3 次比较后的结果:
2 3 5 9 4
第 1 趟,第 4 次比较后的结果:
2 3 5 4 9
第 2 趟,第 1 次比较后的结果:
2 3 5 4 9
第 2 趟,第 2 次比较后的结果:
2 3 5 4 9
第 2 趟,第 3 次比较后的结果:
2 3 4 5 9
第 3 趟,第 1 次比较后的结果:
2 3 4 5 9
第 3 趟,第 2 次比较后的结果:
2 3 4 5 9
第 4 趟,第 1 次比较后的结果:
2 3 4 5 9
 

从上面的测试结果可以看出,从第2趟第3次比较后,数组元素已经处于有序状态,此后所有的比较都不必进行。

1.2.1 外循环优化
  第一种优化就基于上面的测试结果来进行,如果某次比较过程中,发现没有任何元素移动,则不再进行接下来的比较。具体的做法是在每趟比较时,引入一个boolean型变量isSwap,来判断下次比较还有没有必要进行。示例代码如下:
 

        int[ ] array=new int[ ]{5,2,3,9,4};
        /*外循环为排序趟数,array.length个数进行array.length-1趟 */
        for(int i=0;i<array.length-1;i++){
        	boolean isSwap=false;
        	/*内循环为每趟比较的次数,第i趟比较array.length-i次 */
            for(int j=0;j<array.length-1-i;j++){
            	 /*相邻元素比较,若满足条件则交换(升序为左大于右,降序反之) */
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    isSwap=true;
                }
                /*查看每趟比较后的数组元素*/
                System.out.println("第 "+(i+1)+" 趟,第 "+(j+1)+" 次比较后的结果:");
                for(int k=0;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
            /*如果没有交换过元素,则已经有序,不再进行接下来的比较*/
            if(!isSwap){
            	break;
            }
        }

  测试结果如下:

第 1 趟,第 1 次比较后的结果:
2 5 3 9 4
第 1 趟,第 2 次比较后的结果:
2 3 5 9 4
第 1 趟,第 3 次比较后的结果:
2 3 5 9 4
第 1 趟,第 4 次比较后的结果:
2 3 5 4 9
第 2 趟,第 1 次比较后的结果:
2 3 5 4 9
第 2 趟,第 2 次比较后的结果:
2 3 5 4 9
第 2 趟,第 3 次比较后的结果:
2 3 4 5 9
第 3 趟,第 1 次比较后的结果:
2 3 4 5 9
第 3 趟,第 2 次比较后的结果:
2 3 4 5 9

从上面的测试结果可以看出,已经对排序过程进行了优化,因为没有进行第4趟比较。也许有人会有疑问“第2趟比较结束后,数组已经有序了,为什么还要进行第3次比较”?之所以对此有疑问,可能是没太清楚isSwap变量的作用,该变量的作用是“假如本趟比较过程中没有交换发生,则不必进行下一趟比较”,在第2趟比较过程中,发生了交换动作,所以第3趟比较仍会进行。

这篇关于冒泡排序(不是很详细)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!