冒泡排序

/**
* @author jy
* @date 2018年6月7日
* <p>Description: </p> 
*/
package sort;

import java.util.Arrays;

/**
* @author jy
*/
public class BubbleSort {

  public void bubbleSort(int a[]) {

      // 长度为n的数组，只需要n-1趟
      // 两两比较，大的就放在最后
      for (int i = 0; i < a.length - 1; i++) {
          for (int j = 0; j < a.length - 1 - i; j++) {
              if (a[j] > a[j + 1]) {
                  swap(a, j, j + 1);
              }
          }
      }
  }

  /**
   * @param a
   * @param j
   * @param i
   *            <p>
   *            Description:
   *            </p>
   */
  private void swap(int[] a, int j, int i) {

      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;

  }

  /**
   * @param args
   *            <p>
   *            Description:
   *            </p>
   */
  public static void main(String[] args) {

      int a[] = { 8, 61, 1, 9, 6 };
      BubbleSort s = new BubbleSort();
      s.bubbleSort(a);
      System.out.println(Arrays.toString(a));

  }

}

通过从左到右不断交换相邻逆序的相邻元素，在一轮的交换之后，可以让未排序的元素上浮到最右侧，是的右侧是已排序的。
一次数据比较和交换算一次，共需n-1+(n-2)+...+1=n(n-1)/2 。故时间复杂度为O（n^2）

优化：如果在中间的某一步已经有序了，不需要再继续遍历了。

    public void bubbleSort(int a[]) {

        // 长度为n的数组，只需要n-1趟
        // 两两比较，大的就放在最后
        boolean flag=false;
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    flag=true;
                }
            }
            if(flag==false){
                System.out.println("break");
                break;
            }
        }
    }