排序算法总结

image

关注点：

• 时间复杂度：最差、平均、最好
• 额外空间复杂度
• 稳定性：原本有相等键值的纪录维持相对次序
• 依据排序的方法：插入、交换、选择、合并等等。
• 适合并行处理？

插入

• 希尔
• 简单插入

交换

• 快速排序
• 冒泡

选择

• 简单选择
• 堆排序

归并排序

基数排序

内部排序：仅使用内存（RAM）的排序算法。

外部排序：外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

八大排序的空间复杂度

O(1)
冒泡 插入 选择 希尔 堆排序 归并（迭代写法）

O(lgN) ~ O(N)
快速排序[具体要看划分的情况]

O(N) 
归并（递归版本）。

O(M)  M 为桶的数量 非比较  桶排序是一种思想，不是具体的排序方法
基数排序  计数排序

通用的方法论

对于不同的排序算法，脑海中应该要有不同的模型。比如说 插入排序的某一轮

         |
  |      |
|||    | |
|||    |||  左边是已经有序的，右边待排

基于比较 vs 非基于比较

我们最常用的快速排序和堆排序等算法，这些算法需要对序列中的数据进行比较，因为被称为基于比较的排序。

基于比较的排序算法是不能突破 O(NlogN)的。简单证明如下：

N 个数有 N!个可能的排列情况，也就是说基于比较的排序算法的判定树有 N!个叶子结点，比较次数至少为 log(N!)=O(NlogN)(斯特林公式)。

而非基于比较的排序，如计数排序，桶排序，和在此基础上的基数排序，则可以突破 O(NlogN)时间下限。但要注意的是，非基于比较的排序算法的使用都是有条件限制的，例如元素的大小限制，相反，基于比较的排序则没有这种限制(在一定范围内)。但并非因为有条件限制就会使非基于比较的排序算法变得无用，对于特定场合有着特殊的性质数据，非基于比较的排序算法则能够非常巧妙地解决。

顺口溜

移动次数和关键字顺序无关的有：

一堆（堆排序）海龟（归并排序）选（选择排序）基（基数排序）友

归并也是吗？

不稳定排序算法

快速选择堆希尔

基于什么？

插交选归基

1.冒泡

（1）普通冒泡

1. 从前往后排 每一轮最大的会排到最后
2. 从后往前排 每一轮最小的会排到最前

eg
    void BubbleSort1(int a[], int n) {
        int i, j;
        for (i = 0; i < n; i++)//第一层循环 ，从头遍历到尾
            for (j = 1; j < n - i; j++)//第二层循环——真正的比较，每完成一轮比较（外循环）之后，最后那一个数都不用参加下一轮的比较。通过 n - i 来控制 j 的大小。
                if (a[j - 1] > a[j])//大数往后移
                    Swap(a[j - 1], a[j]);
    }

（2）带 flag

因为原本可能已经有序了，但是使用上面的冒泡排序方式，依然需要比较多次（只是没发生交换而已）。所以增加一个标记位,记录本轮 比较之中是否发生交换。如果没有发生交换，那么说明已经是有序的了。

eg
    static void bubbleSort2(int a[]){
        int len = a.length;//记录长度
        boolean flag = true; //记录一轮排序中是否发生了交换
        while(flag){
            flag = false;
            for(int j = 1; j < len; j++){ //每一轮过后 len 都会减 1
                if (a[j] < a[j-1]) {
                    swap(a, j);
                    flag = true;//发生了交换就把 flag 设为 true
                }
            }
            len --; //每一轮都把最后一个位置排好了，所以要减一
        }
    }

（3）带 flag 冒泡进一步优化

用 flag 记录每一轮交换的位置的末位，flag 之后的位置都是已经排好序的了

eg
    static void bubbleSort3(int a[]){
        int flag = a.length;//标记符号，上一轮比较中最后一个交换的位置
        int k;//标记符号，上一轮比较中最后一个交换的位置
        
        while(flag>0){
            k = flag;//上一轮比较的最后一个交换的位置
            flag = 0; //重新赋值为 0，以便末次的退出
            for (int i = 1; i < k; i++) {
                if (a[i] < a[i-1]) {
                    swap(a, i);
                    flag = i; //（更新）记录交换的位置
                }
            }
        }
    }

2. 选择

每一轮都进行遍历比较，每次把第 i 个位置排好。

    private static void selectSort(int[] ary) {
        int len = ary.length;
        for (int i = 0; i < len - 1; i++) {//只需要比较到倒数第二个
            int k = findMinKeyIndex(ary, len, i);//找到本轮中最小数的索引
            if (k != i) {
                swap(ary, i, k);
            }
        }
    }

    private static void swap(int[] ary, int i, int k) {
        int tmp = ary[k];
        ary[k] = ary[i];
        ary[i] = tmp;
    }

    private static int findMinKeyIndex(int[] ary, int len, int i) {
        int k = i;//记录最小数的下标
        //找到本轮中最小数的下标
        for (int j = i + 1; j < len; j++) {
            if (ary[k] > ary[j]) {
                k = j;
            }
        }
        return k;
    }

3.插入

插入有两种处理方式。第一种是先保存待插入的值 t ，（t 只需要交换一次）然后将这个值与前面排好序的值进行比较，移动「排好序」的值，最后才将 t 填到目标位置。第二种是 t 需要不断地进行交换。

一个问题：1月20号时，想要实现一个仅在有需要的情况下才进行交换的插入排序算法，结果一直报错。原因：把要比较的数弄错了，应该是 A[i](由于需要往后移动 A[i] 可能会被覆盖，所以应该先将 A[i] 保存起来) 而不是 A[j];

为什么那么久都没发现呢？还有一个原因就是没有将过程打印出来。在编程平台上面通过 sout 打印出来不成问题

一个一个往后挪，如果出现 t >= a[j]的情况就把
上一个挪完的位置==[j+1]== 赋值为 t

eg
    public static int[] insertSort(int[] a) {
        int j;
        for(int i = 1; i<a.length; i++){
            int t = a[i];
            for(j = i-1; j >= 0; j--){
                if (t < a[j]) {
                    a[j+1] = a[j];
                } else {
                    a[j+1] = t;
                    break;//
                }
            }
        }
        return a;
    }

static void insertSort(int a[]) {
    int n = a.length;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {               //若第 i 个元素大于 i-1 元素，直接插入。小于的话，移动有序表,找到合适位置插入
            int j = i - 1;
            int tmp = a[i];        //复制为哨兵，即存储待排序元素
            while (j >= 0 && tmp < a[j]) {  //查找在有序表的插入位置
                a[j + 1] = a[j];
                j--;         //元素后移
            }
            a[j + 1] = tmp;      //插入到正确位置，注意是 j + 1，因为跳出时 j--
        }
    }

}

private static void insertSort(int[] ary) {
    int len = ary.length;

    for (int i = 1; i < len; i++) {
        int k = i;//记录位置
        //找到合适的插入位置
        /**
         * 思路有误：
         *  这里使用了选择的方法，而不是将有序表后移。会导致乱序，因为将小的数与后面的数交换，而实际上，找到的那个「最小数」应该只是后移一位
         * */
        for (int j = i - 1; j >= 0; j--) {
            if (ary[k] < ary[j]) {
                System.out.println("ary[k]:" + ary[k] + " ary[j]: " + ary[j]);
                k = j;
            }
        }
        int tmp = ary[k];
        ary[k] = ary[i];
        ary[i] = tmp;
        System.out.println("第 " + i + " 趟：" + Arrays.toString(ary));

    }
}

eg 经典写法

    static int[] insertSort2(int[] a) {
        int j;
        for(int i = 1; i<a.length; i++){//i 从 1 开始，因为下面 j=i-1,酱紫可以防止数组越界
            int t = a[i];
            for(j=i-1; j>=0 && t<a[j]; j--){
                a[j+1] = a[j];//将下标为 j 的元素往后移动一个位置
            }
            a[j+1] = t; //因为跳出循环的条件为 t >= a[j], 所以这里是 j + 1 应该排在其后面，
        }
        return a;
    }

二分插入

减少比较次数

4.希尔排序

原理：

将相距某个“增量”的一组元素组成一个子序列。然后将较大值移到前面，较小值 移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强版的插入排序

代码：

eg:
    public static void shellSort3(int[] a, int n) {

        // gap 为步长，每次减为原来的一半。
        for (int gap = n / 2; gap > 0; gap /= 2) {

            // 共 gap 个组，对每一组都执行直接插入排序
            for (int i = 0; i < gap; i++) {

                for (int j = i + gap; j < n; j += gap) {

                    // 如果 a[j] < a[j-gap]，则寻找 a[j]位置，并将后面数据的位置都后移。
                    if (a[j] < a[j - gap]) {

                        int tmp = a[j];// 保存小的那个数
                        int k = j - gap;
                        while (k >= 0 && a[k] > tmp) {// 找到一个数大于 tmp
                            a[k + gap] = a[k];// 往后移动
                            k -= gap;
                        }
                        a[k + gap] = tmp;// 找到 tmp 在组中的位置插入
                    }
                }
            }
        }
    }

5.快速排序

import java.util.*;

public class QuickSort {
    public int[] quickSort(int[] A, int n) {
        // write code here
        if(A == null||n<=0){
            return null;
        }
  
        qsort(A,0,n-1);
        return A;
    }
    
    void qsort(int[] A,int start,int end){
        if(start>=end){
            return ;
        }
        int j = partition(A,start,end);
        qsort(A,start,j-1);
        qsort(A,j+1,end);
    }
    
    int partition(int[] A,int start,int end){
        int pivot = A[start];
        int i = start;
        int j = end+1;
        
        while(true){
            while(A[++i]< pivot){
                if(i==end) break;//如果在数组的打乱之后，把最大元素放到最右边，这个检查也可以省略。
            }
            while(A[--j]>pivot){ 
                if(j==start) break;//启发式·其实这个判断可以省略，因为 pivot = A[start]，而判断条件是 A[--j] > pivot 等价于 A[--j] > A[start] ，当 --j == start 的时候，二者相等，循环自动退出
            }
            if(i >= j){
                break;
            }
            int tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
        }
        int tmp = A[start];
        A[start] = A[j];
        A[j]=tmp;
        return j;
    }
}

0128 花费了60min，因为自己前面一直 return i;
吐血

辅助空间：使用递归实现时需要 logN 的栈空间，迭代实现则不同。

为什么堆排比快排慢

这里的关键问题就在于第 2 步，堆底的元素肯定很小，将它拿到堆顶和原本属于最大元素的两个子节点比较，它比它们大的可能性是微乎其微的。实际上它肯定小于其中的一个儿子。而大于另一个儿子的可能性非常小。于是，这一次比较的结果就是概率不均等的，根据前面的分析，概率不均等的比较是不明智的，因为它并不能保证在糟糕情况下也能将问题的可能性削减到原本的 1/2。可以想像一种极端情况，如果 a 肯定小于 b，那么比较 a 和 b 就会什么信息也得不到——原本剩下多少可能性还是剩下多少可能性。

在堆排里面有大量这种近乎无效的比较，因为被拿到堆顶的那个元素几乎肯定是很小的，而靠近堆顶的元素又几乎肯定是很大的，将一个很小的数和一个很大的数比较，结果几乎肯定是“小于”的，这就意味着问题的可能性只被排除掉了很小一部分。

这就是为什么堆排比较慢（堆排虽然和快排一样复杂度都是 O(NlogN)但堆排复杂度的常系数更大）。

MacKay 也提供了一个修改版的堆排：每次不是将堆底的元素拿到上面去，而是直接比较堆顶（最大）元素的两个儿子，即选出次大的元素。由于这两个儿子之间的大小关系是很不确定的，两者都很大，说不好哪个更大哪个更小，所以这次比较的两个结果就是概率均等的了。具体参考这里。

分治思想。

三个子序列 L U G

找到轴点 pivot（一般都选数组的首元素），

• 小于 pivot 分到 L
• 大于 pivot 分到 U
• G 为未排序序列

low high 终止判断节点 low=high

最优 nlogn

尽量避免（无法杜绝）最坏情况发生：

• 随机选取
• 三者取中法

不同的实现版本

迭代方式

右先还是左先？

/> 还是 >= ?

有一些是先保存 pivot，前面交换左右侧元素，最后才把 pivot 与目标位置交换

有的实现是：先把 pivot 跟数组中的元素进行交换。也就是说 pivot 会发生多次交换

快排优化：

1. 对小数组使用插入排序。Java 标准库自带的排序DualPivotQuicksort就是这么干的。小数组具体为多少呢？INSERTION_SORT_THRESHOLD = 47。
2. 使用双枢轴，也就是将数组三切分(大于枢轴，等于枢轴，小于枢轴），可以证明这样是熵最优的并且更高效。为什么这样划分呢？因为统计表明对大规模数组进行排序时，数据重复的情况比较多，因此使用双枢轴可以有效避免相等元素之间的比较。以 Java 标准库为例，JDK 1.8 中的DualPivotQuicksort实现了一种 快速三向切分 的快速排序，它通过将相等元素聚集起来的方式使熵最优（原理：将相等元素聚集起来，不必再切分这些元素）。
3. 还有一个优化的杀手锏就是 改进划分的策略，DualPivotQuicksort使用了一种称为 五取样划分 的策略对数组进行划分，类似于BFPRT 算法。

总结一下，快排的改进主要有三种方法：小数组使用插入排序、双枢轴（快速三向切分）、划分策略优化（五取样划分）。经过优化后的快速排序算法时间复杂度可以介于 O(N) 到 O(NlogN) 之间。

快排为什么快？

这种策略的本质可以概括成“让未知世界无机可乘”。它是没有“弱点的”，答案的任何一个分支都是等概率的。反之，一旦某个分支蕴含的可能性更多，当情况落到那个分支上的时候你就郁闷了。比如猜数字游戏最糟糕的策略就是一个一个的猜：是 1 吗？是 2 吗？… 因为这种猜法最差的情况下需要 64 次才能猜对，下界非常糟糕。二分搜索为什么好，就是因为它每次都将可能性排除一半并且无论如何都能排除一半（它是最糟情况下表现最好的）。

双基准快速排序：

一趟能确定两个数。

1. 对于长度小于17的数组使用插入排序(常见优化步骤，传统快排也有应用)。
2. 选择两个枢纽元p1,p2，一般选择起始元素a[left]和末尾元素a[right]（有其他选取方式）。
3. 假设p1<p2，如果不是就交换。
4. 基于这p1,p2将整个数组分成三部分，<p1的,p1<&<p2的,>p2的。
5. 递归排序这三个部分。

单基准三向切分

原理：将相等元素聚集起来，不必再切分这些元素）。

每一趟可以确定 数组中与 pivot 个数相等的n 个元素。

也有两个版本

这里写图片描述

快速三向切分

数组三切分(大于枢轴，等于枢轴，小于枢轴）

快速切分的扩展应用

在数组中查找第k个小或大的元素。我们可以回想前面《快速排序及改进》中的partition(Comparable[] a,int lo,int hi)方法，它会将数组的a[lo]到a[hi]重新排列(局部排序)并返回一个整数j，使得：

a[lo ... j - 1] <= a[j] <= a[j + 1 ... hi]

那么，要获取第K小的值，当k = j时，a[j]就是要求解的数值了。

6.归并排序 （分治 思想）

具体的实现，前面是 分支递归，后面是排序。也就是说，它先把子数组内部排序完了，然后再合并

概念： 先分 后 合并（参考白话经典算法）
基本思路： 将数组分成二组 A,B，如果这两组组内的数据都是有序的，那么就可以 i 方便地对这两组进行排序。如何令这两组组内数据有序？

将 A,B 再各自分成两组。以此类推，当分出来的小组只有一个数据时，即可认为这两组数据已经有序。然后再合并相邻的两个小组即可。

这样通过先递==归==分解数列，再合==并==数列就完成了==归并==排序。

首先看看如何将两个有序的数列合并

无论是自顶向下还是自底向上，都是分治思想。

• 自顶向下，通过递归的方式，先分配，根据子结果得到父结果。
• 自底向上，以迭代的方式控制归并数组的 lo mid hi

//将有序数组 a[]和 b[]合并到 c[]中  
void MemeryArray(int a[], int n, int b[], int m, int c[])  
{  
    int i, j, k;  
  
    i = j = k = 0;  
    while (i < n && j < m)  
    {  
        if (a[i] < b[j])  
            c[k++] = a[i++];  
        else  
            c[k++] = b[j++];   
    }  
  //上面循环退出，要么是 i>=n,要么是 j<=n
    while (i < n)  
        c[k++] = a[i++];  
  
    while (j < m)  
        c[k++] = b[j++];  
}  

//将有二个有序数列 a[first...mid]和 a[mid...last]合并。  
void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
      
    while (i <= m)  
        temp[k++] = a[i++];  
      
    while (j <= n)  
        temp[k++] = a[j++];  
      
    for (i = 0; i < k; i++)  
        a[first + i] = temp[i];  
}  
void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);    //左边有序  
        mergesort(a, mid + 1, last, temp); //右边有序  
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
    }  
}  
  
bool MergeSort(int a[], int n)  
{  
    int *p = new int[n];  
    if (p == NULL)  
        return false;  
    mergesort(a, 0, n - 1, p);  
    delete[] p;  
    return true;  
}  

递归实现要注意的问题

每一次归并结果都要复制回待排序数组，因为后续的归并过程中，默认 待排序数组是有序的了。

若果要 装x（ 把 /2 改为 >>1 ）的话，一定要注意顺序。

归并的趟数

logn

思路就是:构造归并树，对n个数构造它的归并树，而归并树的高度再减去1就是归并排序的趟数，也就等于log (n)，举个简单而直观的例子，设对1~8这8个数进行归并排序，从上到下构造它的归并树如下
1   2   3   4   5   6   7   8
  \ /   \ /      \ /      \ /
 1  2    3  4    5  6    7  8
 \    /              \   /
   1  2  3  4     5  6  7  8
          \        /
    1  2  3  4  5  6  7  8
每上下相邻的两层之间，从上层到下层的过程就是一趟归并，这棵二叉树的总高度等于4，因此归并趟数为3，正好等于log(8)。

优化

1. 小数组（长度小于 15）使用插入排序
2. 如果A[mid] < A[mid + 1] ,则不需要进行归并

归并路数

7.堆排序

时间复杂度

初始建堆的时间复杂度？

n

重复建堆的时间复杂度

logn

空间复杂度

额外辅助空间：

原地堆排序 0；

堆是一棵完全二叉树？不能是左子树中孩子数目少于右子树吗？也就是左边没满但是填到右边去了

---

1. 建立大顶堆
2. 堆顶元素与堆尾元素进行交换
3. 堆的尺寸缩小1，调用 shift down 堆序性。
4. 重复步骤 2，直到堆的大小为 1.

树和二叉树的三个主要差别：

• 树的结点个数至少为 1，而二叉树的结点个数可以为 0
• 树中结点的最大度数没有限制，而二叉树结点的最大度数为 2
• 树的结点无左、右之分，而二叉树的结点有左、右之分

二叉树又分为完全二叉树（complete binary tree）和满二叉树（full binary tree）

堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

二叉堆一般分为两种：最大堆和最小堆。

进行堆调整的前提首先要左右子节点都满足堆序性。大前提满足了，后续的条件才有可能满足。

需要注意的一个问题是：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变

• Parent(i) = floor((i-1)/2)，i 的父节点下标
• Left(i) = 2i + 1，i 的左子节点下标
• Right(i) = 2(i + 1)，i 的右子节点下标

创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。

8.桶排序（一种思想）

计数排序似乎饶了点弯子，比如当我们刚刚统计出 C，C[i]可以表示 A 中值为 i 的元素的个数，此时我们直接顺序地扫描 C，就可以求出排序后的结果。的确是这样，不过这种方法不再是计数排序，而是桶排序(Bucket Sort)，确切地说，是桶排序的一种特殊情况。用这种方法，可以很容易写出程序，比计数排序还简单，只是不能求出稳定的 Order。

桶中元素的顺序放入和顺序取出是有必要的，因为这样可以确定桶排序是一种稳定排序算法，配合基数排序是很好用的。

算法步骤

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

8.1.基数排序

适合并行处理？

假设我们有一些二元组(a,b)，要对它们进行以 a 为首要关键字，b 的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD 方法往往比 MSD 简单而开销小。

把数字按照数位分开来进行比较。实际上比较是无法避免的，但是为什么称之为「非比较型的排序」呢？

基数排序的时间复杂度是[图片上传失败...(image-d9f0ea-1522464999983)]，其中[图片上传失败...(image-8a0dd2-1522464999983)]是排序元素个数，[图片上传失败...(image-2cfd2d-1522464999984)]是数字位数。注意这不是说这个时间复杂度一定优于[图片上传失败...(image-cbca7c-1522464999984)]，{\displaystyle k}[图片上传失败...(image-810cd6-1522464999984)]的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小；{\displaystyle k}[图片上传失败...(image-2e4ddd-1522464999984)]决定了进行多少轮处理，而{\displaystyle n}[图片上传失败...(image-98b73d-1522464999984)]是每轮处理的操作数目。

8.2计数排序

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。

算法步骤

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去 1

9.拓扑排序

基本概念

定义：设 G(V,E)是一个具有 n 个顶点的有向图，V 中的顶点序列 v1,v2,······,vn,
满足若从顶点vi 到 vj 有一条路径，则在顶点序列中顶点 vi 必在顶点 vj 之前， 则称这样一个顶点序列为一个拓扑序列。

• “类比”，其实就是对一个有向图构造拓扑排序的过程。

代码

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

Ref

一个 DAG 图，如何写出它的拓扑排序呢？

这里说一种比较常用的方法：

1. 从 DAG 图中选择一个 没有前驱（即入度为 0）的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

通常，一个有向无环图可以有一个或多个拓扑排序序列。

二、拓扑排序的应用

拓扑排序通常用来“排序”具有依赖关系的任务。

比如，如果用一个 DAG 图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边 表示在做任务 B 之前必须先完成任务 A。故在这个工程中，任意两个任务要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。

小结

线性排序算法使用最重要的是，充分利用数据特殊的性质，以达到最佳效果。

三种线性排序算法 计数排序、桶排序与基数排序