81 Collections.sort(ArrayList, Comparator) 是否是稳定的排序

前言

之前碰到了这样的一个问题?

Collections.sort 的排序是否稳定, 一下关于 排序算法稳定性 的描述摘录自百度百科?

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

我映像中 Collections.sort, 的排序是委托给了 Arrays.sort, 然后 Arrays.sort 似乎是兼容了多种场景选择了不同的排序方式, 比如 当数量小于某一阈值的时候使用了一种算法, 否则使用的双枢轴快速排序 吧?

快速排序是不稳定的, 那么就是不稳定的 ??

然后 查看了一下 Arrays.sort, 对于 几种基础类型的数组似乎是可能使用到 双枢轴快速排序, 而对于引用类型的数组的排序 是使用的 TimSort?

对于 byte[] 排序, 大于阈值 29 的时候使用的是 计数排序(经典算法), 小于阈值使用的是 插入排序?

对于 short[], char[] 排序, 大于预制 3200 的时候使用的是 计数排序, 小于阈值的时候使用的是 双枢轴排序?

对于 int[], long[], 小于 286 的时候使用的是 普通快速排序, 大于阈值的时候使用的是 双枢轴快速排序?

对于 flot[], double[] ... 这个就看不懂了 ...?

对于 Object[], 使用的是 遗留的归并排序 或者?ComparableTimSort?

测试用例

package com.hx.test04;

import java.util.*;

/**
 * CollectionsSort
 *
 * @author Jerry.X.He <970655147@qq.com>
 * @version 1.0
 * @date 2020-04-01 18:39
 */
public class Test23CollectionsSort {

  // Test23CollectionsSort
  public static void main(String[] args) {

    List<String> list = new ArrayList<>();
//    list.addAll(Arrays.asList("a", "b", "c", "d", "e"));
    list.addAll(Arrays.asList("c", "a", "b", "d", "e"));

    Collections.sort(list, MyStringComparator.INSTANCE);
//    Collections.sort(list, MyStringComparator.INSTANCE);
//    Collections.sort(list, MyStringComparator.INSTANCE);

    int x = 0;

  }

  /**
   * MyStringComparator
   *
   * @author Jerry.X.He <970655147@qq.com>
   * @version 1.0
   * @date 2020-04-01 18:41
   */
  static class MyStringComparator implements Comparator<String> {
    // INSTANCE
    public static MyStringComparator INSTANCE = new MyStringComparator();

    @Override
    public int compare(String o1, String o2) {
      return 0;
    }
  }

}

排序结果 和 输入的结果一致?

这里的 Comparator 将各个 输入字符串视为相同, 走的时候这里的 TimSort 是一种稳定的排序, 因此 输入输出 顺序相同

TimeSort 核心代码

1. 如果需要排序的长度为 1 或者 0 则直接返回, 本身就有序, 剪枝

2. 如果需要排序的长度小于 MIN_MERGE[32], 则直接进行二分排序?

3. 循环每一个批次的数据(max(minLen, runLen)), 如果这个批次的数据不是有序, 则先试用 二分排序对本批次数据进行排序, 如果不满足给定的限定进行 merge, 循环结束 对所有的批次的数据进行 merge?

为什么需要, 循环 mergeCollapse 呢 ?.. 网上搜索了一下, 我也不知道?

countRunAndMakeAscending

查找 lo 开始的 n 个连续的升序 或者 降序的数据, 如果是降序的话, 反转 [lo, lo+n]?

返回 n?

binarySort

从 start 开始(这里上下文的场景下面 [lo, start] 这个分段的数据是有序的), 二分查找找到 a[start] 应该放置的位置 idx, 然后移动 a[idx] - a[start] 向后移动一个单位, 然后更新 a[idx] 为 pivot?

然后 依次向后处理, 查找 a[start] 应该放置的位置, 然后 移动该位置之后的元素, 放置 a[start] 到应该放置的位置?

类似于插入排序, 不过对于 查询 a[start] 的位置使用的是二分查找?

mergeCollapse &?mergeForceCollapse

mergeAt 的细节我们暂时就不看了, 就是将 (base[n], runLen[n]) 和?(base[n+1], runLen[n+1]) 进行 merge?

完?