[关闭]
@DATASOURCE 2015-10-29T09:27:45.000000Z 字数 18032 阅读 1682

排序算法

排序


快速排序法

概述

快速排序(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两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。
  1. //代码示例:
  2. #include<time.h>
  3. #include<stdlib.h>
  4. using namespace std;
  5. void swap(int *a, int *b){ // 简单的交换函数;
  6. int t;
  7. t = *a;
  8. *a = *b;
  9. *b = t;
  10. }
  11. void quicksort(int *a, int l, int r){ // 快排函数;
  12. int t, i, j;
  13. if(l < r){ // 递归结束条件;
  14. srand(time(NULL)); // 找一个随机数来作为每一个分区的基准数;
  15. t = l + rand()%(r - l + 1);
  16. swap(&a[t], &a[l]); // 将这个基准数放在数组的末尾;
  17. int base = a[l]; // 用base 来存储这个基准数;
  18. i = l, j = r;
  19. while (i < j)
  20. {
  21. while(i < j && a[j]>= base) // 从右向左找第一个小于x的数
  22. j--;
  23. if(i < j)
  24. a[i++] = a[j];
  25. while(i < j && a[i]< base) // 从左向右找第一个大于等于x的数
  26. i++;
  27. if(i < j)
  28. a[j--] = a[i];
  29. }
  30. a[i] = base;
  31. quicksort(a, l, i - 1);
  32. quicksort(a, i + 1, r);
  33. }
  34. }

复杂度分析

快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是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` 类型.
  • 对一维整型数组排序:
  1. intcmp(const void* a, const void*b) {
  2. return *(int*)a - *(int*)b;
  3. }
如果整型数组为`a[]`,其中元素个数为n,则`qsort(a,n,sizeof(a[0]),cmp);`即完成了对`a[]`数组的 升序排序. 如果要按降序排列,可将`return *(int*)a - *(int*)b;`改为 `return *(int*)b - *(int*)a;` 
  • 对 char 类型数组排序:
  1. int cmp(const void* a, const void* b) {
  2. return *(char*)a - *(char*)b;
  3. }
  4. charword[100];
  5. qsort(word,100,sizeof(word[0]),cmp);
  6. //即完成了对word 中的字符按升序排列.
  • double 类型数组排序:
  1. double in[100];
  2. int cmp(const void*a, const void*b) {
  3. return *(double*)a > *(double*)b ? 1 : -1;
  4. }
  5. qsort(in,100,sizeof(in[0]),cmp);
值得注意的是,`cmp` 里不能像对 `int` 排序那样写 `return *(double*)a - *(double*)b`,因为返回值 是整型,这样返回值是 `double` 会出错且不易察觉. 
  • 对字符串排序:
  1. chars[100][100];
  2. int cmp(const void* x, const void* y) {
  3. return strcmp((char*)x, (char*)y);
  4. }
  5. qsort(s, 100, sizeof(s[0]), cmp);
  • 对结构体一级排序:
  1. struct node {
  2. int a, b;
  3. }s[100];
  4. int cmp(const void*x, const void*y) {
  5. node xx = *(node*)x;
  6. node yy= *(node*)y;
  7. return xx.a - yy.a;
  8. }
  9. qsort(s, 100, sizeof(s[0]), cmp);
  10. //按 a 的升序对结构体 s 进行排序
  • 对结构体二级排序:
  1. struct node {
  2. int a; int b;
  3. }s[100];
  4. int cmp(const void* x, const void* y) {
  5. node xx = *(node*)x;
  6. node yy = *(node*)y;
  7. if(xx.a != yy.a) return xx.a - yy.a;
  8. else return xx.b - yy.b;
  9. }
  10. qsort(s,100,sizeof(s[0]),cmp);
  11. //先按 a 进行升序排序,如果a 相同,按 b 的升序排列.
  • 计算几何中求凸包的 cmp
  1. int cmp(const void *a, const void *b) // 重点 cmp 函数,把除了 1 点外的所有点,旋转角度排序
  2. {
  3. struct point *c = (point *)a;
  4. struct point *d = (point *)b;
  5. if(calc(*c,*d,p[1]) < 0) return 1;
  6. 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)) // 如果在一条直线上,则把远的放在前面
  7. return 1;
  8. else return -1;
  9. }

Sort cmp 函数的写法

默认排序顺序为从小到大 sort(arr, arr + n);
如果是没有定义小于运算的数据类型,或者想改变排序的顺序,就要用到第三参数——比较函数。比较函数是一个自己定义的函数,返回值是 bool 型,它规定了什么样的关系才是“小于”。想把刚才的整数数组按降序排列,可以先定义一个比较函数 cmp
  1. bool cmp(int a, int b){
  2. return a > b;
  3. }
排序的时候就写 sort(a,a+100,cmp);
假设自己定义了一个结构体 node
  1. struct node{
  2. int a;
  3. int b;
  4. double c;
  5. }
有一个 node 类型的数组 node arr[100] ,想对它进行排序:先按 a 值升序排列,如果 a 值相同,再按 b 值降序排列,如果 b 还相同,就按 c 降序排列。就可以写这样一个比较函数:

以下是代码片段:

  1. bool cmp(node x, node y){
  2. if(x.a != y.a) return x.a
  3. if(x.b != y.b) return x.b > y.b;
  4. return return x.c > y.c;
  5. }
排序时写 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.将另一序列剩下的所有元素直接复制到合并序列尾

代码示例

  1. #include<iostream>
  2. using namespace std;
  3. int c[1010];
  4. void mergesort(int *a, int l, int r){
  5. int mid, i, j, k;
  6. if(r - l > 1){ // 递归结束条件;
  7. mid = (l + r) / 2;
  8. mergesort(a, l, mid); // 分治思想的应用;
  9. mergesort(a, mid, r);
  10. i = l;
  11. j = mid;
  12. k = l;
  13. while(i < mid && j < r){ // 将每一个小区间[l, r) 中的元素排列到临时数组 c 中去;
  14. if(a[i] <= a[j])
  15. c[k++] = a[i++];
  16. else
  17. c[k++] = a[j++];
  18. }
  19. for(; i < mid; i++) // 将剩余的元素放在后面;
  20. c[k++] = a[i];
  21. for(; j < r; j++)
  22. c[k++] = a[j];
  23. for(i = l; i < r; i++)
  24. a[i] = c[i];
  25. }
  26. return;
  27. }
  28. int main(){
  29. int a[20] = {0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
  30. for(int i = 0; i < 20; i++)
  31. cout << a[i] <<" ";
  32. cout << endl;
  33. mergesort(a, 0, 20);
  34. for(int i = 0; i < 20; i++)
  35. cout << a[i] <<" ";
  36. cout << endl;
  37. return 0 ;
  38. }

复杂度分析

时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。空间复杂度为 O(n)比较操作的次数介于(nlogn) / 2和nlogn - n + 1。赋值操作的次数是(2nlogn)。归并算法的空间复杂度为:0 (n)归并排序比较占用内存,但却是一种效率高且稳定的算法。

其他作用(求逆序数)

修改合并排序在合并两个子序列时,出现右边元素小于左边元素的情况,亦即a[j]

  1. //代码:
  2. while(i < mid && j < r){ // 将每一个小区间[l, r) 中的元素排列到临时数组 c 中去;
  3. if(a[i] <= a[j])
  4. c[k++] = a[i++];
  5. else{
  6. c[k++] = a[j++];
  7. ans += mid i; // 在此处求逆序数;
  8. }

堆排序(详见数据结构, 堆)

简述

堆排序(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个关键字即可以使得文件递增有序。
    • 用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止

代码示例

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. int heap[20]; // 用数组模拟堆;
  5. int n; // 堆中元素的数量;
  6. void Minheapsortdown(int i, int m){ // 向下调整下标为i的元素直到合适的位置;
  7. int j, temp;
  8. temp = heap[i]; // 依然临时变量temp来记录该元素的值;
  9. j = 2 * i + 1; // 令j等于其中一个儿子的值;
  10. while(j < m){
  11. if(j + 1 < m && heap[j + 1] < heap[j]) // 选择一个父节点下面较小的儿子来交换;
  12. j++;
  13. if(heap[j] >= temp) // 当所有的儿子都大于该元素的时候, 停止;
  14. break;
  15. heap[i] = heap[j]; // 否则, 将比较小的儿子放到父节点的位置;
  16. i = j; // 更新i和 j的值;
  17. j = 2 * i + 1;
  18. }
  19. heap[i] = temp; // 将temp放到合适的位置;
  20. }
  21. void makeMinheap(){ // 对一个数组进行堆化操作;
  22. int i;
  23. for(i = n / 2 - 1; i >= 0; i--) // 注意此处从n / 2 – 1 开始排列;
  24. Minheapsortdown(I, n);
  25. }
  26. void Minheapsort(){ // 堆排序;
  27. for(int i = n - 1; i >= 1; i--){
  28. swap(&heap[0], &heap[i]); // 每次排序可以确定一个最小值(堆顶元素), 将其放在数组的末尾;
  29. Minheapsortdown(0, i); // 每次排好 顶元素;
  30. }
  31. }
  32. int main(){
  33. int i;
  34. for(i = 0; i < 10; i++)
  35. heap[i] = -i;
  36. n = 10;
  37. for(i = 0; i < 10; i++)
  38. cout << heap[i] <<" ";
  39. cout << endl;
  40. makeMinheap();
  41. for(i = 0; i < 10; i++)
  42. cout << heap[i] <<" ";
  43. cout << endl;
  44. Minheapsort();
  45. for(i = 0; i < 10; i++)
  46. cout << heap[i] <<" ";
  47. cout << endl;
  48. return 0;
  49. }

复杂度分析

堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。平均性能O(N*logN)。

其他性能

由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序是就地排序,辅助空间为O(1).它是不稳定的排序方法。

STL 中的堆排序

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<vector>
  5. using namespace std;
  6. bool cmp(int a, int b){ // 实现最小堆的比较函数;
  7. return a > b;
  8. }
  9. void print(int elem)
  10. {
  11. cout << elem << ' ';
  12. }
  13. int main(){
  14. int n;
  15. vector <int> hea; // 定义堆;
  16. while(cin >> n && n)
  17. hea.push_back(n); // 向堆中添加数据, 并放在尾部;
  18. printf("%s\n", "After make_heap: ");
  19. make_heap(hea.begin(), hea.end(), cmp);
  20. for_each(hea.begin(), hea.end(), print);
  21. printf("\n");
  22. printf("%s\n", "After sort_heap: ");
  23. sort_heap(hea.begin(), hea.end(), cmp); // 堆排序函数, 从小到大排序;
  24. for_each(hea.begin(), hea.end(), print);
  25. printf("\n");
  26. return 0;
  27. }

以上四种排序算法的总结

时空复杂度和稳定性

程序效率验证

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <ctime>
  4. using namespace std;
  5. //------------------------快速排序(普通)--------------------------
  6. void quick_sort(int s[], int l, int r)
  7. {
  8. if (l < r)
  9. {
  10. int i = l, j = r, x = s[l];
  11. while (i < j)
  12. {
  13. while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
  14. j--;
  15. if(i < j)
  16. s[i++] = s[j];
  17. while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
  18. i++;
  19. if(i < j)
  20. s[j--] = s[i];
  21. }
  22. s[i] = x;
  23. quick_sort(s, l, i - 1); // 递归调用
  24. quick_sort(s, i + 1, r);
  25. }
  26. }
  27. //-----------------------快速排序(随机)--------------------------
  28. void swap(int *a, int *b){ // 简单的交换函数;
  29. int t;
  30. t = *a;
  31. *a = *b;
  32. *b = t;
  33. }
  34. void quick_sort1(int *a, int l, int r){ // 快排函数;
  35. int t, i, j;
  36. if(l < r){ // 递归结束条件;
  37. srand(time(NULL)); // 找一个随机数来作为每一个分区的基准数;
  38. t = l + rand()%(r - l + 1);
  39. swap(&a[t], &a[l]); // 将这个基准数放在数组的末尾;
  40. int base = a[l]; // 用base 来存储这个基准数;
  41. i = l, j = r;
  42. while (i < j)
  43. {
  44. while(i < j && a[j]>= base) // 从右向左找第一个小于x的数
  45. j--;
  46. if(i < j)
  47. a[i++] = a[j];
  48. while(i < j && a[i]< base) // 从左向右找第一个大于等于x的数
  49. i++;
  50. if(i < j)
  51. a[j--] = a[i];
  52. }
  53. a[i] = base;
  54. quick_sort(a, l, i - 1);
  55. quick_sort(a, i + 1, r);
  56. }
  57. }
  58. //------------------------归并排序----------------------------
  59. //将有二个有序数列a[first...mid]和a[mid...last]合并。
  60. void mergearray(int a[], int first, int mid, int last, int temp[])
  61. {
  62. int i = first, j = mid + 1;
  63. int m = mid, n = last;
  64. int k = 0;
  65. while (i <= m && j <= n)
  66. {
  67. if (a[i] < a[j])
  68. temp[k++] = a[i++];
  69. else
  70. temp[k++] = a[j++];
  71. }
  72. while (i <= m)
  73. temp[k++] = a[i++];
  74. while (j <= n)
  75. temp[k++] = a[j++];
  76. for (i = 0; i < k; i++)
  77. a[first + i] = temp[i];
  78. }
  79. void mergesort(int a[], int first, int last, int temp[])
  80. {
  81. if (first < last)
  82. {
  83. int mid = (first + last) / 2;
  84. mergesort(a, first, mid, temp); //左边有序
  85. mergesort(a, mid + 1, last, temp); //右边有序
  86. mergearray(a, first, mid, last, temp); //再将二个有序数列合并
  87. }
  88. }
  89. bool MergeSort(int a[], int n)
  90. {
  91. int *p = new int[n];
  92. if (p == NULL)
  93. return false;
  94. mergesort(a, 0, n - 1, p);
  95. return true;
  96. }
  97. //------------------------堆排序---------------------------
  98. inline void Swap(int &a, int &b)
  99. {
  100. int c = a;
  101. a = b;
  102. b = c;
  103. }
  104. //建立最小堆
  105. // 从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
  106. void MinHeapFixdown(int a[], int i, int n)
  107. {
  108. int j, temp;
  109. temp = a[i];
  110. j = 2 * i + 1;
  111. while (j < n)
  112. {
  113. if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的
  114. j++;
  115. if (a[j] >= temp)
  116. break;
  117. a[i] = a[j]; //把较小的子结点往上移动,替换它的父结点
  118. i = j;
  119. j = 2 * i + 1;
  120. }
  121. a[i] = temp;
  122. }
  123. //建立最小堆
  124. void MakeMinHeap(int a[], int n)
  125. {
  126. for (int i = n / 2 - 1; i >= 0; i--)
  127. MinHeapFixdown(a, i, n);
  128. }
  129. void MinheapsortTodescendarray(int a[], int n)
  130. {
  131. for (int i = n - 1; i >= 1; i--)
  132. {
  133. Swap(a[i], a[0]);
  134. MinHeapFixdown(a, 0, i);
  135. }
  136. }
  137. const int MAXN = 5000000;
  138. int a[MAXN];
  139. int b[MAXN], c[MAXN], d[MAXN], e[MAXN];
  140. int main()
  141. {
  142. int i;
  143. srand(time(NULL));
  144. for (i = 0; i < MAXN; ++i)
  145. a[i] = rand() * rand(); //注rand()产生的数在0到0x7FFF之间
  146. for (i = 0; i < MAXN; ++i)
  147. e[i] = d[i] = c[i] = b[i] = a[i];
  148. clock_t ibegin, iend;
  149. printf("n == %d\n", MAXN);
  150. //快速排序
  151. printf("quick_sort: ");
  152. ibegin = clock();
  153. quick_sort(a, 0, MAXN - 1);
  154. iend = clock();
  155. printf("%d MS\n", iend - ibegin);
  156. printf("quick_sort1: ");
  157. ibegin = clock();
  158. quick_sort(e, 0, MAXN - 1);
  159. iend = clock();
  160. printf("%d MS\n", iend - ibegin);
  161. //归并排序
  162. printf("MergeSort: ");
  163. ibegin = clock();
  164. MergeSort(b, MAXN);
  165. iend = clock();
  166. printf("%d MS\n", iend - ibegin);
  167. //堆排序
  168. printf("Heap_Sort: ");
  169. ibegin = clock();
  170. MakeMinHeap(c, MAXN);
  171. MinheapsortTodescendarray(c, MAXN);
  172. iend = clock();
  173. printf("%d MS\n", iend - ibegin);
  174. //STL中的堆排序
  175. printf("STL_Heap_sort: ");
  176. ibegin = clock();
  177. make_heap(d, d + MAXN);
  178. sort_heap(d, d + MAXN);
  179. iend = clock();
  180. printf("%d MS\n", iend - ibegin);
  181. return 0;
  182. }
  • 程序运行结果

拓扑排序

概述

一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(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)图所示。

图1
(4) 在(d)图上依次输出顶点v3,v4和v5,并在每个顶点输出后删除该顶点及出边,操作都很简单,不再赘述。为了利用C++语言在计算机上实现拓扑排序算法,AOV网采用邻接表表示较方便。如对于上图(a),对应的邻接表如下图2.
图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.

代码示例

  1. #include <vector>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <algorithm>
  5. #define M 110
  6. using namespace std;
  7. vector <int> vec[M]; // 邻接表;
  8. int ingree[M]; // 存储节点的入度;
  9. int ans[M]; // 存储排序后的数字;
  10. int n, m; // 点数;
  11. bool TOSort(){ // 排序成功返回 true 否则返回 false;
  12. int i, j;
  13. int top = -1; // 栈顶;
  14. int count = 0; // 排序数组的指针;
  15. fill(ingree, ingree + M, 0);
  16. for(i = 1; i <= n; i++){ // 初始化入度数组, 统计所有点的入度;
  17. int end = vec[i].size();
  18. for(j = 0; j < end; j++)
  19. ingree[vec[i][j]]++;
  20. }
  21. for(i = 1; i <= n; i++) // 初始化栈;
  22. if(ingree[i] == 0){
  23. ingree[i] = top;
  24. top = i;
  25. }
  26. while(top != -1){ // -1 为栈底;
  27. int t = top;
  28. top = ingree[t];
  29. ans[count++] = t;
  30. int end = vec[t].size();
  31. for(i = 0; i < end; i++){ // 删除入度为零的点的边;
  32. ingree[vec[t][i]]--;
  33. if(ingree[vec[t][i]] == 0){
  34. ingree[vec[t][i]] = top;
  35. top = vec[t][i];
  36. }
  37. }
  38. }
  39. if(count < n)
  40. return false;
  41. return true;
  42. }
  43. int main(){
  44. int i, a, b;
  45. scanf("%d%d", &n, &m); // 输入点的个数, 和边的个数;
  46. for(i = 0; i < m; i++){
  47. scanf("%d%d", &a, &b); // a -> b 边;
  48. vec[a].push_back(b);
  49. }
  50. if(TOSort())
  51. for(i = 0; i < n; i++)
  52. printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
  53. else
  54. printf("有环\n");
  55. return 0;
  56. }

复杂度分析

拓扑排序实际上是对邻接表表示的图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.”
  1. #include <queue>
  2. #include <stack>
  3. #include <vector>
  4. #include <cstdio>
  5. #include <iostream>
  6. #include <algorithm>
  7. #define M 30
  8. using namespace std;
  9. vector <int> vec[M];
  10. int degree[M];
  11. int ans[M];
  12. bool is[M];
  13. int n, m, nn;
  14. int tosort(){
  15. int i, j;
  16. int f = 0; // 记录是否出现不确定的情况;
  17. int ff = 0; // 记录是否出现了环;
  18. int count = 0;
  19. fill(degree, degree + M, 0);
  20. stack <int> sta;
  21. for(i = 1; i <= n; i++){
  22. int end = vec[i].size();
  23. for(j = 0; j < end; j++)
  24. degree[vec[i][j]]++;
  25. //cerr << 1 << endl;
  26. }
  27. for(i = 1; i <= n; i++){
  28. if(degree[i] == 0 && is[i])
  29. sta.push(i);
  30. //cerr << 2 << endl;
  31. }
  32. if(sta.size() > 1)
  33. f = 1;
  34. while(!sta.empty()){
  35. int t = sta.top();
  36. sta.pop();
  37. ans[count++] = t;
  38. int end = vec[t].size();
  39. for(i = 0; i < end; i++){
  40. int k = vec[t][i];
  41. degree[k]--;
  42. if(degree[k] == 0)
  43. sta.push(k);
  44. //cerr << 3 << endl;
  45. }
  46. if(sta.size() > 1)
  47. f = 1;
  48. }
  49. if(count < nn)
  50. return 1; // 出现环;
  51. else if(f)
  52. return 2; // 出现了不确定答案;
  53. else
  54. return 3; // nn 个元素正常拓扑排序;
  55. }
  56. int main(){
  57. int i, j;
  58. while(scanf("%d%d", &n, &m) != EOF){
  59. if(n == 0 && m == 0)
  60. break;
  61. nn = 0;
  62. char a, b;
  63. int f = 0;
  64. int fx = 0;
  65. int fff = 0;
  66. int fffx = 0;
  67. for(i = 0; i < M; i++)
  68. vec[i].clear();
  69. fill(is, is + M, false);
  70. for(i = 0; i < m; i++){
  71. scanf(" %c<%c", &a, &b);
  72. //printf("%c%c", a, b);
  73. int aa = a - 'A' + 1;
  74. int bb = b - 'A' + 1;
  75. if(!is[aa]){
  76. nn++;
  77. is[aa] = true;
  78. }
  79. if(!is[bb]){
  80. nn++;
  81. is[bb] = true;
  82. }
  83. vec[aa].push_back(bb);
  84. int choice = tosort(); // 1 代表有环 2 代表没有环但是不确定 3 代表 满足条件;
  85. if(choice == 1 && !f){
  86. f = 1; // 出现矛盾;
  87. fx = i + 1;
  88. }
  89. else if(choice == 3 && nn == n && !fff){
  90. fff = 1;
  91. fffx = i + 1;
  92. }
  93. }
  94. if(fff){
  95. printf("Sorted sequence determined after %d relations: ", fffx);
  96. for(int i = 0; i < n; i++)
  97. printf("%c", ans[i] - 1 + 'A');
  98. printf(".\n");
  99. }
  100. else if(f)
  101. printf("Inconsistency found after %d relations.\n", fx);
  102. else
  103. printf("Sorted sequence cannot be determined.\n");
  104. }
  105. return 0;
  106. }

例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 所示。但是它不一定能得到本题要求的拓扑序。

    1. 把所有入度为 0 的节点放进队列 Q
    2. WHILE: Q 不是空队列
    3. 从 Q 中取出队列首元素 a,把 a 添加到答案的尾部。
    4. FOR:所有从 a 出发的边 a → b
    5. 把 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 可以求出字典序最先的拓扑序。

    1. 把所有入度为 0 的节点放进优先队列 PQ
    2. WHILE: PQ 不是空队列
    3. 从 PQ 中取出编号最小的元素 a,把 a 添加到答案的尾部。
    4. FOR:所有从 a 出发的边 a → b
    5. 把 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。

    1. 把所有出度为 0 的节点放进优先队列 PQ
    2. WHILE: PQ 不是空队列
    3. 从 PQ 中取出编号最大的元素 a,把 a 添加到答案的头部。
    4. FOR:所有指向 a 的边 b → a
    5. 把 b 的出度减 1。如果 b 的出度变为 0,则把 b 放进优先队列 PQ。
  • 算法 3 求出本题目要求的拓扑序

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. int Map[210][210], indegree[210], Ans[210];
  5. int n, m, x, y;
  6. int i, j;
  7. void Topo() {
  8. for(i = n; i >= 1; i--) {
  9. for(j = n; j >= 1; j--) {
  10. if(indegree[j] == 0) {
  11. indegree[j]--;
  12. Ans[j] = i;
  13. for(int k = 1; k <= n; k++)
  14. if(Map[j][k] == 1)
  15. indegree[k]--;
  16. break;
  17. }
  18. }
  19. if(j < 1)
  20. break;
  21. }
  22. if(i >= 1)
  23. printf("-1\n");
  24. else
  25. for(i = 1; i <= n; i++)
  26. printf("%d%c", Ans[i], i == n ? '\n' : ' ');
  27. }
  28. void Solve() {
  29. int cases;
  30. scanf("%d", &cases);
  31. while(cases--) {
  32. memset(Map, 0, sizeof(Map));
  33. memset(indegree, 0, sizeof(indegree));
  34. scanf("%d%d", &n, &m);
  35. for(i = 1; i <= m; i++) {
  36. scanf("%d%d", &x, &y);
  37. if(!Map[y][x]) {
  38. Map[y][x] = 1;
  39. indegree[x]++;
  40. }
  41. }
  42. Topo();
  43. }
  44. }
  45. int main() {
  46. Solve();
  47. return 0;
  48. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注