冒泡排序原理和JAVA实现

分类： Algorithm2010-12-17 16:23 1658人阅读 评论(1) 收藏 举报

javastringclassnull

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

先定义两个变量：

    待排序数组：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 plaincopy

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;j10.                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;i29.                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.}  

分享到：