冒泡排序原理和JAVA实现

 

冒泡排序是一种比较排序，下面我实现一个从小到大的冒泡排序：

先定义两个变量：

    待排序数组：int[] source;

    数组长度  length = source.length;

 

原理如下：

1、开始：有length-1次循环，每次参与循环的是未排序的数。第一次参与循环的是整个数组，因为假设整个数组是无序的。

    每次循环需要设置一个标志位： boolean flag = false;表示循环过程中是否产生了交换。

2、过程：循环过程中， 相邻的两个元素进行比较，如果source[j] > source[j+1]，则交换两者顺序，同时标志位flag = true;表示产生了交换。每一次循环结束后，最大数沉到未排序部分的尾部，每次循环找出一个最大数。

3、结束：每次循环结束后，如果标志位flag未改变的话，证明未排序的部分中没有source[j] > source[j+1]，即未排序部分已经有序，这时，跳出循环，排序结束。

   或者length-1次循环结束后，数组有序。

 

    为什么是length-1次而不是length循环，因为每次循环找出一个最大数，沉下去，length-1次循环后，只剩下一个元素，不需要进行任何比较，它就是最小的。

 

JAVA代码如下：

 

[java] view plaincopyprint?

1. package sort;  
2. import java.util.Scanner;  
3. public class bubbleSort {  
4.     public void sort(int[] source){  
5.         int length = source.length;  
6.         boolean flag = false;  
7.         for(int i=1;i<=length-1;++i){  
8.             flag = false;  
9.             for(int j=0;j<length-i;++j){  
10.                 if(source[j] > source[j+1]){  
11.                     int temp = source[j];  
12.                     source[j] = source[j+1];  
13.                     source[j+1] = temp;  
14.                     flag = true;  
15.                 }  
16.             }  
17.             if(flag == false)  
18.                 break;  
19.         }  
20.     }  
21.       
22.     public static void main(String[] args){  
23.         Scanner in = new Scanner(System.in);  
24.         bubbleSort bs = new bubbleSort();  
25.         while(in != null){  
26.             int num = in.nextInt();  
27.             int[] source = new int[num];  
28.             for(int i=0;i<num;++i){  
29.                 source[i] = in.nextInt();  
30.             }  
31.             bs.sort(source);  
32.             for(int a:source){  
33.                 System.out.print(a+" ");  
34.             }  
35.             System.out.println();  
36.         }  
37.     }  
38. }