package com.study.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序。
 *
 * <p><B>排序原理：</B>
 * <ol>
 * <li>比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
 * <li>对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。
 * </ol>
 *
 * <p><B>时间复杂度分析：</B>冒泡排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码。
 * 所以，我们分析冒泡排序的时间复杂度，主要分析一下内层循环体的执行次数即可。
 *
 * <p>在最坏的情况下，也就是假如要排序的元素为 {@code {6,5,4,3,2,1}} 逆序，那么：
 * 元素比较的次数为：{@code (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2}，
 * 元素交换的次数为：{@code (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2}，
 * 总共执行次数为：{@code (N^2/2-N/2)+(N^2/2-N/2)=N^2-N}。
 * 按照大O推导法则，保留函数中的最高阶项，那么最终冒泡排序的时间复杂度为 <B>O(N^2)</B>。
 *
 * @author chenganbang
 */
public class Bubble implements Sort {

  private Bubble() {
  }

  private static class Holder {
    private static final Bubble INSTANCE = new Bubble();
  }

  public static Bubble getInstance() {
    return Bubble.Holder.INSTANCE;
  }

  /**
   * 对数组 source 进行排序。
   * <p>假设待排序数组：[4, 5, 6, 3, 2, 1]，那么排序过程如下：
   * <ul>
   * <li>第 1 趟排序结果：[4, 5, 3, 2, 1, <B>6</B>]
   * <li>第 2 趟排序结果：[4, 3, 2, 1, <B>5</B>, 6]
   * <li>第 3 趟排序结果：[3, 2, 1, <B>4</B>, 5, 6]
   * <li>第 4 趟排序结果：[2, 1, <B>3</B>, 4, 5, 6]
   * <li>第 5 趟排序结果：[1, <B>2</B>, 3, 4, 5, 6]
   * </ul>
   * 排好序结果：[1, 2, 3, 4, 5, 6]
   *
   * @param source
   *     待排序数组
   */
  @Override
  public void sort(Comparable[] source) {
    if (source == null || source.length == 0) {
      return;
    }
    System.out.println("待排序数组：" + Arrays.toString(source));

    SortHelper sortHelper = SortHelper.getInstance();
    for (int i = source.length - 1; i > 0; i--) {
      for (int j = 0; j < i; j++) {
        if (sortHelper.greater(source[j], source[j + 1])) {
          sortHelper.exchange(source, j, j + 1);
        }
      }
      sortHelper.printArray(source.length - i, source);
    }

    System.out.println("排好序结果：" + Arrays.toString(source));
  }
}