@DATASOURCE
2015-10-29T09:27:45.000000Z
字数 18032
阅读 1687
排序算法
排序
快速排序法
概述
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列.
基本操作
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。步骤为：
> 1.从数列中挑出一个元素，称为 "基准"（pivot），
> 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
> 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
排序演示
假设用户输入了如下数组：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 数据 | 6 | 2 | 7 | 3 | 8 | 9 |
创建变量`i=0`（指向第一个数据）, `j=5`(指向最后一个数据), `k=6`(赋值为第一个数据的值)。 我们取走了下标0的数据，于是，我们需要找到一个数字来替换他。由于我们要把所有比6小的数移动到左面，所以我们可以开始寻找比6小的数并从右往左找。别急，我们要按顺序找哦。不断递减j的值，我们发现下标3的数据比6小，于是把3移到下标0（实际是i指向的位置。代码中要用i，因为后面还会循环这个步骤，不用i的话第二次循环就会出问题。），数组和变量变成了以下状态：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 数据 | 3 | 2 | 7 | 6 | 8 | 9 |
i=0 j=3 k=6
由于变量k已经储存了下标0的数据，所以我们可以放心的把下标0覆盖了。如此一来，下标3虽然有数据，但是相当于没有了，因为数据已经复制到别的地方了。于是我们再找一个数据来替换他。这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2是第一个比k大的，于是用下标2的数据7替换j指向的下标3的数据，数据状态变成下表：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 数据 | 3 | 2 | 6 | 7 | 8 | 9 |
i=2 j=3 k=6
重复上面的步骤，递减变量`j`。这时，我们发现`i`和`j`“碰头”了：他们都指向了下标`2`。于是，循环结束，把`k`填回下标`2`里，即得到结果。 如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。
- 注意：快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。（你可以想象一下i和j是两个机器人，数据就是大小不一的石头，先取走i前面的石头留出回旋的空间，然后他们轮流分别挑选比k大和比k小的石头扔给对面，最后在他们中间把取走的那块石头放回去，于是比这块石头大的全扔给了j那一边，小的全扔给了i那一边。只是这次运气好，扔完一次刚好排整齐。）为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
//代码示例:#include<time.h>#include<stdlib.h>using namespace std;void swap(int *a, int *b){ // 简单的交换函数;int t;t = *a;*a = *b;*b = t;}void quicksort(int *a, int l, int r){ // 快排函数;int t, i, j;if(l < r){ // 递归结束条件;srand(time(NULL)); // 找一个随机数来作为每一个分区的基准数;t = l + rand()%(r - l + 1);swap(&a[t], &a[l]); // 将这个基准数放在数组的末尾;int base = a[l]; // 用base 来存储这个基准数;i = l, j = r;while (i < j){while(i < j && a[j]>= base) // 从右向左找第一个小于x的数j--;if(i < j)a[i++] = a[j];while(i < j && a[i]< base) // 从左向右找第一个大于等于x的数i++;if(i < j)a[j--] = a[i];}a[i] = base;quicksort(a, l, i - 1);quicksort(a, i + 1, r);}}
复杂度分析
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。” 随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。
其他
C语言中可直接调用 `qsort` 快排函数,包含在 `#include<algorithm>` 头文件中, 它有四个参数，第一个为要排序的数组的 首地址，第二个参数为要排序的元素的个数，第三个参数为每个元素所占的空间大小，第四 个参数是需要自己写的比较函数,即告诉它应该按什么来排序.一种典型的写法如下: `qsort(s,n,sizeof(s[0]),cmp);`下面具体介绍它的各种用法,主要是 `cmp` 函数的写法,`cmp` 函数有两个参数,均为 `const void*` 类型，有一个返回值，为 `int` 类型.
- 对一维整型数组排序:
intcmp(const void* a, const void*b) {return *(int*)a - *(int*)b;}
如果整型数组为`a[]`,其中元素个数为n,则`qsort(a,n,sizeof(a[0]),cmp);`即完成了对`a[]`数组的 升序排序. 如果要按降序排列，可将`return *(int*)a - *(int*)b;`改为 `return *(int*)b - *(int*)a;`
- 对 char 类型数组排序：
int cmp(const void* a, const void* b) {return *(char*)a - *(char*)b;}charword[100];qsort(word,100,sizeof(word[0]),cmp);//即完成了对word 中的字符按升序排列.
- 对
double类型数组排序：
double in[100];int cmp(const void*a, const void*b) {return *(double*)a > *(double*)b ? 1 : -1;}qsort(in,100,sizeof(in[0]),cmp)；
值得注意的是，`cmp` 里不能像对 `int` 排序那样写 `return *(double*)a - *(double*)b`,因为返回值 是整型，这样返回值是 `double` 会出错且不易察觉.
- 对字符串排序：
chars[100][100];int cmp(const void* x, const void* y) {return strcmp((char*)x, (char*)y);}qsort(s, 100, sizeof(s[0]), cmp);
- 对结构体一级排序：
struct node {int a, b;}s[100];int cmp(const void*x, const void*y) {node xx = *(node*)x;node yy= *(node*)y;return xx.a - yy.a;}qsort(s, 100, sizeof(s[0]), cmp);//按 a 的升序对结构体 s 进行排序
- 对结构体二级排序:
struct node {int a; int b;}s[100];int cmp(const void* x, const void* y) {node xx = *(node*)x;node yy = *(node*)y;if(xx.a != yy.a) return xx.a - yy.a;else return xx.b - yy.b;}qsort(s,100,sizeof(s[0]),cmp);//先按 a 进行升序排序，如果a 相同,按 b 的升序排列.
- 计算几何中求凸包的 cmp
int cmp(const void *a, const void *b) // 重点 cmp 函数，把除了 1 点外的所有点，旋转角度排序{struct point *c = (point *)a;struct point *d = (point *)b;if(calc(*c,*d,p[1]) < 0) return 1;else if(!calc(*c, *d, p[1]) && dis(c -> x, c -> y, p[1].x, p[1].y) < dis(d -> x, d -> y, p[1].x, p[1].y)) // 如果在一条直线上，则把远的放在前面return 1;else return -1;}
Sort cmp 函数的写法
默认排序顺序为从小到大 sort(arr, arr + n);
如果是没有定义小于运算的数据类型，或者想改变排序的顺序，就要用到第三参数——比较函数。比较函数是一个自己定义的函数，返回值是 bool 型，它规定了什么样的关系才是“小于”。想把刚才的整数数组按降序排列，可以先定义一个比较函数 cmp
bool cmp(int a, int b){return a > b;}
排序的时候就写 sort(a,a+100,cmp);
假设自己定义了一个结构体 node
struct node{int a;int b;double c;}
有一个 node 类型的数组 node arr[100] ，想对它进行排序：先按 a 值升序排列，如果 a 值相同，再按 b 值降序排列，如果 b 还相同，就按 c 降序排列。就可以写这样一个比较函数：
以下是代码片段：
bool cmp(node x, node y){if(x.a != y.a) return x.aif(x.b != y.b) return x.b > y.b;return return x.c > y.c;}
排序时写 sort(arr,a+100,cmp);
归并排序
概述
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
基本操作
具体排序过程分成三个过程：
- （1）分解：将当前区间一分为二，即求分裂点 mid = (low + high)/2;
- （2）求解：递归地对两个子区间 array[low..mid] 和 array[mid + 1..high] 进行归并排序；递归的终结条件：子区间长度为 1（一个记录自然有序）。
- （3）合并：将已排序的两个子区间R[low..mid]和R[mid + 1..high]归并为一个有序的区间 array[low..high]。
合并操作的过程如下：
- 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 4.重复步骤3直到某一指针到达序列尾
- 5.将另一序列剩下的所有元素直接复制到合并序列尾
代码示例
#include<iostream>using namespace std;int c[1010];void mergesort(int *a, int l, int r){int mid, i, j, k;if(r - l > 1){ // 递归结束条件;mid = (l + r) / 2;mergesort(a, l, mid); // 分治思想的应用;mergesort(a, mid, r);i = l;j = mid;k = l;while(i < mid && j < r){ // 将每一个小区间[l, r) 中的元素排列到临时数组 c 中去;if(a[i] <= a[j])c[k++] = a[i++];elsec[k++] = a[j++];}for(; i < mid; i++) // 将剩余的元素放在后面;c[k++] = a[i];for(; j < r; j++)c[k++] = a[j];for(i = l; i < r; i++)a[i] = c[i];}return;}int main(){int a[20] = {0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};for(int i = 0; i < 20; i++)cout << a[i] <<" ";cout << endl;mergesort(a, 0, 20);for(int i = 0; i < 20; i++)cout << a[i] <<" ";cout << endl;return 0 ;}
复杂度分析
时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。空间复杂度为 O(n)比较操作的次数介于(nlogn) / 2和nlogn - n + 1。赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)归并排序比较占用内存，但却是一种效率高且稳定的算法。
其他作用(求逆序数)
修改合并排序在合并两个子序列时，出现右边元素小于左边元素的情况，亦即a[j]
//代码:while(i < mid && j < r){ // 将每一个小区间[l, r) 中的元素排列到临时数组 c 中去;if(a[i] <= a[j])c[k++] = a[i++];else{c[k++] = a[j++];ans += mid – i; // 在此处求逆序数;}
堆排序(详见数据结构, 堆)
简述
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
基本操作
（1）用大根堆排序的基本思想
- 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
- 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
- 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
（2）大根堆排序算法的基本操作：
- 初始化操作：将R[1..n]构造为初始堆；
- 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。
注意
- 只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
- 用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
代码示例
#include <iostream>#include <cstdio>using namespace std;int heap[20]; // 用数组模拟堆;int n; // 堆中元素的数量;void Minheapsortdown(int i, int m){ // 向下调整下标为i的元素直到合适的位置;int j, temp;temp = heap[i]; // 依然临时变量temp来记录该元素的值;j = 2 * i + 1; // 令j等于其中一个儿子的值;while(j < m){if(j + 1 < m && heap[j + 1] < heap[j]) // 选择一个父节点下面较小的儿子来交换;j++;if(heap[j] >= temp) // 当所有的儿子都大于该元素的时候, 停止;break;heap[i] = heap[j]; // 否则, 将比较小的儿子放到父节点的位置;i = j; // 更新i和 j的值;j = 2 * i + 1;}heap[i] = temp; // 将temp放到合适的位置;}void makeMinheap(){ // 对一个数组进行堆化操作;int i;for(i = n / 2 - 1; i >= 0; i--) // 注意此处从n / 2 – 1 开始排列;Minheapsortdown(I, n);}void Minheapsort(){ // 堆排序;for(int i = n - 1; i >= 1; i--){swap(&heap[0], &heap[i]); // 每次排序可以确定一个最小值(堆顶元素), 将其放在数组的末尾;Minheapsortdown(0, i); // 每次排好 顶元素;}}int main(){int i;for(i = 0; i < 10; i++)heap[i] = -i;n = 10;for(i = 0; i < 10; i++)cout << heap[i] <<" ";cout << endl;makeMinheap();for(i = 0; i < 10; i++)cout << heap[i] <<" ";cout << endl;Minheapsort();for(i = 0; i < 10; i++)cout << heap[i] <<" ";cout << endl;return 0;}
复杂度分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。平均性能O(N*logN)。
其他性能
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1）.它是不稳定的排序方法。
STL 中的堆排序
#include<iostream>#include<algorithm>#include<cstdio>#include<vector>using namespace std;bool cmp(int a, int b){ // 实现最小堆的比较函数;return a > b;}void print(int elem){cout << elem << ' ';}int main(){int n;vector <int> hea; // 定义堆;while(cin >> n && n)hea.push_back(n); // 向堆中添加数据, 并放在尾部;printf("%s\n", "After make_heap: ");make_heap(hea.begin(), hea.end(), cmp);for_each(hea.begin(), hea.end(), print);printf("\n");printf("%s\n", "After sort_heap: ");sort_heap(hea.begin(), hea.end(), cmp); // 堆排序函数, 从小到大排序;for_each(hea.begin(), hea.end(), print);printf("\n");return 0;}
以上四种排序算法的总结
时空复杂度和稳定性
程序效率验证
#include <cstdio>#include <algorithm>#include <ctime>using namespace std;//------------------------快速排序(普通)--------------------------void quick_sort(int s[], int l, int r){if (l < r){int i = l, j = r, x = s[l];while (i < j){while(i < j && s[j] >= x) // 从右向左找第一个小于x的数j--;if(i < j)s[i++] = s[j];while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数i++;if(i < j)s[j--] = s[i];}s[i] = x;quick_sort(s, l, i - 1); // 递归调用quick_sort(s, i + 1, r);}}//-----------------------快速排序(随机)--------------------------void swap(int *a, int *b){ // 简单的交换函数;int t;t = *a;*a = *b;*b = t;}void quick_sort1(int *a, int l, int r){ // 快排函数;int t, i, j;if(l < r){ // 递归结束条件;srand(time(NULL)); // 找一个随机数来作为每一个分区的基准数;t = l + rand()%(r - l + 1);swap(&a[t], &a[l]); // 将这个基准数放在数组的末尾;int base = a[l]; // 用base 来存储这个基准数;i = l, j = r;while (i < j){while(i < j && a[j]>= base) // 从右向左找第一个小于x的数j--;if(i < j)a[i++] = a[j];while(i < j && a[i]< base) // 从左向右找第一个大于等于x的数i++;if(i < j)a[j--] = a[i];}a[i] = base;quick_sort(a, l, i - 1);quick_sort(a, i + 1, r);}}//------------------------归并排序----------------------------//将有二个有序数列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++];elsetemp[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);return true;}//------------------------堆排序---------------------------inline void Swap(int &a, int &b){int c = a;a = b;b = c;}//建立最小堆// 从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2void MinHeapFixdown(int a[], int i, int n){int j, temp;temp = a[i];j = 2 * i + 1;while (j < n){if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的j++;if (a[j] >= temp)break;a[i] = a[j]; //把较小的子结点往上移动,替换它的父结点i = j;j = 2 * i + 1;}a[i] = temp;}//建立最小堆void MakeMinHeap(int a[], int n){for (int i = n / 2 - 1; i >= 0; i--)MinHeapFixdown(a, i, n);}void MinheapsortTodescendarray(int a[], int n){for (int i = n - 1; i >= 1; i--){Swap(a[i], a[0]);MinHeapFixdown(a, 0, i);}}const int MAXN = 5000000;int a[MAXN];int b[MAXN], c[MAXN], d[MAXN], e[MAXN];int main(){int i;srand(time(NULL));for (i = 0; i < MAXN; ++i)a[i] = rand() * rand(); //注rand()产生的数在0到0x7FFF之间for (i = 0; i < MAXN; ++i)e[i] = d[i] = c[i] = b[i] = a[i];clock_t ibegin, iend;printf("n == %d\n", MAXN);//快速排序printf("quick_sort: ");ibegin = clock();quick_sort(a, 0, MAXN - 1);iend = clock();printf("%d MS\n", iend - ibegin);printf("quick_sort1: ");ibegin = clock();quick_sort(e, 0, MAXN - 1);iend = clock();printf("%d MS\n", iend - ibegin);//归并排序printf("MergeSort: ");ibegin = clock();MergeSort(b, MAXN);iend = clock();printf("%d MS\n", iend - ibegin);//堆排序printf("Heap_Sort: ");ibegin = clock();MakeMinHeap(c, MAXN);MinheapsortTodescendarray(c, MAXN);iend = clock();printf("%d MS\n", iend - ibegin);//STL中的堆排序printf("STL_Heap_sort: ");ibegin = clock();make_heap(d, d + MAXN);sort_heap(d, d + MAXN);iend = clock();printf("%d MS\n", iend - ibegin);return 0;}
- 程序运行结果
拓扑排序
概述
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。对一个AOV网G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
基本操作
由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
下面以有图(a)为例，来说明拓扑排序算法的执行过程。
(1) 在(a)图中v0和v1的入度都为0，不妨选择v0并输出之，接着删去顶点v0及出边<0,2>，得到的结果如(b)图所示。
(2) 在(b)图中只有一个入度为0的顶点v1，输出v1，接着删去v1和它的三条出边<1,2>,<1,3>和<1,4>，得到的结果如(c)图所示。
(3) 在(c)图中v2和v4的入度都为0，不妨选择v2并输出之，接着删去v2及两条出边<2,3>和<2,5>，得到的结果如(d)图所示。
(4) 在(d)图上依次输出顶点v3,v4和v5，并在每个顶点输出后删除该顶点及出边，操作都很简单，不再赘述。为了利用C++语言在计算机上实现拓扑排序算法，AOV网采用邻接表表示较方便。如对于上图(a)，对应的邻接表如下图2.
在拓扑排序算法中，需要设置一个包含n个元素的一维整型数组，假定用d表示，用它来保存AOV网中每个顶点的入度值。如对于图3-8(a)，得到数组d的初始值为
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 值 | 0 | 0 | 2 | 2 | 1 | 3 |
在进行拓扑排序中，为了把所有入度为0的顶点都保存起来，而且又便于插入、删除以及节省存储，最好的方法是把它们链接成一个栈. 这里有两种方法，一种是再重新建一个栈用来存储入度为0 的点，另一种是直接用 d 数组来模拟栈操作，下面只介绍第二种。
例如，利用图2所示的邻接表，建立的入度为0的初始栈的过程为：
(1) 开始置链栈为空，即给链栈指针top赋初值为-1： top=-1;
(2) 将入度为0的元素d[0]进栈，即： d[0]=top; top=0;
此时top指向d[0]元素，表示顶点v0的入度为0，而d[0]的值为-1，表明为栈底。
(3) 将入度为0的元素d[1]进栈，即: d[1]=top; top=1;
此时top指向d[1]元素，表示顶点v1的入度为0，而d[1]的值为0，表明下一个入度为0的元素为d[0]，即对应下一个入度为0的顶点为v0，d[0]的值为-1，所以此栈当前有两个元素d[1]和d[0]。
(4) 因d[2]至d[5]的值均不为0，即对应的v2到v5的入度均不为0，所以它们均不进栈，至此，初始栈建立完毕，得到的数组d为:
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 值 | -1 | 0 | 2 | 2 | 1 | 3 |
将入度为0的顶点利用上述链栈链接起来后，拓扑算法中循环执行的第(1)步“选择一个入度为0的顶点并输出之”，可通过输出栈顶指针top所代表的顶点序号来实现；第(2)步“从AOV网中删除刚输出的顶点（假定为vj，其中j等于top的值）及所有出边”，可通过首先作退栈处理，使top指向下一个入度为0的元素，然后遍历vj的邻接点表，分别把所有邻接点的入度减1，若减1后的入度为0则令该元素进栈来实现。此外，该循环的终止条件“直到不存在入度为0的顶点为止”，可通过判断栈空来实现。
对于上表，当删除由top值所代表的顶点v1及所有出边后，数组d变为：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 值 | -1 | 1 | 1 | 0 | 3 |
当依次删除top所表示的每个顶点及所有出边后，数组d的变化分别如下图所示：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 值 | -1 | 1 | 1 | 2 |
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 值 | -1 | 1 | 2 |
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 值 | -1 | 1 |
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 值 | -1 |
当删除顶点v5及所有出边后，top的值为1，表示栈空，至此算法执行结束，得到的拓扑序列为：1,4,0,2,3,5.
代码示例
#include <vector>#include <cstdio>#include <iostream>#include <algorithm>#define M 110using namespace std;vector <int> vec[M]; // 邻接表;int ingree[M]; // 存储节点的入度;int ans[M]; // 存储排序后的数字;int n, m; // 点数;bool TOSort(){ // 排序成功返回 true 否则返回 false;int i, j;int top = -1; // 栈顶;int count = 0; // 排序数组的指针;fill(ingree, ingree + M, 0);for(i = 1; i <= n; i++){ // 初始化入度数组, 统计所有点的入度;int end = vec[i].size();for(j = 0; j < end; j++)ingree[vec[i][j]]++;}for(i = 1; i <= n; i++) // 初始化栈;if(ingree[i] == 0){ingree[i] = top;top = i;}while(top != -1){ // -1 为栈底;int t = top;top = ingree[t];ans[count++] = t;int end = vec[t].size();for(i = 0; i < end; i++){ // 删除入度为零的点的边;ingree[vec[t][i]]--;if(ingree[vec[t][i]] == 0){ingree[vec[t][i]] = top;top = vec[t][i];}}}if(count < n)return false;return true;}int main(){int i, a, b;scanf("%d%d", &n, &m); // 输入点的个数, 和边的个数;for(i = 0; i < m; i++){scanf("%d%d", &a, &b); // a -> b 边;vec[a].push_back(b);}if(TOSort())for(i = 0; i < n; i++)printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');elseprintf("有环\n");return 0;}
复杂度分析
拓扑排序实际上是对邻接表表示的图G进行遍历的过程，每次访问一个入度为0的顶点。若图G中没有回路，则需要扫描邻接表中的所有边结点，再加上在算法开始时，为建立入度数组d需要访问表头向量中的每个域和其单链表中的每个结点，所以此算法的时间复杂性为O(n+e)。
POJ 例题
例1: 1094
题目描述: 输入的第一行有两个数字, n 和 m, n 指有n 个字母(从A开始的n 个), m 表示有m条信息, 接下来的m行信息的格式为: 字母1<字母2(例如A<B), m条信息后, 会有三种可能, 在第i个信息就能判断出n个字母的排序输出” Sorted sequence determined after i relations: ABCD…..”, 中间出现矛盾(A<B, B<A), 输出” Inconsistency found after i relations.”, 或者最终也没有一个唯一的排序输出” Sorted sequence cannot be determined.”
#include <queue>#include <stack>#include <vector>#include <cstdio>#include <iostream>#include <algorithm>#define M 30using namespace std;vector <int> vec[M];int degree[M];int ans[M];bool is[M];int n, m, nn;int tosort(){int i, j;int f = 0; // 记录是否出现不确定的情况;int ff = 0; // 记录是否出现了环;int count = 0;fill(degree, degree + M, 0);stack <int> sta;for(i = 1; i <= n; i++){int end = vec[i].size();for(j = 0; j < end; j++)degree[vec[i][j]]++;//cerr << 1 << endl;}for(i = 1; i <= n; i++){if(degree[i] == 0 && is[i])sta.push(i);//cerr << 2 << endl;}if(sta.size() > 1)f = 1;while(!sta.empty()){int t = sta.top();sta.pop();ans[count++] = t;int end = vec[t].size();for(i = 0; i < end; i++){int k = vec[t][i];degree[k]--;if(degree[k] == 0)sta.push(k);//cerr << 3 << endl;}if(sta.size() > 1)f = 1;}if(count < nn)return 1; // 出现环;else if(f)return 2; // 出现了不确定答案;elsereturn 3; // nn 个元素正常拓扑排序;}int main(){int i, j;while(scanf("%d%d", &n, &m) != EOF){if(n == 0 && m == 0)break;nn = 0;char a, b;int f = 0;int fx = 0;int fff = 0;int fffx = 0;for(i = 0; i < M; i++)vec[i].clear();fill(is, is + M, false);for(i = 0; i < m; i++){scanf(" %c<%c", &a, &b);//printf("%c%c", a, b);int aa = a - 'A' + 1;int bb = b - 'A' + 1;if(!is[aa]){nn++;is[aa] = true;}if(!is[bb]){nn++;is[bb] = true;}vec[aa].push_back(bb);int choice = tosort(); // 1 代表有环 2 代表没有环但是不确定 3 代表 满足条件;if(choice == 1 && !f){f = 1; // 出现矛盾;fx = i + 1;}else if(choice == 3 && nn == n && !fff){fff = 1;fffx = i + 1;}}if(fff){printf("Sorted sequence determined after %d relations: ", fffx);for(int i = 0; i < n; i++)printf("%c", ans[i] - 1 + 'A');printf(".\n");}else if(f)printf("Inconsistency found after %d relations.\n", fx);elseprintf("Sorted sequence cannot be determined.\n");}return 0;}
例2:3687
题目描述: 有N个球，重量分别是1~N，给着n个球贴上标签。输入n，m代表n个球和m条边(a b)，代表 标签为a的要比标签为b的轻。最后输出标签1~N对应的重量（注意是重量，而不是轻重关系），还有要注意“ you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on... ”,意思是标签小的要尽可能贴在重量小的球上。(（输出是每个球第几重，而不是几号球比几号球重！）。
解题思路: 在基本的拓扑排序的基础上又增加了一个要求：编号最小的节点要尽量排在前面；在满足上一个条件的基础上，编号第二小的节点要尽量排在前面；在满足前两个条件的基础上，编号第三小的节点要尽量排在前面……依此类推。（注意，这和字典序是两回事，不可以混淆。）
如图所示，满足要求的拓扑序应该是：6 4 1 3 9 2 5 7 8 0。
一般来说，在一个有向无环图中，用 BFS 进行拓扑排序是比较常见的做法，如算法 1 所示。但是它不一定能得到本题要求的拓扑序。
- 把所有入度为 0 的节点放进队列 Q
- WHILE： Q 不是空队列
- 从 Q 中取出队列首元素 a，把 a 添加到答案的尾部。
- FOR：所有从 a 出发的边 a → b
- 把 b 的入度减 1。如果 b 的入度变为 0，则把 b 放进队列 Q。
算法 1 用 BFS 进行拓扑排序
为了解决本问题，下面让我来探究一下拓扑序的一些性质。以图 1 为例，节点 0 毫无疑问排在最后。除了节点 0 以外，有三条互相平行的路径：6 → 4 → 1、 3 → 9 → 2 和 5 → 7 → 8。一条路径上的各个节点的先后关系都是不能改变的，比如路径 6 → 4 → 1 上的三个节点在拓扑序中，一定是 6 在最前，1 在最后。但是，互相平行的各条路径，在总的拓扑序中任意交错都是合法的。比如，以下都是图 1 的合法拓扑序：
6 4 1 3 9 2 5 7 8 0、 3 6 9 4 5 1 7 8 2 0、 5 6 4 7 3 8 1 9 2 0、 3 5 6 4 1 7 9 2 8 0、 6 5 7 8 4 3 9 2 1 0。
怎么才能找出题目要求的拓扑序呢？在这里，我想用字典序最先的拓扑序来引出这个算法。算法 2 可以求出字典序最先的拓扑序。
- 把所有入度为 0 的节点放进优先队列 PQ
- WHILE： PQ 不是空队列
- 从 PQ 中取出编号最小的元素 a，把 a 添加到答案的尾部。
- FOR：所有从 a 出发的边 a → b
- 把 b 的入度减 1。如果 b 的入度变为 0，则把 b 放进优先队列 PQ。
算法 2 求出字典序最先的拓扑序
可见，算法 2 和算法 1 基本一样，只是把队列改成了优先队列。用它求出的图 1 的字典序最先的拓扑序为：3 5 6 4 1 7 8 9 2 0。但是这显然不是本题要求的答案，因为节点 1 的位置还不够靠前。
算法 2 可以算是一个贪心算法，每一步都找编号最小的节点。但是对于图 1 中的三条路径，头的编号比较小的，不一定要先出队列。正确的步骤应该如下：
节点 0 的位置是铁定在最后的，不用考虑。只考虑剩下的三条路径。
先找编号最小的，节点 1。把它和它所在的路径中位于它前面的节点全部拿出来。目前的答案是 6 4 1，这样， 节点 1 就尽量靠前了。
再找剩下的节点中编号最小的，节点 2。把它和它所在的路径中位于它前面的节点全部拿出来。目前的答案是 6 4 1 3 9 2 ，这样，节点 2 就尽量靠前了。
只剩下一条路径了，只能依次把其中的节点拿出来。最后答案就是 6 4 1 3 9 2 5 7 8 0。
显然，算法 2 的贪心策略对于这个问题是不可行的。不能着眼于每条路径的头，而是要找编号最小的节点在哪条路径上，优先把这条路径拿出来。但问题在于，在 BFS 的过程中，我们只能看到每条路径的头，看不到后面的节点，这该怎么办呢？
让我们换个角度想一想，节点 3 和 6，应该是 6 先出队列，因为节点 1 在 6 的后面。这和节点 3 和 6 的编号大小没有任何关系。但是，再看另外两条路径的尾部，节点 2 和 8，可以肯定地说，2 一定先出队列，因为它们后面都没有别的节点了，这个时候完全以这两个节点本身的编号大小决定顺序。归纳起来就是说，对于若干条平行的路径，小的头部不一定排在前面，但是大的尾部一定排在后面。于是，就有了算法 3。
- 把所有出度为 0 的节点放进优先队列 PQ
- WHILE： PQ 不是空队列
- 从 PQ 中取出编号最大的元素 a，把 a 添加到答案的头部。
- FOR：所有指向 a 的边 b → a
- 把 b 的出度减 1。如果 b 的出度变为 0，则把 b 放进优先队列 PQ。
算法 3 求出本题目要求的拓扑序
#include <iostream>#include <cstdio>using namespace std;int Map[210][210], indegree[210], Ans[210];int n, m, x, y;int i, j;void Topo() {for(i = n; i >= 1; i--) {for(j = n; j >= 1; j--) {if(indegree[j] == 0) {indegree[j]--;Ans[j] = i;for(int k = 1; k <= n; k++)if(Map[j][k] == 1)indegree[k]--;break;}}if(j < 1)break;}if(i >= 1)printf("-1\n");elsefor(i = 1; i <= n; i++)printf("%d%c", Ans[i], i == n ? '\n' : ' ');}void Solve() {int cases;scanf("%d", &cases);while(cases--) {memset(Map, 0, sizeof(Map));memset(indegree, 0, sizeof(indegree));scanf("%d%d", &n, &m);for(i = 1; i <= m; i++) {scanf("%d%d", &x, &y);if(!Map[y][x]) {Map[y][x] = 1;indegree[x]++;}}Topo();}}int main() {Solve();return 0;}
