实现k路归并排序

Question

import random as r
import heapq as h

n = 4
yo = 0
jk = []
o = []
l = 0

for ih in range(0, 5):
    jk = []

    for i in range(n):
        t = r.randint(0, 10)
        jk.append(t)

    jk.sort()    
    o.append(jk)

for i in o:
    print(i)

def ksort(l, a, b, c):
    print('c=', end='')
    print(c)
    print()

    for i in range(len(a)):
        if a[i] > (len(l[i])):
            a[i] = -3

    for i in range(len(l)):
        if a[i] >= 0:
            b[i] = l[i][a[i]]

    h.heapify(b)

    #print(a)
    #print(b)

    c.append(b[0])

    yu = b[0]
    op = 0
    for i in range(len(l)):
        if a[i] >= 0 and (l[i][a[i]] == yu) and op == 0:
            a[i] += 1
            b[i] = l[i][a[i] + 1]
            op = 1
    ksort(l, a, b, c)

ju = ksort(o, [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [])

ju

​

​

我使用上面的代码来实现k-way合并排序。我对每个单独列表的长度是4，但在某个点之后，由于超出范围的错误，它崩溃了。有谁能提点建议吗？

Answer 1

当所有元素都已合并时，代码不会检查终止条件。还有一些其他问题或不需要的代码。我修改了问题代码，它似乎起作用了。

import random as r
import heapq as h

def ksort(l):
    a = [0]*len(l)
    c = []
    while True:
        for i in range(len(a)):
            if a[i] >= (len(l[i])):
                a[i] = -1
        j = 0                       #check if done
        for i in range(len(a)):
            if a[i] == -1:
                j = j + 1
        if j == len(a):
            return c
        b = []
        for i in range(len(l)):
            if a[i] >= 0:
                b.append(l[i][a[i]])
        h.heapify(b)                #only used to find smallest element
        c.append(b[0])
        yu = b[0]                   #scan for b[0] and advance corresponding index
        op = 0
        for i in range(len(l)):
            if a[i] >= 0 and (l[i][a[i]] == yu) and op == 0:
                a[i] += 1
                #b[i] = l[i][a[i] + 1]
                op = 1

n = 4
yo = 0
jk = []
o = []
l = 0

for ih in range(0, 5):
    jk = []

    for i in range(n):
        t = r.randint(0, 10)
        jk.append(t)

    jk.sort()    
    o.append(jk)

ju = ksort(o)

print(ju)

使用堆的C++ K方式合并排序的示例。请注意，由于堆开销，K路合并排序比传统的合并排序慢。K路合并与堆的典型用法是在执行外部(磁盘驱动器)排序时。使用标准的基于内存的排序来创建一组排序的临时文件(根据可用内存，一次创建一个文件)，然后使用K路合并来合并临时文件，直到产生单个排序的文件。然而，4路合并排序可以使用嵌套的if语句而不是堆来实现，并且比传统的2路合并排序快大约15%。

static void MergeSort(uint64_t *a, size_t n)
{
    uint64_t *b = new uint64_t [n];             // second buffer
    uint64_t *t = b;                            // backup of ptr to b
    std::pair<size_t, size_t>h[K];              // heap
    size_t s = 1;                               // run size
    while(s < n){
        size_t i = 0, k, o = 0;
        while(i < n){
            for(k = 0; k < K && i < n; k++){    // init run indexes
                h[k].first  = i;
                i = min(i+s, n);
                h[k].second = i;
            }
            std::make_heap(h+0, h+k,            // create heap
                [&a](std::pair<size_t, size_t>i, std::pair<size_t, size_t>j){
                    return a[i.first] > a[j.first];});
            while(k){                           // merge heap into b[]
                std::pop_heap(h+0, h+k,         //  pop run with smallest element
                    [&a](std::pair<size_t, size_t>i, std::pair<size_t, size_t>j){
                        return a[i.first] > a[j.first];});
                --k;
                b[o++] = a[h[k].first++];       //  copy element
                if(h[k].first == h[k].second)   //  if end run continue
                    continue;
                ++k;                            //  else update heap
                std::push_heap(h+0, h+k,
                    [&a](std::pair<size_t, size_t>i, std::pair<size_t, size_t>j){
                        return a[i.first] > a[j.first];});
                }
            }
            s *= K;                             // bump run size
            std::swap(a, b);                    // swap ptrs
        }
    if(t == a)                                  // if sorted data is in what was originally b
        std::memcpy(b, a, n*sizeof(uint64_t));  //  copy to what was orignally a
    delete[] t;                                 // delete what was originally b
}