一、从分治说起

二、快速排序

快排就是在首尾之间找一个任意值(假设该值的位置为 p)，将比它大的放到右边，比它小的放到左边。
再将左右两边各看成一个要排序的数组，再从中找出一个任意值，将比它大的放到右边，比它小的放到左边。
如此往复，直到要排序的数组中只剩下两个或者一个值。

 // 快速排序，a是数组，n表示数组的大小
  public static void quickSort(int[] a, int n) {
    quickSortInternally(a, 0, n-1);
  }

  // 快速排序递归函数，p,r为下标
  private static void quickSortInternally(int[] a, int p, int r) {
    if (p >= r) return;

    int q = partition(a, p, r); // 获取分区点
    quickSortInternally(a, p, q-1);
    quickSortInternally(a, q+1, r);
  }

  private static int partition(int[] a, int p, int r) {
    int pivot = a[r];
    int i = p;
    for(int j = p; j < r; ++j) {
      if (a[j] < pivot) {
        if (i == j) {
          ++i;
        } else {
          int tmp = a[i];
          a[i++] = a[j];
          a[j] = tmp;
        }
      }
    }

    int tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;

    System.out.println("i=" + i);
    return i;
  }

三、归并排序

三、源码解析——sort()

在Java中，sort()是 JDK 提供的排序算法。他可以为 Arrays 和 Collections 及其子类进行排序。

1.Arrays.sort()

基本数据类型数组

在 Arrays 中，参数为 int 数组的 sort() 函数

public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, (int[])null, 0, 0);
}

public static void sort(int[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, (int[])null, 0, 0);
}

我们可以看到，只有数组一个参数时，由 DualPivotQuicksort.sort 直接排序；
当参数还包括起始下标时，会先使用 rangeCheck() 对传入参数进行检查。
不过，无论传入参数如何设置，他们最终都将传递给 DualPivotQuicksort.sort 进行排序。

下面我们就来看看 DualPivotQuicksort.sort 是如何进行排序的呢?

DualPivotQuicksort.sort

在第一行我们可以看到，sort 先进行长度的判断，当长度小于 286 时，就转入到另一个 sort 中进行排序，长度大于 286 的

if (right - left < 286) {
            sort(a, left, right, true);
} else {
    //此处省略
}

Object 数组

Collection.sort()

在 Collection 中，我们可

TimSort