排序算法总结

各种排序算法比较：

约定

待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。
使用辅助函数 less() 和 swap() 来进行比较和交换的操作，使得代码的可读性和可移植性更好。
排序算法的成本模型是比较和交换的次数。

public abstract class Sort<T extneds Comparable<T>> {
    public abstract void sort(T[] nums);

    protected boolean less(T v,T w) {
        return v.compareTo(w) < 0;
    }

    protected void swap(T[] a,int i,int j) {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

选择排序

从数组中选出最小的元素，将它和第一个元素交换，然后再从剩余数组中选出最小元素，将它与数组的第二个元素交换。不断进行比较直到整个数组有序。

选择排序需要 N*N/2 次比较和 N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

public class Selection<T extends Comparable<T>> extends Sort<T> {
    
    @Override
    public void sort(T[] nums) {
        int len = nums.length;
        for(int i = 0; i < len-1; i++) {
            int min = i;
            for(int j = i+1; j < len; j++) {
                if(less(nums[j],nums[min])) {
                    min = j;
                }
            }
            swap(nums,i,min);
        }
    }
}

冒泡排序

从左到右依次对比交换相邻的元素，一轮下来可以让数组中最大的元素浮到最右侧。
在一轮排序中，如果没有元素进行交换，则说明整个数组已经有序

public class Bubble<T extends Comparable<T>> extends Sort<T> {
    
    @Override
    public void sort(T[] nums) {
        int len = nums.length;
        boolean isSorted = false;
        for(int i = len - 1; i > 0 && !isSorted; i--){
            isSorted = true;
            for(int j = 0; j < i; j++) {
                if(less(nums[j+1],nums[j])) {
                    isSorted = false;
                    swap(nums,j,j+1);
                }
            }
        }
    }
}

插入排序

每次将当前元素插入到左侧（有序区）已经排序的数组中，使得插入之后的左侧数组依然有序。

排序算法的时间复杂度主要与数组的比较和移动次数有关。如果数组中已经部分有序，那么需要交换的次数也就较少，时间复杂度较低。

• 平均情况下插入排序需要 N * N/4 比较以及 N * N/4 次交换；
• 最坏的情况下需要 N * N/2 比较以及 N * N/2 次交换，最坏的情况是数组是倒序的；
• 最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。

public class Insertion<T extends Comparable<T>> extends Sort<T> {
    
    @Override
    public void sort(T[] nums) {
        int len = nums.length;
        for(int i = 1; i < len; i++) {
            //如果比较之后发现已经比有序区最大的大，那么不用交换，左边到当前位置已经有序，直接进行下一个元素的判断
            for(int j = i; j > 0 && less(nums[j],nums[j-1]); j--) {
                swap(nums,j,j-1);
            }
        }
    }
}

希尔排序

希尔排序是对直接插入排序的改进，对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

public class Shell<T extends Comparable<T> extends Sort<T>> {
    
    @Override
    public void sort(T[] nums) {
        int len = nums.length();
        int d = 1;//增量d

        while(d < N / 3) {
            d = 3 * d + 1;//相当于确定一个增量序列,必须要有一趟为1
        }

        while(d >= 1) {
            for(int i = d; i < len; i++) {
                for(int j = i; j >= d && less(nums[j],nums[j-d]); j -= d) {
                    swap(nums,j,j-d);
                }
            }
            d = d / 3;
        }
    }
}

归并排序

归并方法

归并方法用于将两个已经排序的部分归并成一个

public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> {
    protected T[] aux;
    
    /**
     * 将相邻的有序区间nums[i..m] 和 nums[m+1..n]归并为有序的nums[i,n]
     **/
    protected void merge(T[] nums,int i,int m,int n) {
        
        int k,j;

        for(k = i; k <= n; k++) {
            aux[k] = nums[k];
        }

        for(k = i, j = m + 1; i <= m || j <= n; k++) {
            if(aux[i].compareTo(aux[j]) <= 0) {
                //通过"<="保证有序
                nums[k] = aux[i++];
            } else {
                nums[k] = aux[j++];
            }
        }

        //复制剩余内容
        while(i <= m) nums[k++] = aux[i++];
        while(j <= n) nums[k++] = aux[j++];
    }
}

归并算法

将一个大数组分成两个小数组去求解。
因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。

public class Up2DownMergeSort<T extends Comparable<T>> extends MergeSort<T> {

    @Override
    public void sort(T[] nums) {
        aux = (T[]) new Comparable[nums.length];
        sort(nums,0,nums.length-1);
    }

    private void sort(T[] nums, int l, int h) {
        if(h <= l) {
            return;
        }
        int mid = (l + h) / 2;
        sort(nums,l,mid);
        sort(nums,mid+1,h);
        merge(nums,l,mid,h);
    }
}

快速排序

快速排序的基本思想是从代排序列中选定一个元素作为枢轴，通过元素与枢轴元素的比较将待排序序列划分成两个子序列，其中枢轴之前的子序列的所有元素都不大于枢轴，枢轴之后的所有元素都不小于枢轴。此时枢轴已到位，再用同样的方式对两个子序列进行递归快速排序，最终使得整个数组有序。

划分算法

快速排序算法首先从数组中选定一个元素作为枢轴，然后对枢轴两端进行遍历，左边从最左开始，右边从最右开始。
从数组的右端向左扫描找到第一个小于它的元素，将这个元素放在 l 位置，从数组的左端向右扫描直到找到第一个大于等于枢轴的元素，放到右边高端刚交换完空出的位置。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将枢轴的值放到该位置。

/**
 * 对子序列nums[l..h]进行一次划分
 **/
private int partition(T[] nums,int l,int h) {
    int i = l;
    int j = h;
    T v = nums[l];//提取枢轴元素，让出一个空间可以给其他元素交换

    while( i < j) {
        while(j != i && less(v,nums[j])) j--;//遍历枢轴右边直到找到第一个比枢轴小的元素
        nums[i] = nums[j];//把找到的元素放到左边
        while(i != j && less(nums[i],v)) i++;//遍历枢轴左边直到找到第一个比枢轴大的元素
        nums[j] = nums[i];//把元素放到右边
    }
    num[i] = v;//将枢轴元素放到该位置
    return i;//返回当前枢轴位置
}

基本算法

public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        sort(nums,0,nums.length-1);
    }

    private void sort(T[] nums,int l,int h) {

        if(l < h) {
            //获得一趟划分后的枢轴位置
            int pivotloc = partition(nums,l,h);
            sort(nums,l,pivotloc-1);//对枢轴之前的序列进行快排
            sort(nums,pivotloc+1,h);//对枢轴之后的序列进行快排
        }
    }
}

性能分析

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 C(N)=2C(N/2)+N，复杂度为 O(NlogN)。
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N*N/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

优化方式1：三分单向扫描

对于这样一个序列 2,2,2,2,3,1，使用上面提到的单轴快排中最简单的实现对其进行排序：选择第一个元素2 作为 pivot 中心点，划分后得到两段子序列分别为：1和2,2,3,2，接着继续递归对子序列进行排序，对于 2,2,3,2 子序列又是将 2 作为 pivot 中心点，会发现对于这种大量元素等于 pivot 的序列，单轴快排并没有起到很好的划分作用。如果将等于 pivot 的元素也作为一个划分区段，则可以将序列划分为3段：小于 pivot 的元素，等于 pivot 的元素，大于 pivot 的元素。这种处理方式，会大大节省递归次数

public void div3ScanSort(int[] items) {
    div3ScanSort(items, 0, items.length - 1);
}

public void div3ScanSort(int[] items,int start,int end) {
    if(start < end) {
        int privot = items[start];
        int i = start; //start到(i-1)是小于privot的元素
        int j = end; // j到end是大于privot的元素
        int k = start +1; //i到k-1是等于privot的元素
        //k到j则是待遍历元素
        while(k <= j) {
            if(items[k] > privot) {
                //如果比枢轴大，跟后面位置交换，同时j-1，将交换过来的元素继续比较，所以k不变
                swap(items, k, j);
                j--;
            } else if(items[k] < privot) {
                //如果比枢轴小，交换到枢轴左边，同时枢轴元素位置往前挪，待遍历元素往前移
                swap(items,k,i);
                k++;
                i++;
            } else {
                //如果一样大，则遍历元素往下移即可
                k++;
            }

            //因为枢轴已经包含在相等的情况里了，所以不用交换枢轴和i元素
        }

        div3ScanSort(items, start, i - 1);
        div3ScanSort(items, j + 1, end);
    }
}

优化方式2：三分双向扫描

在上面的实现中，扫描到大于 pivot 的元素，将最后一个未扫描的元素(j所在的位置)与当前元素(k所在的位置)进行交换。如果这个未扫描的元素正好是比 pivot 大的元素，无疑增加了交换的次数。

所以 j 索引应当扫描到一个不比 pivot 大的元素，再做交换，而如果 j==pivot，将k与j进行交换，否则继续执行 j-- 直到第一个小于等于 pivot 的元素出现：

public void div3DeScanSort(int[] items) {
    div3DeScanSort(items, 0, items.length - 1);
}

public void div3DeScanSort(int[] items, int start, int end) {
    if (start < end) {
        int pivot = items[start];
        int i = start, j = end, k = start + 1;

        OUT_LOOP: while (k <= j) {
            if (items[k] < pivot) {
                swap(items, i, k);
                i++;
                k++;
            } else if (items[k] == pivot) {
                k++;
            } else {
                // j向左扫描，直到一个不大于pivot的元素
                while (items[j] > pivot) {
                    j--;
                    if (k > j) {
                        // 后面的待排元素全大于pivot，直接结束排序
                        break OUT_LOOP;
                    }
                }
                if (items[j] < pivot) {
                    swap(items, j, k);
                    swap(items, i, k);
                    i++;
                } else {
                    swap(items, j, k);
                }
                k++;
                j--;
            }
        }
    
        div3DeScanSort(items, start, i - 1);
        div3DeScanSort(items, j + 1, end);
    }
}

优化方式3：双轴快速排序

双轴快速排序，顾名思义，取两个中心点 pivot1，pivot2，且 pivot1 ≤ pivot2，可将序列分成三段：x<pivot1、pivot1≤x≤pivot2，x<pivot2，然后分别对三段进行递归。

public void dualPivotQuickSort(int[] items) {
    dualPivotQuickSort(items, 0, items.length - 1);
}

public void dualPivotQuickSort(int items[],int start,int end) {
    if(start < end) {
        if(items[start] > items[end]) {
            swap(items,start,end);
        }
        int pivot1 = items[start], pivot2 = items[end];
        int i = start; //0到i-1是小于pivot1的元素,i是pivot1位置
        int j = end;//j+1到end是大于pivot2的元素,j是pivot2位置
        int k = start + 1;//i+1到k-1是大于等于pivot1小于等于pivot2的元素
        //k到j是待遍历元素
        OUT_LOOP: while(k <= j) {
            if(items[k] < items[i]) {
                swap(items,k,i);
                i++;
                k++;
            } else if(items[k] < items[j]) {
                k++;
            } else {
                while(items[j] > pivots2) {
                    j--;//寻找合适位置交换
                    if(j <= k) {
                        break OUT_LOOP;
                    }
                }

                if(items[j] < pivot1) {
                    //如果 j 位置的元素比枢轴1还小，则还需要交换后再换到枢轴1左边
                    swap(items,k,j);
                    swap(items,k,i);
                    i++;
                } else {
                    swap(items,k,j);
                }
                k++;
            }
        }

        //将两个枢轴插入到指定位置
        swap(items, start, i);
        swap(items, end, j);

        dualPivotQuickSort(items, start, i - 1);
        dualPivotQuickSort(items, i + 1, j - 1);
        dualPivotQuickSort(items, j + 1, end);
    }
}

优化方式4：三数取中

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。

堆排序

堆中某个节点的值总是大于等于其子节点的值（大顶堆），并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

堆结构

public class Heap<T extends Comparable<T>> {
    private T[] heap;
    private int N = 0;
    
    public Heap(int maxN) {
        this.heap = (T[]) new Comparable[maxN+1];//0号位置不用
    }

     public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private boolean less(int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    private void swap(int i, int j) {
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }
}

堆的上浮和下沉

在大顶堆中，当一个节点比父节点大，需要交换这个两个节点。交换后可能还比新的父节点大，因此需要不断进行比较和交换，这种操作称为上浮

provate void swim(int k) {
    while(k > 1 && less(k / 2,k)) {
        swap(k / 2,k);
        k = k / 2;
    }
}

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。

privare void sink(int k) {
    while(2 * k <= N) {
        int j = 2 * k;
        // j<N的条件是因为有可能j=N已经到最后一个元素（对应元素个数为双数）
        if(j < N && less(j,j + 1)) j++;
        if(!less(k,j)) break;
        swap(k,j);
        k = j;
    }
}

插入和删除最大元素

将新元素插入到末尾，然后进行上浮

public void insert(Comparable v) {
    heap[++N]  = v;
    swim(N);
}

从数组顶端删除最大元素，并将数组的最后一个元素放到顶端，然后下沉到合适的位置

public T delMax() {
    T max = heap[1];
    swap(1,N--);
    heap[N + 1] = null;
    sink(1);
    return max;
}

堆排序实现

构建堆

由于单个结点的完全二叉树满足堆的特性，所以叶子结点都是堆。因此可以忽略叶子结点元素，对 n 个结点的完全二叉树建堆的过程是：依次将编号为 n/2,n/2-1,…1 的结点为根的子树筛选为子堆，因为 (n/2,n) 这一部分是后半部分，相当于都是叶子结点。

算法思想

利用大顶堆可以进行升序排序。首先先将带排序序列建成一个大顶堆，使得堆顶节点最大；将堆顶节点与堆尾节点交换位置，堆长度减1（即最大纪录排序到位）；然后调整剩余结点为堆，得到次大值结点；重复这一过程，即可得到一个升序序列。

public class HeapSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length - 1; //0号元素没有位置

        //建堆
        for(int i = N / 2; i >= 1; i--) {
            sink(nums,i,N);
        }

        //对建好的堆进行排序
        while(N > 1) {
            swap(nums,1,N--);
            sink(nums,1,N);
        }

    }

    private void sink(T[] nums,int k,int N) {

        while(2 * k <= N) {
            int j = 2 * k;
            if(j < N && less(nums,j,j+1)) j++;
            if(!less(nums,k,j)) break;

            swap(nums,k,j);
            k = j;
        }
    }

    private boolean less(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) < 0;
    }
}

一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。
对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。
堆排序是一种原地排序，没有利用额外的空间。
现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

TimSort 排序算法

Timsort 是一种混合稳定排序算法，源自归并排序（merge sort）和插入排序（insertion sort）。

思路

现实中的大多数据通常是有部分已经排好序的数据块，Timsort 就利用了这一特点。Timsort 称这些已经排好序的数据块们为 natural runs，我们可以将其视为一个一个的”分区”。在排序时，Timsort 迭代数据元素，将其放到不同的 run 里，同时针对这些 run ，按规则进行合并至只剩一个，则这个仅剩的 run 即为排好序的结果。

也就是说，Timsort 的大致思想是先采用插入排序将非常小的 run 扩充为较大的 run ，然后再采用归并排序来合并多个 run，所以说 Timsort 实际为归并排序。具体来说，我们需要定义一个参数 minrun ，当 run 长度小于 minrun 时，我们认为它是非常小的 run ，否则认为它是较大的 run 。

综上，Timsort 的过程为：

• 找到小的 run 扩充为较大的 run
• 按规则合并 run

扩充

从左到右处理待排序序列，将其划分为若干个 run 。从第 1 个尚未处理的对象开始，找到一个尽可能长的连续严格递减（严格降序）或连续非递减（升序）序列，如果是连续严格递减序列，则可以通过一个简单的”翻转操作”在线性时间内将其变为严格递增序列。

这里注意降序的部分必须是”严格”降序才能进行翻转。因为 TimSort 的一个重要目标是保持稳定性。如果在 >= 的情况下进行翻转这个算法就不再是稳定的。

• 升序: a[i−1]≤a[i]≤a[i+1]a[i−1]≤a[i]≤a[i+1]
• 严格降序: a[i−1]>a[i]>a[i+1]a[i−1]>a[i]>a[i+1]

如果这样得到的序列长度等于 minrun ，则我们将其作为一个完整的 run ，继续生成下一 run ；否则用插入排序将后面的元素添加进来，直至其长度达到 minrun 为止。考虑两个简单的例子：

• 待排序序列的前4个数是 3,6,7,5，minrun = 4，则尽可能长的连续非递减序列为 3,6,7，其长度没有达到4。于是将后面的5插入进来，得到长度为4的 run 3,5,6,7。
• 待排序序列的前4个数是 9,1,2,7，minrun = 4，则尽可能长的连续递减序列为 9,1，其长度没有达到4。于是依次将后面的2和7插入进来，得到长度为4的 run 1,2,7,9。

如下图所示，如果 run 是依次减小的，我们反转 run （ run 为图中加粗部分）

合并

再来考虑如何合并 run 。

在理想情况下应当尽量合并长度相近的 run，这样可以节约计算时间。Timsort 选择了一种折中的方案，它要求最右边的三个 run 的长度尽量满足两个条件。记最右边的三个 run 的长度从左到右分别是 A,B,C，则 Timsort 要求：

• A>B+C
• B>C

这样做的目的是让合并后的 run 长度从右至左以指数量级递增，这样只需从右至左依次进行合并就可以使每次合并的两个 run 的长度大致相同，实现了平衡。在具体实现上，如果 A ≤ B + C，则合并 A,B 或者 B,C，这取决于哪一种合并方式生成的新 run 更短。如果 A>B+C 或者 B≤C，则合并B,C。

可以每生成一个新的 run 都试图进行合并。在算法结束后，有可能会出现有剩余 run 没有合并的情况。这时采用强制合并，直至最终仅剩一个 run ，即排序结果。

来看一个具体的例子，考虑待排序序列

3,6,7,5,3,5,6,2,9,1,2,7,0,9,3,6,0,6,2,6,1,8

及 minrun = 4，则排序步骤如下所示。其中每一行代表 Timsort 的一个步骤。方块上括号表示在最初生成 run 时首先找到的尽可能长的连续严格递减序列或连续非递减序列，下方括号表示扩充后或者合并的 run 。

minrun 选取

再讨论下 minrun 的选取方式。因此如果待排序序列长度为 minrun，则我们总共会生成 n/minrun(向上取整)个初始 run。

如果 n/minrun 刚好是2的整数次幂，则归并过程将会非常“完美”，可以表述为一个满二叉树。
如果 n/minrun 比 2 的某个整数次幂稍大一点点，则到算法的最后阶段会出现一个超长 run 与一个超短 run 的合并，这是一种非常不好的的情况。

因此，通常会选取 minrun ，使得 n/minrun 刚好是2的整数次幂或比某个2的整数次幂稍小一点的数。

具体实现上

run 是已经排好序的一块分区，自然 run 可能会有不同的长度，而 Timesort 根据 run 的长度来选择排序的策略，因此 Timsort 也是一个自适应的排序算法。例如，如果 run 的长度小于某一个值，则会选择插入排序算法来排序。

run 的最小长度（minrun）取决于数组的大小。当数组元素少于64个时，那么 run 的最小长度便是数组的长度，这时 Timsort 用插入排序算法来排序。

数组元素小于 64 个为了提升速率采用，实际采用的是二分插入排序（binary merge sort)。

如果数组大于64个元素，则算法将按照之前的思路开始，首先根据 minrun 查找数组中升序或严格降序的部分，这些部分就是 run 了。

当 Timsort 找到一个 run 时，如果 run 的长度小于 minrun，跟之前一样，选择 run 之后的数字插入排序至 run 中，使得 run 的长度到达 minrun。

然后将这个 run 压入栈中，也将该 run 在数组中的起始位置和 run 的长度放入栈中，之后根据先前压入栈中的 run 决定是否该合并 run。

如前所述， 当 run 的数目等于或略小于 2 的幂时，合并两个数组最为有效。所以 Timsort 选择范围为 [32,64],[32,64] 的 minrun，使得原始数组的长度除以 minrun 时，等于或略小于2的幂。

具体而言，选择数组长度的六个最高标志位，如果其余的标志位被设置，则加1：

• 189：10111101，取前六个最高标志位为101111(47)，同时最后两位为 01，所以 minrun 为47+1，n/minrun = 4 满足要求。
• 976：11 1101 0000，取前六个最高标志位为111101(61)，同时最后几位为 0000，所以 minrun 为61，n/minrun = 16 满足要求。

合并的时候，按照思路中的规则进行合并，满足以下条件时，合并结束：

• X>Y+Z
• Y>Z

例如：如果 X<Y+Z，那么 X+Y 合并为一个新的 run，然后入栈。重复上述步骤，直到同时满足上述 2个条件。

当合并结束后，Timsort 会继续找下一 run，然后找到以后入栈，重复上述步骤，即每次 run 入栈都会检查是否需要合并 2 个 run。

注意到，只在栈的顶部进行这样的合并，这个配合 run 是升序或严格降序的可以保证 Timsort 是稳定的，

Timsort 并没执行原址(in_place)的归并，因为保证原址并稳定的话，需要很大的开销。

实际中 Timsort 合并2个相邻的 run 需要临时存储空闲，临时存储空间的大小是 2 个 run 中较小的 run 的大小。Timsort 算法先将较小的 run 复制到这个临时存储空间，然后用原先存储这 2 个 run 的空间来存储合并后的 run。

合并算法是用简单插入排序，依次从左到右或从右到左比较，然后合并 2 个 run。

为了提高效率，Timsort 用二分插入排序（binary merge sort）。即先用二分查找（binary search）找到插入的位置，然后再插入。

参考资料：

github项目CS-Notes
吴伟民.数据结构[M].北京:高等教育出版社,2017.7
TimSort原理学习
Timsort原理介绍