分类： IT业界
2012-07-30 11:42:13
多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k。
(1)假设有K路数据流，流内部是有序的，且流间同为升序或降序
(2)首先读取每个流的第一个数，如果已经EOF，pass
(3)将有效的k(k可能小于K)个数比较，选出最小的那路mink，输出，读取mink的下一个
(4)直到所有K路都EOF
代码如下：
| 001 | /* |
| 002 | * main.c |
| 003 | * |
| 004 | * Created on: 2011-11-11 |
| 005 | * Author: liheyuan |
| 006 | */ |
| 007 |
| 008 | #include |
| 009 | #include |
| 010 | #include |
| 011 |
| 012 | typedef int TYPE; |
| 013 |
| 014 | #define MIN_MAX 8888 |
| 015 |
| 016 | void k_merge(TYPE** arrs, int* lens, int k) |
| 017 | { |
| 018 | int* cnts = (int*) malloc(sizeof(int) * k); |
| 019 | int* has_next = (int*) malloc(sizeof(int) * k); |
| 020 | TYPE* datas = (int*) malloc(sizeof(int) * k); |
| 021 | int i; |
| 022 | int min_index = 0; |
| 023 | TYPE min; |
| 024 |
| 025 | //Read each k-way first into data |
| 026 | for (i = 0; i < k; i++) |
| 027 | { |
| 028 | if (lens[i] >= 1) |
| 029 | { |
| 030 | datas[i] = arrs[i][0]; |
| 031 | cnts[i] = 1; |
| 032 | has_next[i] = 1; |
| 033 | } |
| 034 | else |
| 035 | { |
| 036 | has_next[i] = 0; |
| 037 | } |
| 038 | } |
| 039 |
| 040 | while (1) |
| 041 | { |
| 042 |
| 043 | //Select min in k |
| 044 | min = MIN_MAX; |
| 045 | min_index = 0; |
| 046 | for (i = 0; i < k; i++) |
| 047 | { |
| 048 | if (has_next[i]) |
| 049 | { |
| 050 | if (datas[i] < min) |
| 051 | { |
| 052 | min = datas[i]; |
| 053 | min_index = i; |
| 054 | } |
| 055 | } |
| 056 | } |
| 057 |
| 058 | if (min == MIN_MAX) |
| 059 | { |
| 060 | //No way has data |
| 061 | break; |
| 062 | } |
| 063 | else |
| 064 | { |
| 065 |
| 066 | printf("%d\n", datas[min_index]); |
| 067 |
| 068 | //Succ get one min |
| 069 | if (cnts[min_index] < lens[min_index]) |
| 070 | { |
| 071 | datas[min_index] = arrs[min_index][cnts[min_index]]; |
| 072 | cnts[min_index]++; |
| 073 | } |
| 074 | else |
| 075 | { |
| 076 | has_next[min_index] = 0; |
| 077 | } |
| 078 | } |
| 079 | } |
| 080 |
| 081 | free(cnts); |
| 082 | } |
| 083 |
| 084 | //void k_merge(TYPE** arrs, int* lens, int k) |
| 085 |
| 086 | int main() |
| 087 | { |
| 088 | TYPE a[5] = |
| 089 | { 1, 3, 5, 7, 17 }; |
| 090 | TYPE b[3] = |
| 091 | { -1, 10, 20 }; |
| 092 | TYPE c[4] = |
| 093 | { -20, 30, 88, 111 }; |
| 094 | TYPE* arrs[3] = |
| 095 | { a, b, c }; |
| 096 | int lens[3] = |
| 097 | { 5, 3, 4 }; |
| 098 |
| 099 | k_merge(arrs, lens, 3); |
| 100 |
| 101 | return 0; |
| 102 | } |
输出：
| 01 | -20 |
| 02 | -1 |
| 03 | 1 |
| 04 | 3 |
| 05 | 5 |
| 06 | 7 |
| 07 | 10 |
| 08 | 17 |
| 09 | 20 |
| 10 | 30 |
| 11 | 88 |
| 12 | 111 |
