package com.xj.www.sort;
/**
 * 合并排序算法
 *
 * @author xiongjing
 *
 */
public class MerageSort {
      final static int SIZE = 10;
      // 合并排序算法具体实现
      public static void merageOne(int a[], int b[], int n, int len) {
            int i, j, k, s, e;
            s = 0;
            while (s + len < n) {
                  e = s + 2 * len - 1;
                  // 最后一段可能少于len个结点
                  if (e >= n) {
                        e = n - 1;
                  }
                  // 相邻有序段合并
                  k = s;
                  i = s;
                  j = s + len;
                  // 如果两个有序表都未结束时，循环比较
                  while (i < s + len && j <= e) {
                        // 如果较小的元素复制到数组b中
                        if (a[i] <= a[j]) {
                              b[k++] = a[i++];
                        } else {
                              b[k++] = a[j++];
                        }
                  }
                  // 未合并的部分复制到数组b中
                  while (i < s + len) {
                        b[k++] = a[i++];
                  }
                  // 未合并的部分复制到数组b中
                  while (j <= e) {
                        b[k++] = a[j++];
                  }
                  // 下一对有序段中左段的开始下标
                  s = e + 1;
            }
            if (s < n) {
                  for (; s < n; s++) {
                        b[s] = a[s];
                  }
            }
      }
      // 合并排序
      public static void merageTwo(int a[], int n) {
            int h, count, len, f;
            // 排序步骤
            count = 0;
            // 有序序列的长度
            len = 1;
            // 变量f为标志
            f = 0;
            int[] p = new int[n];
            while (len < n) {
                  // 交替在A和P之间合并
                  if (f == 1) {
                        // p合并到a
                        merageOne(p, a, n, len);
                  } else {
                        // a合并到p
                        merageOne(a, p, n, len);
                  }
                  // 增加有序序列茶高度
                  len = len * 2;
                  // 使f值在0和1之间切换
                  f = 1 - f;
                  count++;
                  // 输出每步排序的结果
                  System.out.print("第" + count + "步排序结果：");
                  for (h = 0; h < SIZE; h++) {
                        System.out.print(" " + a[h]);
                  }
                  System.out.print("\n");
            }
            // 如果进行了排序
            if (f == 1) {
                  for (h = 0; h < n; h++) {
                        // 将内存p中的数据复制回数组a
                        a[h] = p[h];
                  }
            }
      }
      // 程序主入口
      public static void main(String[] args) {
            int[] shuzu = new int[SIZE];
            int i;
            for (i = 0; i < SIZE; i++) {
                  shuzu[i] = (int) (100 + Math.random() * (100 + 1));
            }
            System.out.println("排序前的数组为：");
            for (i = 0; i < SIZE; i++) {
                  System.out.print(shuzu[i] + " ");
            }
            System.out.print("\n");
            merageTwo(shuzu, SIZE);
            System.out.println("排序后的数组为：");
            for (i = 0; i < SIZE; i++) {
                  System.out.print(shuzu[i] + " ");
            }
            System.out.print("\n");
      }
}