冒泡排序 Bubble Sort

概述

通过对待排序序列从前向后，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部.

图解过程

原始数组：3，9，-1，10，20

第一趟排序：// 如果相邻的元素逆序就交换
1：3，9，-1，10，20 // 比较 3 和 9，不用交换
2：3，9，-1，10，20 // 比较 9 和 -1，交换位置
3：3，-1，9，10，20 // 比较 9 和 10，不用交换
4：3，-1，9，10，20 // 比较 10 和 20，不用交换；而且确定了最大值 20

第二趟排序：// 因为 20 是最大值，其实只需要比较前面 4 个就行了
1：-1，3，9，10，20 // 比较 3 和 -1，进行交换
2：-1，3，9，10，20 // 比较 3 和 9，不用交换
3：-1，3，9，10，20 // 比较 9 和 10，不用交换；确定了本轮最大值 10

第三趟排序：// 因为 10 是上一轮最大值，只需要比较前 3 个
1：-1，3，9，10，20 // 比较 -1 和 3，不用交换
2：-1，3，9，10，20 // 比较 3 和 9 ，不用交换；确定了本轮最大值 9

第四趟排序：// 上一轮最大值为 9，只需要比较前 2 个
1：-1，3，9，10，20 // 比较 -1 和 3，不需要交换，bending本轮最大值 3

造轮子

public void bubbleSort(int arr[]) 
   { 
       int n = arr.length; 
       for (int i = 0; i < n-1; i++) 
           for (int j = 0; j < n-i-1; j++) 
               if (arr[j] > arr[j+1]) 
               { 
                   // swap arr[j+1] and arr[j] 
                   int temp = arr[j]; 
                   arr[j] = arr[j+1]; 
                   arr[j+1] = temp; 
               } 
   }