冒泡排序（Java实现）

冒泡排序

冒泡排序的思想：每一次将最大的数字往数组的最右边排序

                           假如一个数组有n个元素，则最多需要n-1趟就可以完成排序。

冒泡排序的时间复杂度：O(n^2).

图解实现(来自参考资料)：

                                                                                        冒泡排序

来，话不多说，先上实现程序

1publicstaticvoid bubbleSort(int[] arr){

2     int n = arr.length;

3     //循环最多n-1趟排序

4     for(int i=0;i<n-1;i++){

5         boolean flag = false;   //这里定义一个标志位，先不要管它的作用，下面会解释

6         //循环每一趟中的单次排序（确定一个最大的数）

7         for(int j=0;j<n-1-i;j++) {  //这里减 i 的原因 是每完成一次排序就少一个需要排序的元素

8             if (arr[j] > arr[j + 1]) {

9                 //交换两数(利用异或运算实现两数交换(不需要额外定义一个变量))

10                 arr[j] ^= arr[j + 1];

11                 arr[j + 1] ^= arr[j];

12                 arr[j] ^= arr[j + 1];

13                 //成功交换则将标志位置位true

14                 flag = true;

15            }

16        }

17         //如果在某一趟循环完毕了，而标志位flag还是false，说明此时数组已经完全排序好，此时可以结束程序，达到提高效率的作用。

18         //这就是我要设置标志位flag的意义之处。

19         if(flag == false){

20             break;

21        }

22    }

23 }

　　测试代码：

1  publicstaticvoid main(String[] args) {

2         int[] arr = newint[]{5,2,4,9,8,3};

3        bubbleSort(arr);

4         for (int i: arr)

5             System.out.print(i+" ");

6     }

   测试结果：

2 3 4 5 8 9

现在我们来思考一下冒泡排序是否是稳定的排序？

    是稳定的。它不断的循环,相同的数排在前面的还是排在前面,不会改变顺序。