Collections.sort实现对算法Timsort的简单理解

实验示例:

 @Test
    public void printListIntegerSort() {
        List<Integer> list = new ArrayList();
        list.add(15);
        list.add(123);
        list.add(10);
        list.add(91);
        list.add(69);
        list.add(92);
        list.add(3);
        for (int i = 0; i < 80; i++) {
            list.add((int) (Math.random() * 100));
        }
        // 常规的排序
        Collections.sort(list);
        // 打印出数据
        for (Integer str : list) {
            System.out.println(str);
        }
    }

直接对长度小于32的数组进行二进制插入和排序

   /**
     * 简化的二分插入排序例子
     数组a[1...n]中，把后一个pivot和前面排序好的（范围：left < right）进行比较交换
     */
    @Test
    public void binarySort() {
        Object[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1};
        int lo = 0;
        for (int start = 1; start < a.length; start++) {
            Comparable pivot = (Comparable) a[start];
            int left = lo;
            int right = start;
            while (left < right) {
                // 二分插入排序获取中值
                int mid = (left + right) >>> 1;
                if (pivot.compareTo(a[mid]) < 0) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            int n = start - left;
            switch (n) {
                case 2:
                    a[left + 2] = a[left + 1];
                case 1:
                    a[left + 1] = a[left];
                    break;
                default:
                    System.arraycopy(a, left, a, left + 1, n);
            }
            a[left] = pivot;
        }
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

大于32的数组直接执行二进制插入排序和复杂合并排序.

运行的概念是将多个二进制数组插入已排序的数组awk数组排序，然后合并并运行多个运行的数组. 在合并排序算法中，合并两个数组是将每个元素一一比较awk数组排序，然后将较小的元素放入相应的位置，然后进行比较. 具体过程非常复杂:

参考: 世界上最快的排序算法——Timsort

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-270445-1.html