归并排序处理复杂对象例子

对象TmpObject 包含了一个 int类型的变量，有一个List<TmpObject> 数组，如何根据这个int变量，进行归并排序？

  1 import java.util.ArrayList;
  2 import java.util.List;
  3 
  4 /**
  5  * 归并排序（递归）
  6  */
  7 public class Merge {
  8     public static void main(String[] args) {
  9         List<TmpObject> list = new ArrayList<>();
 10         list.add(new TmpObject(6));
 11         list.add(new TmpObject(5));
 12         list.add(new TmpObject(3));
 13         list.add(new TmpObject(8));
 14         list.add(new TmpObject(1));
 15         list.add(new TmpObject(7));
 16         list.add(new TmpObject(2));
 17         list.add(new TmpObject(9));
 18         list.add(new TmpObject(5));
 19 
 20         System.out.println("归并前输出：");
 21         for (TmpObject tmp : list) {
 22             System.out.print(tmp.getNum() +" ");
 23         }
 24 
 25         segment(list, 0, list.size() - 1);
 26 
 27         System.out.println("
归并后输出：");
 28         for (TmpObject tmp : list) {
 29             System.out.print(tmp.getNum() +" ");
 30         }
 31     }
 32 
 33     /**
 34      * 递归切分待排
 35      *
 36      * @param list  待切分数组
 37      * @param left  待切分最后第一个元素的索引
 38      * @param right 待切分数组最后一个元素的索引
 39      */
 40     private static void segment(List<TmpObject> list, int left, int right) {
 41         if (left < right) {
 42             // 找出中间索引
 43             int center = (left + right) / 2;
 44             // 对左边数组进行递归
 45             segment(list, left, center);
 46             // 对右边数组进行递归
 47             segment(list, center + 1, right);
 48             // 合并
 49             merge(list, left, center, right);
 50         }
 51     }
 52 
 53     /**
 54      * 两两归并排好序的数组（2路归并）
 55      *
 56      * @param list   带排序数组对象
 57      * @param left   左边数组的第一个索引
 58      * @param center 左数组的最后一个索引，center + 1右数组的第一个索引
 59      * @param right  右数组的最后一个索引
 60      */
 61     private static void merge(List<TmpObject> list, int left, int center, int right) {
 62         List<TmpObject> tmpArray = new ArrayList<TmpObject>(right - left + 1);
 63         int leftIndex = left;   //左数组第一个元素的索引
 64         int rightIndex = center + 1;   //右数组第一个元素索引
 65 
 66         // 把较小的数先移到新数组中
 67         while (leftIndex <= center && rightIndex <= right) {
 68             if (list.get(leftIndex).getNum() <= list.get(rightIndex).getNum()) {
 69                 tmpArray.add(list.get(leftIndex++));
 70             } else {
 71                 tmpArray.add(list.get(rightIndex++));
 72             }
 73         }
 74 
 75         //把左边剩余的数移入数组
 76         while (leftIndex <= center) {
 77             tmpArray.add(list.get(leftIndex++));
 78         }
 79 
 80         // 把右边边剩余的数移入数组
 81         while (rightIndex <= right) {
 82             tmpArray.add(list.get(rightIndex++));
 83         }
 84 
 85         // 把新数组中的数覆盖nums数组
 86         for (int i = 0; i < tmpArray.size(); i++) {
 87             list.set(left + i, tmpArray.get(i));
 88         }
 89     }
 90 }
 91 
 92 class TmpObject {
 93     private int num;
 94 
 95     TmpObject(int num) {
 96         this.num = num;
 97     }
 98 
 99     int getNum() {
100         return num;
101     }
102 
103     void setNum(int num) {
104         this.num = num;
105     }
106 }

输出结果为：

归并前输出：
6 5 3 8 1 7 2 9 5
归并后输出：
1 2 3 5 5 6 7 8 9

可以使用Comparator 比较器来直接比较list，而且它的排序方法是TimSort 算法：

//java8 中自定义Comparator 可以使用lambda 表达式
private static void sortList(List<TmpObject> list) {
    Comparator comp = (o1, o2) -> {
        TmpObject tmpFirst = (TmpObject) o1;
        TmpObject tmpSecond = (TmpObject) o2;
        return tmpFirst.getNum() - tmpSecond.getNum();
    };
    list.sort(comp);
}